Results 1 to 5 of 5

Math Help - Compute the remainder: Fermat's Little Theorem

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    54

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7

    Re: Compute the remainder: Fermat's Little Theorem

    Quote Originally Posted by chocaholic View Post
    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 2^{2^{17}}\equiv2^{4}\pmod{19}.

    Finally, 2^{-1}\equiv10\pmod{19}, and 10^2=100\equiv5\pmod{19}. Therefore 2^{-4} \equiv 10^4 = (10^2)^2 \equiv 5^2 = 25\equiv6\pmod{19}, and so 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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2010
    Posts
    54

    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7

    Re: Compute the remainder: Fermat's Little Theorem

    Quote Originally Posted by chocaholic View Post
    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).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2010
    Posts
    54

    Re: Compute the remainder: Fermat's Little Theorem

    O yeah sorry about that.Didn't preview post.Thank you for all the help.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: January 13th 2012, 10:10 AM
  2. Replies: 1
    Last Post: December 21st 2011, 03:24 AM
  3. Replies: 4
    Last Post: January 10th 2011, 08:51 AM
  4. Fermat's Theorem
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: April 21st 2009, 04:44 PM
  5. Fermat's little theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 23rd 2008, 06:37 PM

/mathhelpforum @mathhelpforum