1

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

Michael
  • 397

1 Answers1

1

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

André Nicolas
  • 507,029
  • Thanks! Are you also able to help explain my question for 2? – Michael Apr 09 '13 at 00:11
  • @Michael: I added an explanation for the second. It is more speculative. – André Nicolas Apr 09 '13 at 00:12
  • a better question would be why is 2^(189)2^14 mod 19 = 2^14 mod18 – Michael Apr 09 '13 at 00: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 09 '13 at 00:44
  • The typeset for the second question is find rE (Z small 19) such that r ≡ 2^68 mod 19 – Michael Apr 09 '13 at 00:51
  • I will type an addendum to answer, solving the problem. Then perhaps you can see what's going on, – André Nicolas Apr 09 '13 at 00:55
  • I have had some negative experiences with chat. Perhaps you will find the added calculation useful. If you have questions, please leave a message and I can answer them. – André Nicolas Apr 09 '13 at 01:07
  • one last question, how did you get 6mod 19? I don't understand how you went from 2^3≡8(mod19) to 2^14≡44≡6(mod19) thanks! – Michael Apr 09 '13 at 01:31
  • In several steps, which are all laid out in detail in the answer. All congruences are mod $19$. We have $2^3\equiv 8$, so $2^6\equiv 8^2=64\equiv 11$, and so on as written out above. We used a more or less ad hoc method. There is a systematic way of doing it called the binary method for exponentiation, which is of significant practical importance. Maybe I should add it. – André Nicolas Apr 09 '13 at 01:43