Results 1 to 12 of 12

Math Help - Prove n is prime (linked to Fermats little theorem)

  1. #1
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722

    Prove n is prime (linked to Fermats little theorem)

    Show that n is prime iff a^{n-1} 1( \textrm{mod} n) for 1 \leq a \leq n-1.

    => Fermats little theorem.

    <=

    Perhaps show that \phi(n) = n-1 but if this is the case I would need a way to start.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Apr 2010
    Posts
    78
    Quote Originally Posted by Deadstar View Post
    Show that n is prime iff a^{n-1} 1( \textrm{mod} n) for 1 \leq a \leq n-1.

    => Fermats little theorem.

    <=

    Perhaps show that \phi(n) = n-1 but if this is the case I would need a way to start.
    <= FALSE. Smallest counterexample: 561. Such numbers are called Carmichael numbers.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by FancyMouse View Post
    <= FALSE. Smallest counterexample: 561. Such numbers are called Carmichael numbers.
    Well well I now hate my lecturer for making me spend all night on a trick question...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by FancyMouse View Post
    <= FALSE. Smallest counterexample: 561. Such numbers are called Carmichael numbers.
    Hold on did you notice the 1 \leq a \leq n-1 condition? Does it still not hold.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by FancyMouse View Post
    <= FALSE. Smallest counterexample: 561. Such numbers are called Carmichael numbers.
    I'm pretty sure this is wrong now.

    3^{560} is not equivalent to 1 mod 561 for example. It does not hold for all a \in [1 \dots n-1]
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Generally,
    \Rightarrow if p is prime, then a^{p - 1} \equiv 1 \pmod{p} for any a such as \gcd{(a, p)} = 1.

    \Rightarrow if a^{p - 1} \equiv 1 \pmod{p} for any a such as \gcd{(a, p)} = 1, then p is likely to be prime (Carmichael numbers are the only numbers that do not satisfy the statement, they are relatively rare but their existence invalidates the statement).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by Bacterius View Post
    Generally,
    \Rightarrow if p is prime, then a^{p - 1} \equiv 1 \pmod{p} for any a such as \gcd{(a, p)} = 1.

    \Rightarrow if a^{p - 1} \equiv 1 \pmod{p} for any a such as \gcd{(a, p)} = 1, then p is likely to be prime (Carmichael numbers are the only numbers that do not satisfy the statement, they are relatively rare but their existence invalidates the statement).
    Right. I'm kinda getting a bit mixed up on whether my question is actually true (i.e, is it an 'iff' question or just an 'if' question)...

    The counter example given was 561 but the problem as I understand it is...

    If a^{n-1} \equiv 1 \textrm{ mod } n for all 1 \leq a \leq n-1, then n is prime.

    But this is not true for 561.

    3^{560} = 375 mod 561. Hence 561 does not satisfy the above... What am I missing here? It holds true for may primes that I have tested using Maple leading me to believe that the part I'm stuck on can be proved.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    The original statement is wrong. It is not an "iff" condition because you found a counter-example with 561.

    The statement is valid if and only if n is a prime OR a Carmichael number.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by Bacterius View Post
    The original statement is wrong. It is not an "iff" condition because you found a counter-example with 561.

    The statement is valid if and only if n is a prime OR a Carmichael number.


    Ok look. I get what iff means but 561 is not a counter example.

    For 561 to be a counter example then for every a \in [1 \dots 560], a^{560} \equiv 1 mod 561.

    But after running it through in Maple you can show that for many values for a
    a^{560}\neq 1 mod 561. (don't know the Latex for not equivalent)

    Hence 561 is not prime.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Apr 2010
    Posts
    78
    Quote Originally Posted by Deadstar View Post
    I'm pretty sure this is wrong now.

    3^{560} is not equivalent to 1 mod 561 for example. It does not hold for all a \in [1 \dots n-1]
    So then everything in [1,n-1] is relatively prime to n indicates that n does not have a divisor there. So OP's statement is true in that sense, which is trivial to prove, but way less meaningful than the existence of Carmichael numbers.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Ok folks, I'm back.

    Hopefully with an understanding.

    It seems perhaps the proof wasn't so complicated as I first thought...

    => Fermat's little theorem. (since all a in this example are coprime to p if p is prime)

    <= If a^{n-1} \equiv 1 \textrm{ (mod } p) \, \textrm{for } 1 \leq a < n, all a are coprime to p, hence p has no divisors and so is prime.

    Is that all it is?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Deadstar View Post
    (don't know the Latex for not equivalent)
    \not\equiv
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: December 8th 2011, 08:42 PM
  2. Replies: 4
    Last Post: January 13th 2011, 12:32 PM
  3. Fermats Little Theorem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: September 25th 2010, 04:18 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