Results 1 to 4 of 4

Math Help - Find x in the congruence using Fermat's Little Theorem

  1. #1
    Junior Member
    Joined
    Jan 2009
    Posts
    27

    Find x in the congruence using Fermat's Little Theorem

    It's supposed to be 2^(11), but don't know how to do it
    2^11 \equiv xmod3 such that 0<=x<=2
    Find x using Fermat's Little Theorem.

    Here is what I have done:
    Since 3 is prime, it follows that (2^11)^2 \equiv 1mod3 by FLT and since (2^11,3)=1.
    So, multiply both sides by 2^11 we get
    (2^11)^2 \equiv 2^11 * xmod3
    1 \equiv 2^11 * xmod3

    It is here I'm not sure what to do since not sure how to get something 0<=x<=2, or how to isolate the x really.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Oct 2008
    From
    Guernsey
    Posts
    69
    2^{3-1} = 2^2 = 1 \pmod{3} by FLT

    So 2^{11} = 2^{10+1} = (2^2)^5 \times 2^1 = 1^5 \times 2 = 2 \pmod{3}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    FLT: If \gcd (a,p) = 1, then a^{p-1} \equiv 1 \ (\text{mod } p)

    So: \gcd (2,3) = 1 \ \Rightarrow \ 2^{2} \equiv 1 \ (\text{mod } 3)

    Raise both sides to the power of 5 (to get it as close to 11 as possible): \left(2^2\right)^{{\color{red}5}} \equiv 1^{{\color{red}5}} \ (\text{mod } 3)

    So we have: 2^{10} \equiv 1 \ (\text{mod } 3)

    Can you finish off?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jan 2009
    Posts
    27
    I see it now
    Thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 10th 2011, 09:51 AM
  2. Replies: 4
    Last Post: December 13th 2009, 06:52 AM
  3. Replies: 1
    Last Post: March 9th 2009, 01:51 PM
  4. Congruence Fermat's little theorem help
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: June 2nd 2008, 02:49 PM
  5. Find remainder with congruence theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 6th 2008, 03:51 PM

Search Tags


/mathhelpforum @mathhelpforum