I am trying to calculate $10^{130} \bmod 48$ but I need to use Euler's theorem in the process.
I noticed that 48 and 10 are not coprime so I couldn't directly apply Euler's theorem. I tried breaking it down into $5^{130}2^{130} \bmod 48$ and I was sucessfully able to get rid of the 5 using Euler's theorem but now I'm stuck with $2^{130} \bmod 48$. $2^{130}$ is still a large number and unfortunately 2 and 48 are not coprime.
Could someone lead me in the right direction regarding how would I proceed from here?
$\endgroup$ 14 Answers
$\begingroup$$$5^{130}2^{130}\equiv a\pmod {48}\iff\begin{cases}5^{130}2^{130}\equiv a\pmod {16}\\5^{130}2^{130}\equiv a\pmod {3}\end{cases}\iff \begin{cases}a\equiv 0\pmod {16}\\a\equiv (-1)^{130}(-1)^{130}\equiv 1\pmod 3\end{cases}$$
$$\iff a\equiv 3\cdot 0\cdot (3^{-1}\mod {16})+16\cdot 1\cdot (16^{-1}\mod 3)\pmod {48}$$
$$\iff a\equiv 16\pmod {48}$$
$\endgroup$ $\begingroup$Calculate $\mod 48$ using the Chinese Remainder Theorem. Or, informally: Clearly $2^{130}$ is divisible by $16$ so modulo $48$ this is one of $0, 16, 32$, which one of the three it is depends on what it is modulo $3$.
$\endgroup$ $\begingroup$As $(10^{n+4},48)=2^4$ for integer $n\ge0$
Let use find $10^n\pmod3$
As $10\equiv1\pmod3,10^n\equiv1$
Now as $a\equiv b\pmod m\implies a\cdot c\equiv b\cdot c\pmod{m\cdot c},$
$\implies10^n\cdot10^4\equiv1\cdot10^4\pmod{3\cdot10^4}$
As $16|10^4\iff48|3\cdot10^4,$
$\implies10^{n+4}\equiv10^4\pmod{48}$
Now $10^2\equiv4\pmod{48}\implies10^4=(10^2)^2\equiv4^2\pmod{48}$
$\endgroup$ $\begingroup$In this case it pays to try the dumb strategy first: by calculating a few powers of 10, you quickly find that for all $n \geq4:$ $10^n = 16 \bmod 48$. Hence $10^{130} = 16 \bmod 48$.
$\endgroup$ 1
