2
$\begingroup$

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$
  • $\begingroup$ Thanks for the help everyone, I finally figured it out. The key was just knowing to divide by 16 (i.e. 2^4). $\endgroup$ – user210783 Jan 27 '15 at 18:59
1
$\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$
1
$\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$
1
$\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$
-1
$\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$
  • $\begingroup$ This is not at all sufficient as a proof, merely strong anecdotal evidence that it is true. $\endgroup$ – siegehalver Jun 11 '17 at 20:47

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.