2

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.

J. W. Tanner
  • 60,406
Parseval
  • 6,413
  • Powers of $21$ are easy. $21^3 \equiv 61 \pmod {100}, 21^4 \equiv 81\pmod {100}.$ Futhermore. if $\gcd(a,100) = 1$ then $a^{20}\equiv 1\pmod{100}$ – Doug M Feb 05 '19 at 21:31
  • Hint: Write $1234$ in binary. – Shaun Feb 05 '19 at 21:32
  • 4
    " but please I don't want t use it" Why the hell not? Then you have utterly no reason to expect this to be easy. "only elementary methods" Euler's theorem is elementary. – fleablood Feb 06 '19 at 00:16
  • @fleablood - Yeah, so here is my answer after thinking about it for 4.5 years: Because the exam did not allow Eulers method :P – Parseval Sep 20 '23 at 12:33

4 Answers4

3

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.

Jim Ferry
  • 2,323
  • 1
    This method just seems to work if one is lucky. If I sit on an exam I wont just start calculating powers like that by hand until a pattern repeats. What if this was an example where it did not repeat until the 15th power? – Parseval Feb 06 '19 at 00:00
  • You know it's going to reapeat in 40 interations. Is try divisors of $40$ first. $2,4, 8, 5, 10, 20, 40$. Just because you don't want to use Euler Th. is no reason to play dumb and pretend you don't know it. – fleablood Feb 06 '19 at 00:25
  • It won't take many attempts at $(10a \pm k)^2 = 100a^2 \pm20ak + k^2\equiv 10b \pm j$ and repeat to break anything down to repetitions. In an exam it won't take too long to do it. – fleablood Feb 06 '19 at 00:44
  • For last-digits questions, it can help to use the (tighter) Carmichael lambda function instead of Euler's totient. $\lambda(n)$ is 4, 20, and 100 for $n =$ 10, 100, and 1000, and is $n/20$ for larger powers of 10. – Jim Ferry Feb 06 '19 at 03:06
3

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}$.

Bill Dubuque
  • 272,048
ETS1331
  • 1,335
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.

Bill Dubuque
  • 272,048
  • This was interesiting. Never heard of this lemma. What does the functions $u$ and $t$ really do besides setting $a$ and $a^n$ to $1$? Also, if I want the last 3 digits, is there a version called hundreds logarithm law? – Parseval Feb 05 '19 at 23:50
  • @Parseval As above, $u(a)$ is the units digit of $a$ so $,u(a) = a\bmod 10,,$ and $,t(a)$ is its tens digit, so $,t(a) = (a-u(a))/10\bmod 10.,$ Yes, you can extend it to more digits by taking more terms in the Bionomial Theorem. The answer you accepted is a special case of this. The formula tells you how to do it for any integer $a^n$ when $a$ has units digit $= 1$ by simply multiplying the tens digit of $a$ with the units digit of $n.,$ If it is not clear let me know where and I can elaborate. – Bill Dubuque Feb 06 '19 at 00:22
  • 2
    @Parseval Btw, the accepted answer is incorrect: it is $81$ not $1\pmod{!100}.\ $ – Bill Dubuque Feb 06 '19 at 00:36
  • Yes I know, I figured that out. Just liked the method, was simple enough. – Parseval Feb 06 '19 at 14:37
1

$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}$.

fleablood
  • 124,253
  • Why split $,21 = 7*3,$ when we can already apply the Binomial Theorem to $,21 = 20+1$? (see my answer or ETS1331's). Splitting it makes it much more work. – Bill Dubuque Feb 06 '19 at 01:00
  • 1
    Because I didn't think of it. Although by the time one does work through this the binomial theorem will probably become obvious. But why do ANY of this when we can do Euler's th? In my mind you can't go wrong breaking things down to smaller parts. So if you the question is "How can I do this if I pretend I don't know the smart way to do it" I figure a good answer is "try simple things and see if you get something easier". Binomial Theorem is still a smart and clever thing that might not occur to one. – fleablood Feb 06 '19 at 01:06