# Simpify large number using congruences

Using the language of congruences, find the remainder when $22^{104}$ is divided by $18$.

My attempt:

$22 \equiv 4(mod 18)$, this means $22^{104} \equiv 4^{104}(mod18)$

I am confused about what to do after this step.

Edit:

$4^{1} \equiv 4(mod18)$

$4^{2} \equiv 16(mod18)$

$4^{3} \equiv 10(mod18)$

$4^{4} \equiv 4(mod18)$

So this means that the congruence will repeat every 3 terms. $104 = 2 + 34 *3$

$4^2 \equiv 16 (mod 18)$

Is this the correct way to do the problem?

• $4^{3*34+2} = 10^34*4^2$ since $4^3=10 mod 18$ and continue from there, there are many ways, you can do whatever you like, just start decomposition the power.
– Rab
Apr 19, 2017 at 21:27

Your way is fine. Nothing wrong with it. Sometimes there are little short cuts like Fermat's Little Theorem or Euler's Theorem, but brute forcing it is onyl bad because of computation and time. Another way: Note that $4^2\equiv 16\equiv-2\pmod{18}$ so that $4^{104}\equiv (4^{2})^{52}\equiv(-2)^{52}\equiv (2^{4})^{13}\equiv(-2)^{13}\equiv (2^{4})^3\cdot(-2)\equiv8\cdot2\equiv-2\equiv16$

• I agree with anonymaker. What if a similar problem appeared in a future exam and you are working with larger numbers? Then Fermat's Little Theorem would really come in handy. Apr 19, 2017 at 22:32

Let $n$ be a natural number, with $u_n=22^n$

For $n=0$ : $u_n= 22^0 \equiv 1[18]$

For $n=1$ : $u_n= 22^1 = 1\cdot18 + 4 \equiv 4[18]$

For $n=2$ : $u_n= 22^2 \equiv 16[18]$

For $n=3$ : $u_n= 22^3 \equiv 10[18]$

For $n=4$ : $u_n= 22^4 \equiv 4[18]$

By This way, we have constructed a periodic sequence, with $p=3$

So $22^{3k+1} \equiv 4[18]$

$104 = 34\cdot3+2$

So $22^{104} = 22^{34\cdot3+2} = 22^{(34\cdot3+1)+1} = 22^{(34\cdot3+1)}\cdot22$

$22^{104} \equiv 22^{(34\cdot3+1)}\cdot22[18] \Leftrightarrow 22^{104} \equiv 4\cdot4[18] \Leftrightarrow 22^{104} \equiv 16[18]$