Results 1 to 3 of 3

Math Help - two definitions of Carmichael numbers

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    9

    two definitions of Carmichael numbers

    I am looking up Carmichael numbers on the internet, and about half define it one way, the other half define it the other way. Both definitions follow:

    (N is composite throughout discussions below)

    Def 1: N is a Carmichael number iff for all integers a, a^n = a (mod n).

    Def 2: N is a Car. num iff for all integers a coprime to n, a^(n-1) = 1(mod n)


    I can see how Def 1 implies Def 2, but I don't get how Def 2 automatically gives Def 1. That is, I don't know why this fact is true...

    Fact: If gcd(a,N) > 1, then a^N = a (mod N)


    Can anyone help me?
    Last edited by kobulingam; September 27th 2009 at 11:16 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    Modular Inverses

    It has to do with the fact that a^{-1} does not exist unless a and n are coprime. Consider Def 1: a^n\equiv a (\bmod n). That means that a^{n-1}\equiv a^na^{-1}\equiv aa^{-1}\equiv 1 (\bmod n). This algebraic step can only be done if you require that a and n are coprime.

    So technically Def 1 does NOT imply Def 2 directly. The correct statement is actually: Def 1 \to (Def 2 OR gcd(a,n)\neq 1)

    Consider a concrete example. 561=3*11*17 is a Carmichael number:

    2^{561}\equiv 2 (\bmod 561) and 2^{560}\equiv 1 (\bmod 561) as the theory suggests.

    3^{561}\equiv 3 (\bmod 561) but 3^{560}\equiv 375 (\bmod 561) because 3 and 561 are not coprime.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2009
    Posts
    9
    Def 1 does imply Def 2 direcly because Def 2 includes the gcd - 1 stipulation. Def2 has to imply Def 1, otherwise these woudlnt be used as alternate definitions.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof with carmichael numbers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 15th 2009, 08:28 PM
  2. why is this argument about carmichael numbers true
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 11th 2009, 04:00 AM
  3. carmichael numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 9th 2009, 07:52 PM
  4. Carmichael numbers
    Posted in the Number Theory Forum
    Replies: 17
    Last Post: April 21st 2009, 10:09 PM
  5. Carmichael Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 25th 2007, 06:09 AM

Search Tags


/mathhelpforum @mathhelpforum