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?
 A: 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$.
A: $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$
A: 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.$$
A: Like Find the last two digits of $2^{2156789}$ and Last Two Digits Problem and How to find last two digits of $2^{2016}$,
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$
A: $\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\!\! } $
