Results 1 to 5 of 5

Math Help - Fermat's Little Theorem Help [again]

  1. #1
    Junior Member
    Joined
    Oct 2008
    Posts
    51

    Fermat's Little Theorem Help [again]

    Hi all,

    The question concerns que same subject as my previous post in this section, but I still didn't figure it out:

    Let p be a prime number and a be an integer such that p does not divide a. Show that if p > 2 then a^{\frac{p-1}{2}} \equiv 1 \ \ (mod \ p) or a^{\frac{p-1}{2}} \equiv -1 \ \ (mod \ p).

    Any tips or approach suggestions will be useful.

    Thanks in advance,
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by Rafael Almeida View Post
    Hi all,

    The question concerns que same subject as my previous post in this section, but I still didn't figure it out:

    Let p be a prime number and a be an integer such that p does not divide a. Show that if p > 2 then a^{\frac{p-1}{2}} \equiv 1 \ \ (mod \ p) or a^{\frac{p-1}{2}} \equiv -1 \ \ (mod \ p).

    Any tips or approach suggestions will be useful.

    Thanks in advance,
    This is because \left(a^{\frac{p-1}{2}}\right)^2\equiv a^{p-1}\equiv 1\,({\rm mod }\,p) (by Fermat's little theorem) and \pm 1 are the only roots of the polynomial X^2-1 on the field \mathbb{Z}_p (in a field, a polynomial of degree n has at most n roots). Or you can say: if x^2\equiv 1\,({\rm mod}\,p), then p|x^2-1=(x-1)(x+1), so that either p|x+1 (i.e. x\equiv -1\,({\rm mod}\, p)) or p|x-1 (i.e. x\equiv 1\,({\rm mod}\, p)) because p is prime.
    Last edited by Laurent; October 27th 2008 at 12:16 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Here is a related proof: a^{p-1} \equiv 1 \implies a^{p-1} - 1\equiv 0 \implies \left( a^{(p-1)/2} - 1\right)\left( a^{(p-1)/2}+1\right) \equiv 0 (\bmod p).
    From here we see a^{(p-1)/2}\equiv \pm 1(\bmod p).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by ThePerfectHacker View Post
    Here is a related proof: a^{p-1} \equiv 1 \implies a^{p-1} - 1\equiv 0 \implies \left( a^{(p-1)/2} - 1\right)\left( a^{(p-1)/2}+1\right) \equiv 0 (\bmod p).
    From here we see a^{(p-1)/2}\equiv \pm 1(\bmod p).
    And why is this last implication correct? This is because \mathbb{Z}_p is a field (and hence an integral domain). Or because of the other elementary argument I gave about divisibility.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Laurent View Post
    And why is this last implication correct? This is because \mathbb{Z}_p is a field (and hence an integral domain). Or because of the other elementary argument I gave about divisibility.
    Yes, I should have been more explicity why the last line holds. By the way, when I talk about \mathbb{Z}_p instead of saying "it is a field and hence and integral domain" I perfer to say "it is an integral domain and hence a field". Why? Because there is a theorem, which I am sure you know but if not it is a nice result, that says if D is a finite integral domain then D is a field. Because I like this result I like to switch around the order of my statement. But whatever, I am getting off topic.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fermatís Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 27th 2011, 06:52 PM
  2. Replies: 4
    Last Post: January 10th 2011, 08:51 AM
  3. Fermat's Last Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 18th 2010, 01:33 AM
  4. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 19th 2009, 09:47 PM
  5. Fermat's little theorem
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 17th 2009, 06:28 AM

Search Tags


/mathhelpforum @mathhelpforum