Euler's theorem (modular arithmetic) for non-coprime integers

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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