Results 1 to 7 of 7

Math Help - Fermats Little Theorem

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    54

    Fermats Little Theorem

    Let n be a positive integer and suppose that p=2k+1 is an odd prime divisor of n^2+1.

    CONG implies congruent to.

    1)Show that n^2 CONG -1 mod p

    I've done this by saying, because p|n^2+1 --> n^2+1 CONG mod p hence we arrive at the desired result by moving 1.

    2) Using Fermat Little Theorem show that (n^2)^k CONG 1 mod p

    I've done this by using the standard version of Fermat's little Theorem,
    i.e a^p-1 CONG 1 mod p

    Using p=2k+1 --> p-1=2k and setting a=n

    We get, n^(2k) CONG 1 mod p and fixing up n^2k to (n^2)^k CONG 1 mod p we arrive at the desired result.

    3)Deduce from the preceding two parts, show that p CONG 1 mod 4.

    Now here is where I'm in doubt, I'm confident with my previous answers(I don't have the solutions to these btw).


    Setting p=4, causes problems with p=2k+1 --> 3=2k .. k ?

    So this is where I need your guidance.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Why would you set p=4? You are given that p is an odd prime. Specifically, p is odd so either p \equiv 1 \ mod 4 or p \equiv 3 \ mod 4

    Assume by contradiction that p \equiv \ 3 mod 4 and proceed to use the previous results.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    To conclude the first two parts, you have n^2\equiv-1\bmod p and n^{p-1}\equiv1\bmod p, where p-1=2k. Notice that n^{p-1}=(n^2)^k\equiv(-1)^k\bmod p. Now consider what happens if k is odd.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Sep 2010
    Posts
    54
    How do you know that p cong 1 mod 4 or p cong 3 mod 4 ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    p is odd. Can an odd number be congruent to 2 or 0 mod 4?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Sep 2010
    Posts
    54
    Nope? Because it's not divisible by 2 or 4 ?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Prove it. It should take no more than 2 lines.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 13th 2011, 12:32 PM
  2. Fermats last theorem solution, try 2.
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 14th 2010, 11:24 PM
  3. large exponents with fermats little theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 24th 2010, 07:53 PM
  4. Prime problem, Fermats little theorem?
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: November 5th 2009, 08:00 AM
  5. Fermats Last Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 18th 2008, 07:23 AM

Search Tags


/mathhelpforum @mathhelpforum