Find the last three digits of $17^{102}$.
That is we have to find out $17^{102}\equiv ?\pmod{1000}$.
Now if we solve it through general congruence relation , then the process becomes very difficult , computational and laborious. Again from Euler's theorem , $$17^{\phi(1000)}\equiv 1 \pmod{1000}.$$ But $\phi(1000)=400(>102)$. So it can't help me.
Does there any simplest way to solve this congruence relation easily ?
On
A good approach is to use the Chinese Remainder Theorem. Instead of looking at $17^{102}$ modulo $1000$, we'll look at it modulo $2^3 = 8$ and $5^3 = 125$.
Modulo $8$, this is very simple, since $17 \equiv 1 \bmod 8$. Modulo $125$, we have $\phi(125) = 100$, so $17^{102} \equiv 17^2 \equiv 39 \bmod 125$.
Now, to raise these solutions back up to a single solution modulo $1000$, we consider the integers $39 + 125s$ and check which ones are congruent to $1$ modulo $8$. We get that $38 + 125 s \equiv 30 + 125s \equiv 5(6+s) \equiv 0 \bmod 8$. So $s \equiv 2 \bmod 8$. Therefore those integers that are congruent to $39 \bmod 125$ and congruent to $1 \bmod 8$ are of the form $39 + 125(2+8s') = 289 + 1000s'$. So $17^{102} \equiv 289 \bmod 1000.$
On
$102$ in binary is $1100110$. Denoting equality mod $1000$ by $\equiv$ one finds by successively computing the last three digits of the squares: $$17^2\equiv289, \ 17^4\equiv521, \ 17^8\equiv441, \ 17^{16}=481, \ 17^{32}\equiv361, \ 17^{64}\equiv321\ .$$ It follows that $$17^{102}\equiv17^2\cdot17^4\cdot 17^{32}\cdot 17^{64}\equiv 289\cdot 521\cdot 361\cdot 321\equiv289\ ,$$ where at each stage in the last multiplication we just compute only the last three digits.
On
The units digit of $17^1$ is $7$.
The units digit of $17^2$ is $9$ ($7 \times 7 = 49$).
The units digit of $17^3$ is $3$ ($7 \times 9 = 63$).
The units digit of $17^4$ is $1$ ($7 \times 3 = 21$).
Calculating,
$\; 17^4 = 289 \cdot 289 = (280+9)^2 = 280^2 + 18 \cdot 280 + 81 \equiv$
$\quad\quad\quad 400 + 800 + 600 + 640 + 81 \equiv 521 \pmod{1000}$
Calculating,
$\; 17^{102} \equiv 17^2 \cdot 521^{25} \equiv 289 \cdot (1 + 520)^{25} \equiv 289 \cdot (1 + 2^3 \cdot 5^1 \cdot 13^1)^{25} \equiv$
$\quad\quad\quad\; \, \; 289 \; \bigr(1 + \binom{25}{1}\,2^3 \cdot 5^1 \cdot 13^1 + \binom{25}{2}\,2^6 \cdot 5^2 \cdot 13^2 + 0\bigr) \equiv$
$\quad\quad\quad\; \, \; 289 \; \bigr(1 + 0 + 0 + 0 \bigr) \equiv 289 \pmod{1000}$
You want to use Carmichael's theorem to see that $17^{100} \equiv 1 \mod 1000$.
Carmichael's theorem states that if $a$ and $n$ are coprime, then $a^{\lambda(n)} \equiv 1 \mod n$, where $\lambda(n)$ is the Carmichael function.
$\lambda(n)$ can be calculated recursively for $n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$ as $\lambda(n) = LCM( \lambda(p_1^{a_1}), \lambda(p_2^{a_2}), \dots, \lambda(p_k^{a_k})) $, where $\lambda(n) = \phi(n)$ for $n$ a power of an odd prime or $2,4$ and $\lambda(n) = \frac{1}{2} \phi(n)$ for $n = 2^k$ for $k > 2$.
For $n = 1000 = 2^3 5^3$, we get that $\lambda(n) = LCM(\frac{1}{2} \phi(2^3), \phi(5^3) ) = LCM(2,100) = 100$.