Find $21^{1234}\pmod{100}\equiv \ ?$

Question

The I'm having trouble to do this only by hand (no software or calculator). I tried the following:

\begin{align}21^{1234}(\text{mod} \ 100) &= 21^{1000}21^{200}21^{20}21^4(\text{mod} \ 100)\equiv41^{500}41^{100}41^{15}41^2(\text{mod} \ 100)\\ \end{align}

It's not reasonable to continue taking powers of 21, takes too long with pen and paper. Is there a more efficient way?

Yes I know about the Euler theorem and his totient function but please I don't want to use it, only elementary methods.

Answer 1

Does the binomial theorem count as an elementary method? If so, we can just do $21^{1234} \equiv (20+1)^{1234} \equiv 20^{1234} + \binom{1234}{1} \cdot 20^{1233} + ... + 20\cdot \binom{1234}{1} + 1 \pmod{100}$. Then, if the exponent of $20$ is greater than or equal to $2$, it is divisible by $100$, so we simply get $20 \cdot 1234 + 1 \equiv 81 \pmod{100}$.

Otherwise, just break it down $\pmod{4}$ and $\pmod{25}$, and evaluate the first few terms, which should give you $1 \pmod{4}$ and $6 \pmod{25} \implies 81 \pmod{100}$.

Answer 2

Note that the first five powers of 21 end in 21, 41, 61, 81, and 01, respectively. So the pattern repeats every five terms, and the result is therefore 81.

Answer 3

Applying the Lemma below, with $\,u(a) = $ units digit of $a,\,$ and $\,t(a) =$ tens digit, we obtain

$\ \ u(21^{1234}) = 1,\,\ t(21^{1234}) = u(123\color{#c00}4)\,t(\color{#0a0}21) = \color{#c00}4\cdot\color{#0a0}2 = \color{#f0f}8,\ $ so $\, \ \bbox[6px,border:1px solid red]{\color{#0a0}21^{\large 123\color{#c00}4}\equiv \color{#f0f}81\pmod{\!100}}$

Lemma $\ \ u(a)=1\ \Rightarrow\ u(a^n)=1,\ \ t(a^n) = u(n)\,t(a)\bmod 10\ \ $ [Tens Logarithm Law]

Proof $\,\ a = 1\!+\!10k\,\Rightarrow\, a^n = (1\!+\!10k)^n = 1+10nk + 100(\cdots)\,$ by the Binomial Theorem.

This implies $\ u(a^n)=1,\ $ and $\,\bmod 10\!:\,\ t(a^n) \equiv nk\equiv n\,t(a)\equiv u(n)\,t(a)$

Remark $ $ Notice in particular: $\bmod 10\!:\ t(a^n) \equiv n\, t(a),\,$ thus the name "tens logarithm"

See also here.

Answer 4

$3^4< 100 < 3^5 = 243 \equiv 43 \pmod{100}$

So $3^{5k}\equiv 43^{k}\pmod {100}$.

$43^2 = (40 + 3)^2 = 1600 + 2*3*40 + 9 \equiv 49 \pmod {100}$

So $3^{10k} \equiv 49^k \pmod {100}$.

$49^2 = (50-1)^2 = 2500 - 100 + 1 \equiv 1 \pmod {100}$.

So $3^{20k}\equiv 1\pmod{100}$ so

$3^{1234} \equiv 3^{14} \equiv 49*3^4 = (50-1)(80+1) \equiv 4000-80 + 50 -1 \equiv -31\equiv 69\pmod{100}$.

Do similar crap for $7$.

$7^2 = 49$ and so $7^4 = (50-1)^2 = 2500- 100 + 1\equiv 1 \pmod {100}$

So $7^{4k}\equiv 1 \pmod {100}$ and $7^{1234} \equiv 7^2 \equiv 49\pmod {100}$.

So $21^{1234} = 3^{12347}7^{1234} \equiv 69*49 \equiv (70 -1)(50-1) \equiv 3500 -70-50 + 1\equiv 81\pmod{100}$.