Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.