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.