# Calculation of the last three digits of $132^{1601}$ (solving $x \equiv 132^{1601} \pmod {1000}$)

I want to calculate the last three digits of $$132^{1601}$$. This is equivalent to find $$x \equiv 132^{1601} \pmod {1000}$$.

This is how I've solved it:

$$\Phi(1000)=400,$$

$$132^{400} \equiv 1 \pmod {1000},$$

So $$x \equiv 132^{1601} \pmod {1000} \equiv (132^{400})^4132 \pmod {1000} \equiv 132 \pmod {1000}.$$

Is this approach correct?

Thanks.

EDIT: one of my friends suggest that it must be split using the Chinese reminder theorem and that the solution is $$632 \pmod {1000}$$. How is that possible?

• Note: Euler doesn't apply here since $\gcd(132,1000)>1$. – lulu Feb 2 at 19:11
• Your friend is correct; I have posted a solution along those lines below. – lulu Feb 2 at 19:19
• math.stackexchange.com/questions/607829/… – lab bhattacharjee Feb 2 at 19:21
• – lab bhattacharjee Feb 2 at 19:23
• @lab Thanks for spending the time to gather that list of related questions. – Bill Dubuque Feb 2 at 21:27

You can not apply Euler to this directly, since $$132$$ is not relatively prime to $$1000$$. Indeed, it is clear that $$132^{400}\not \equiv 1 \pmod {1000}$$ since this would imply that $$2\,|\,1$$.

To solve the problem, work mod $$2^3$$ and $$5^3$$ separately. Clearly $$132^{1601}\equiv 0\pmod {2^3}$$. Now, $$\varphi(5^3)=100$$ and Euler applies here (since $$\gcd(132,5)=1$$) so we do have $$132^{100}\equiv 1 \pmod {5^3}\implies 132^{1600}\equiv 1 \pmod {5^3}$$

Thus $$132^{1601}\equiv 132\equiv 7\pmod {5^3}$$

It follows that we want to find a class $$n\pmod {1000}$$ such that $$n\equiv 0 \pmod 8\quad \&\quad n\equiv 7 \pmod {125}$$ The Chinese Remainder Theorem guarantees a unique solution, which is easily found to be $$\boxed {132^{1601}\equiv 632\pmod {1000}}$$

Note: with numbers as small as these, the CRT can be solved by mental arithmetic (or, at least, by simple calculations). We start with $$7$$. Clearly that isn't divisible by $$8$$ so we add $$125$$ to get $$132$$. That's divisible by $$4$$, but not by $$8$$. Now, adding $$125$$ to this would give an odd number so add $$250$$. We now get $$382$$, still no good. Adding $$250$$ again gives $$632$$ and that one works, so we are done.

If you prefer to solve it algorithmically, write the solution as $$n=7+125m$$ We want to solve $$7+125m\equiv 0\pmod 8\implies 5m\equiv 1 \pmod 8\implies m\equiv 5 \pmod 8$$ In that way we get $$n=7+5\times 125=632$$.

• You should show the work for CRT instead of pulling the answer out of a hat like magic. – Bill Dubuque Feb 2 at 19:58
• @BillDubuque It's a matter of simple mental arithmetic...easier to do than to read about. But, sure. I'll edit to include a discussion of the mechanics. – lulu Feb 2 at 20:00
• Thanks for elaborating. Magic disguised as math always irks me! – Bill Dubuque Feb 2 at 20:07
• @Alessar This is the same as your prior error. Euler/Fermat can only be used when the base is prime to the modulus. – lulu Feb 4 at 13:46
• @Alessar Nobody said the modulus had to be prime. Euler tells us that $\gcd(a,n)=1\implies a^{\varphi(n)}\equiv 1 \pmod n$. This holds for composite $n$ as well as prime. BUT you need the assumption that $\gcd (a,n)=1$. That's the mistake you keep making. – lulu Feb 4 at 15:08

I would do it in a slightly different way: split $$132$$ as a factor of $$1000$$ times a factor coprime to $$1000$$: $$132=4\cdot 33.$$

On the other hand, $$\;\varphi(1000)=\varphi(2^3)\,\varphi(5^3)=4\,(4\cdot 5^2)=400$$, so by Euler's theorem $$33^{1601}\equiv 33^{1601\bmod400}=33^1.$$

As to $$4$$, we'll use the Chinese remainder theorem, in the form:

If $$a$$ and $$b$$ are coprime, the solutions of the system of congruences $$\;\begin{cases}x\equiv\alpha\mod a,\\ x\equiv \beta\mod b,\end{cases}\;$$ are given by $$x\equiv\beta ua+\alpha vb\mod ab.$$

Now $$4^k\equiv 0\mod 8$$ for all $$k>1$$, and as $$4$$ is coprime to $$125$$, $$\;4^{1601}\equiv 4^{1601\bmod \varphi(125)}= 4^1 \mod 125$$, so that a Bézout's relation between $$8$$ and $$125$$: $$47\cdot 8-3\cdot 125=1$$ (obtained with the extended Euclidean algorithm) yields the congruence $$4^{1601}\equiv 4\cdot47\cdot8=1504\equiv 504\mod 1000,$$ and ultimately $$132^{1601}=4^{1601}33^{1601}\equiv 504\cdot 33 =500\cdot 32+500+4\cdot 33=632\mod 1000.$$

• This is a really interesting approach!!! Thanks!!! – Alessar Feb 4 at 11:13

$$2\mid 132,1000\,$$ so Euler $$\phi$$ doesn't apply. Use CRT, or simpler (a minute of mental calculation)

$$4k^{\large 1+100N}\!\bmod 1000\, =\, 8 \overbrace{\left[ \dfrac{(4k)^{\large 1+\color{#c00}{100}N}}8\bmod \color{#c00}{125}\right]}^{\qquad \large \color{#c00}{100\ \ = \ \ \phi(125)} } \!$$ = 8\underbrace{\left[ \dfrac{k}2\bmod 125\right]} =\!\!\!\!\!\!\begin{align}\overbrace{4k\!+\!500}^{\ \ \large 632\ {\rm if}\ 4k\ =\ 132}\!\!\!& {\rm if}\ \ 2\nmid k \\ 4k\qquad & {\rm if}\ \ 2\mid k \\ \phantom{.} \end{align}
by $$\,\ ab\bmod ac\, =\, a(b\bmod c)\$$ [mod distributive law] $$\$$ & $$\ \ \dfrac{k}2\equiv \dfrac{k\!+\!125}2\,\pmod{\!\!125}\ \,$$ if $$\ 2\nmid k$$

• Above we assume $\,N>0\,$ so $\,8\mid (4k)^{\large 1+100N},\,$ and $\,(k,5)=1\,$ so $\,(4k,125)=1\,$ enabling Euler $\phi,\,$ and also that $\, k\,$ Is already reduced $\!\bmod 125,\,$ i.e. $\,0\le k < 125\ \$ – Bill Dubuque Feb 2 at 21:41

let us find $$P=132^{1601-2}\pmod{125}$$

Now $$132\equiv7\pmod{125},1601-2\equiv-1\pmod{\phi(125)}$$

$$\implies P\equiv7^{-1}\pmod{125}\equiv18$$

$$\implies132^2P\equiv18\cdot132^2\pmod{125\cdot132^2}$$

$$\equiv18(100+32)(100+32)\pmod{1000}$$

$$\equiv18(200\cdot32+32^2)$$

$$\equiv18(400+24)\equiv200+432$$

Euler's theorem $$a^{\phi n} \equiv 1 \pmod n$$ only works if $$\gcd(a,n) = 1$$. Which is not the case with $$132, 1000$$

However $$1000 = 8*125$$

And CRT theorem does guarantee that if we can solve $$132^{1601}\pmod 8$$ and $$132^{1601} \pmod {125}$$ those two solutions will provide a unique solution to $$132^{1601} \pmod {1000}$$

....

We can't use Euler's Theorem for $$132^{1601} \pmod 8$$, of course, but $$132 = 33*4$$ so $$132^{1601} = 33^{1601}*4^{1601}$$ and $$8|4^k$$ for all $$k \ge 2$$ so $$132^{1601} \equiv 0 \pmod 8$$.

And for $$132^{1601} \pmod {125}$$ we CAN use Euler's theorem.

As $$125|1000$$ then $$\phi{125}|\phi{1000}$$ so $$132^{1601}\equiv 132 \pmod {125}$$. (in fact $$\phi(125) = 20$$ but... why redo work you already did.)

So we need to find the unique solution $$x \equiv 0 \pmod 8$$ and $$x \equiv 132 \pmod {125}$$. That is $$x = 8m = 132 + 125k$$ where $$0 \le m < 125$$ and $$0 \le k < 8$$.

As $$8\not \mid 132$$ we can't have $$8\mid k$$ but as $$4|132$$ we must have $$4|k$$.

In other words $$k =4$$ and $$x \equiv 132 + 500\equiv 632 \pmod {1000}$$ is the unique solution.

.....

If we want to verify this:

$$132^{1601} = 4^{1601}*33^{1601}$$ And $$33^{1601} \equiv 33\pmod{1000}$$ so

$$4^{1601}\equiv 4\pmod {125}$$ so $$4^{1601} \equiv 4,129,254,379,504,629,754,$$ or $$879 \pmod {1000}$$. But as $$8|4^{1601}$$ then $$4^{1601}\equiv 504\equiv 500 + 4 \pmod{1000}$$

So $$132^{1601} = 4^{1601}33^{1601} \equiv (500 + 4)33 \pmod{1000}$$

$$\equiv 500 + 132\equiv {1000}$$

==========

In general. If you have $$a$$ and $$n$$ and $$\gcd(a,n) = d$$ then we can set up $$n = n'D$$ where $$\gcd(n',D) = 1$$ and $$d|D$$.

Then we can solve $$a^k \equiv x\pmod n$$ by solving $$a^k \pmod{n'}$$ and $$a^k \equiv \pmod D$$.

$$a^k \pmod{n'}$$ can be solved by Euler's Theorem.

$$a$$ can also be written as $$a = a'\delta$$ where $$\gcd(a',n) = \gcd(a', d) = 1$$ and $$d|\delta$$ (note that either $$\delta$$ or $$D$$ equals $$d$$). And so we can solve $$a^k\pmod D$$ by solving $$a^k = a'^k*d^k*(\frac {\delta}d)^k = MD = Md*\frac Dd\implies$$

$$a'^k d^{k-1}(\frac {\delta}d)^k = M\frac Dd$$ . If $$D= d$$ then will mean $$a^k\equiv 0 \pmod D$$. Other wise this means $$a'^k d^{k-1} = M\frac Dd$$. Now $$\frac Dd$$ has the same prime factors of $$d$$ so this will usually mean $$a^k \equiv 0\pmod D$$ but might not if the powers of the prime factors of $$\frac Dd$$ are higher than the prime factors of $$d^{k-1}$$. But if that is the case we can reduce and and solve by Euler's theorem.

So Euler's theorem in combination with CRT will always allow us to solve these.

$$\overbrace{132^{\large 1+\color{#c00}{100}N}}^{\large X}\!\!\equiv 132\,\ \overbrace{{\rm holds} \bmod \color{#c00}{125}}^{\large\color{#c00}{100\ =\ \phi(125)}}\,$$ & $$\overbrace{\!\bmod 4}^{\large 0^K \equiv\ 0}\,$$ so mod $$500,\,$$ so it's $$\overbrace{ 132\ \ {\rm or} \underbrace{132\!+\!500}_{\large \rm must\ be \ this }\!\pmod{\!1000}}^{\large 132\ \not\equiv\ X\ \ {\rm by}\ \ N>1\ \,{\Large \Rightarrow}\,\ 8\ \mid\ 132^{\LARGE 2}\, \mid\ X\!\! }$$