how to calculate remainder of large numbers? (no calculator)

Question

How do I calculate the remainder of $30^{29} \pmod {51}$?

I cant use Fermat's little theorem since $51$ is not a prime number.

Answer 1

As $(30,51)=3$

let's find $30^{29-1}\pmod{51/3}$

Now $30\equiv13\pmod{17}$

$30^2\equiv13^2\equiv-1$

$30^{28}=(30^2)^{14}\equiv(-1)^{14}\pmod{17}$

$30\cdot30^{28}\equiv1\cdot30\pmod{17\cdot30}$

Answer 2

You could use the Chinese remainder theorem.

$x\equiv30^{29}\bmod 51\implies x\equiv0\bmod3$ and $x\equiv13^{13}\bmod 17$.

Answer 3

You could do any one of the following:

• Chinese remainder theorem applied to the mod by factors of 51 ( 3 and 17)
• Use negative equivalents like $30\equiv -21\pmod {51}$ , and $29\equiv -3\pmod {32}$
• Calculate by repeated squaring and the fact $(30^7)^4\cdot 30=30^{29}$

There are tons of methods and other things you can use.

Answer 4

Put $\,a,b = 3,10\,$ below, using $\!\bmod c\!=\!17\!:\ \color{#c00}{(ab)^4} =30^4\equiv ((-4)^2)^2\equiv (-1)^2\color{#c00}{\equiv 1}$

$\ \color{#c00}{(ab)^4\equiv 1}\pmod{\!c}\,\Rightarrow\,(ab)^{1+4n}\bmod ac\overset{\rm\color{#0a0}{DL}} = a(b \color{#c00}{(ab)}^{\color{#c00}4\:\!n}\!\bmod c)= a(b)$

where we've factored out $\,a\,$ via $\, ad\bmod ac = a(d\bmod c) = $ $\rm\color{#0a0}{DL} = $ Mod Distributive Law