# Thread: Compute the remainder: Fermat's Little Theorem

1. ## Compute the remainder: Fermat's Little Theorem

Compute the remainder of [2^(2^17)]+1 when divided by 19.

My attempt:
If we are dividing 2^n by 19 then by Fermat's theorem and the fact that 1^x=1 for all x we have (2^18)^m is congruent to 1(mod19) so if we can find the remainder of 2^17 when divided by 18 we can write the dividend in the form 2^(18n+r)=((2^18)^m)(2^r) is congruent to 2^r where r is the remainder when 2^17 is divided by 18. So since 2^17=2^(18-1) it is congruent to 1(mod18) and r=1 hence [2^(2^17)]+1 is congruent to 2^1+1 is congruent to 3(mod19) and hence the remainder is 3.

Is my reasoning correct or incorrect?If incorrect where did I go wrong? If correct is my answer correct?

Any input would be appreciated.Thanks in advance.

2. ## Re: Compute the remainder: Fermat's Little Theorem

Originally Posted by chocaholic
Compute the remainder of [2^(2^17)]+1 when divided by 19.

My attempt:
If we are dividing 2^n by 19 then by Fermat's theorem and the fact that 1^x=1 for all x we have (2^18)^m is congruent to 1(mod19) so if we can find the remainder of 2^17 when divided by 18 we can write the dividend in the form 2^(18n+r)=((2^18)^m)(2^r) is congruent to 2^r where r is the remainder when 2^17 is divided by 18. Correct as far as here.

So since 2^17=2^(18-1) it is congruent to 1(mod18) and r=1 hence [2^(2^17)]+1 is congruent to 2^1+1 is congruent to 3(mod19) and hence the remainder is 3.
So you correctly want to find the remainder when 2^17 is divided by 18. In other words, you want to know what 2^17 is congruent to (mod 18). For that, notice that the powers of 2 (mod 18) form a recurring sequence 2, 4, 8, 16, 14, 10, 2, 4, ..., with period 6. Since 17 is congruent to 5 (mod 6), it follows that 2^17 is congruent to 2^5 (mod 18). Since 2^5 is congruent to 14, or equivalently –4 (mod 18), it then follows that $\displaystyle 2^{2^{17}}\equiv2^{–4}\pmod{19}.$

Finally, $\displaystyle 2^{-1}\equiv10\pmod{19}$, and $\displaystyle 10^2=100\equiv5\pmod{19}$. Therefore $\displaystyle 2^{-4} \equiv 10^4 = (10^2)^2 \equiv 5^2 = 25\equiv6\pmod{19},$ and so $\displaystyle 2^{2^{17}}+1\equiv7\pmod{19}.$

Problems like this are quite tricky, because you have to work to different moduli, first 19, then 18, then 6, and you have to be sure to use the correct modulus at each stage.

3. ## Re: Compute the remainder: Fermat's Little Theorem

"Since 17 is congruent to 5 (mod 6), it follows that 2^17 is congruent to 2^5 (mod 18). Since 2^5 is congruent to 14, or equivalently –4 (mod 18), it then follows that"
I understand everything except how you get from 17 is congruent to 5 (mod 6) to 2^17 is congruent to 2^5 (mod 18).Where does the 2^5 and the 18 come from I mean I know why it's 18 but how is it calculated and why is the period used? I don't think I've seen this aproach before. Is it ok to say instead that 2^4=16 is congruent to -2(mod18) and 2^17=2^(4*4+1)=2*(2^4)^4 is congruent to 2*(-2)^4 is congruent to 2*16 is congruent to 32 is congruent to -4(mod18) then 2^17+1 is congruent to 2^(-4)+1 is congruent to [(2^4)^-1]+1 is congruent to (16^(-1))+1 is congruent to (-3^-1)+1 is congruent to 6+1 is congruent to 7(mod19) hence the remainder is 7

4. ## Re: Compute the remainder: Fermat's Little Theorem

Originally Posted by chocaholic
Is it ok to say instead that 2^4=16 is congruent to -2(mod18) and 2^17=2^(4*4+1)=2*(2^4)^4 is congruent to 2*(-2)^4 is congruent to 2*16 is congruent to 32 is congruent to -4(mod18) then 2^17+1 is congruent to 2^(-4)+1 is congruent to [(2^4)^-1]+1 is congruent to (16^(-1))+1 is congruent to (-3^-1)+1 is congruent to 6+1 is congruent to 7(mod19) hence the remainder is 7
Yes, that's fine, apart from one small (but confusing) detail. That 2^17 in red should be 2^(2^17).

5. ## Re: Compute the remainder: Fermat's Little Theorem

O yeah sorry about that.Didn't preview post.Thank you for all the help.