3
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You should show the work for CRT instead of pulling the answer out of a hat like magic. $\endgroup$ – Bill Dubuque Feb 2 at 19:58
  • 1
    $\begingroup$ @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. $\endgroup$ – lulu Feb 2 at 20:00
  • 1
    $\begingroup$ Thanks for elaborating. Magic disguised as math always irks me! $\endgroup$ – Bill Dubuque Feb 2 at 20:07
  • 1
    $\begingroup$ @Alessar This is the same as your prior error. Euler/Fermat can only be used when the base is prime to the modulus. $\endgroup$ – lulu Feb 4 at 13:46
  • 1
    $\begingroup$ @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. $\endgroup$ – lulu Feb 4 at 15:08
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is a really interesting approach!!! Thanks!!! $\endgroup$ – Alessar Feb 4 at 11:13
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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\ \ $ $\endgroup$ – Bill Dubuque Feb 2 at 21:41
1
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

$\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\!\! } $

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.