# Equivalent modulos

In my course notes I came onto two examples for finding remainders of huge numbers with fermat's little theorem and need some helping analyzing them.

1) Find the remainder when 5^183 is divided by 11. I know that 5^10 ≡ 1 mod(11) so (5^(10*18)) = 5^180*5^3. That ≡ 1(5^3)mod11 but then the examples says 3*5 mod 11 ≡ 4 mod 11. How did 125 mod11 turn to 3*5 mod 11?

2) why is 2^(18*9)*2^14 mod 19 = 2^14 mod18

-

For the first question, $5^3=5^2\cdot 5$. But $5^2\equiv 3$.

For the second, unless there is a typo, I suspect the question has shape find the remainder when $a^{2^{68}}$ is divided by $19$. For the calculation, if $a$ is not divisible by $19$, we want to use the fact that $a^{18}\equiv 1\pmod{19}$. So we want to begin by calculating the remainder when $2^{68}$ is divided by $18$. Also, it looks as though the thing you call $68\ast 3$ is meant to be $18\ast 3$.

If the problem is to find the ramainder when $2^{68}$ is divided by $19$, note that by Fermat's Theorem we have $2^{18}\equiv 1\pmod{19}$. Note that $68=3\cdot 18+14$. So $2^{68}=2^{18\cdot 3}2^{14}=(2^{18})^3\cdot 2^{14}\equiv 2^{14}\pmod{19}$.

So now we need to calculate the remainder when $2^{14}$ is divided by $19$. We have $2^{3}\equiv 8\pmod{19}$, so $2^6\equiv 64\equiv 7\pmod{19}$. It follows that $2^{12}\equiv 49\equiv 11\pmod{19}$, and therefore $2^{14}\equiv 44\equiv 6\pmod{19}$. There are a number of other ways to do the calculation.

Remark: There is a more systematic way, called the binary method for exponentiation, which I recommend you look up. All congruences are modulo $19$. We have $2^2\equiv 4$, so $2^4\equiv 16\equiv -3$, so $2^8\equiv 9$, so $2^{12}= 2^8\cdot 2^4\equiv -27\equiv 11$, so $2^{14}=2^{12}\cdot 2^2\equiv 11\cdot 4\equiv 6$.

-
Thanks! Are you also able to help explain my question for 2? – Michael Apr 9 '13 at 0:11
@Michael: I added an explanation for the second. It is more speculative. – André Nicolas Apr 9 '13 at 0:12
a better question would be why is 2^(18*9)*2^14 mod 19 = 2^14 mod18 – Michael Apr 9 '13 at 0:26
@Michael: what was going on in the first question was clear. In order to be sure of what was going on in the second, I would need to see the problem exactly as it was posed, more or less properly typeset. – André Nicolas Apr 9 '13 at 0:44
The typeset for the second question is find rE (Z small 19) such that r ≡ 2^68 mod 19 – Michael Apr 9 '13 at 0:51