1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Easy (but not to me) Modern Algebra Proof

  1. Mar 24, 2009 #1
    Hi everyone, I am hoping that someone can please give me some help with this homework problem.

    1. The problem statement, all variables and given/known data
    In n>2 is a Carmichael number and p/n is an odd prime, then show that gcd(p-1,n-1) >1


    2. Relevant equations



    3. The attempt at a solution
    This is what I did, but I am not sure if its right:

    Choose an a coprime to n and that does not divide p (2 will work because p is prime and carmichael numbers are odd).

    Then ap-1 [tex]\equiv[/tex]1 (mod p) (by Fermats Little Theorem) and an-1 [tex]\equiv[/tex]1 (mod n) by definition. This implies that an-1 [tex]\equiv[/tex]1 (mod p) because p/n.

    So to finish can I just say that because ap-1 [tex]\equiv[/tex]1 (mod p) and an-1 [tex]\equiv[/tex]1 (mod p) this implies that ap-1^some integer=an-1, and so (p-1)/(n-1)?


    Any help would be greatly appreciated. Thanks guys.
     
  2. jcsd
  3. Mar 24, 2009 #2
    How about this revised version, is this right?

    Choose an a coprime to n and that does not divide p (2 will work because p is prime and carmichael numbers are odd).

    Then by FLT, ap-1[tex]\equiv[/tex]1 (mod p), and by definition an-1[tex]\equiv[/tex]1 (mod n). Then because p/n, an-1[tex]\equiv[/tex]1 (mod p). Now this implies that the order of a mod p (which cannot be 1 because that would mean a is 1 and 1 isnt coprime to n and does divide p) divides both n-1 and p-1. Thus the gcd(n-1,p-1) is greater than 1.
     
  4. Mar 24, 2009 #3

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I haven't really had a lot of time to think about this, but stop writing p/n instead of p|n. (i.e. p divides n). It confused me right off the bat, and may confuse other people. Who might know number theory a lot better than I do.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Easy (but not to me) Modern Algebra Proof
Loading...