Results 1 to 4 of 4

Math Help - why is this argument about carmichael numbers true

  1. #1
    Banned
    Joined
    Nov 2008
    Posts
    63

    why is this argument about carmichael numbers true

    to find all the carmichael numbers N  < 10^{6} , we only need to test composite N with primes a from 2 to 19 , and see if they satisfy:

     (a,N)=1  \ \ s.t. \ \ a^{N-1}=1 \ \ mod \ \ N
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by silversand View Post
    to find all the carmichael numbers N  < 10^{6} , we only need to test composite N with primes a from 2 to 19 , and see if they satisfy:

     (a,N)=1  \ \ s.t. \ \ a^{N-1}=1 \ \ mod \ \ N
    If prime numbers a satisfy a^{N-1}\equiv 1(\bmod N) then any number (n,N)=1 would have to satisfy n^{N-1}\equiv 1(\bmod N). This is because if a,b satisfy this congruence then (ab)^{N-1}\equiv a^{N-1}b^{N-1}\equiv 1(\bmod N). Therefore, there products of all these primes would satisfy the congruence. But since n can be realized as a product of primes it would mean that it itself satisfies the congruence.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by silversand View Post
    to find all the carmichael numbers N  < 10^{6} , we only need to test composite N with primes a from 2 to 19 , and see if they satisfy:

     (a,N)=1 \ \ s.t. \ \ a^{N-1}=1 \ \ mod \ \ N
    You will also find primes as pointed out by ThePerfectHacker, but
    how will you distinguish these Carmichael Numbers from primes:
    A few Carmichael Numbers < 10^6 with smallest factor > 19
    252601 = 41 * 61 * 101
    294409 = 37 * 73 * 109
    399001 = 31 * 61 * 211
    410041 = 41 * 73 * 137
    488881 = 37 * 73 * 181
    512461 = 31 * 61 * 271

    .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Nov 2008
    Posts
    63

    no clear

    ThePerfectHacker's answer is not clear.

    i cant get why we only need to test primes a from 2 to 19 to find all Carmichael < 10^6
    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, 07:28 PM
  2. two definitions of Carmichael numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 27th 2009, 10:18 AM
  3. carmichael numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 9th 2009, 06:52 PM
  4. Carmichael numbers
    Posted in the Number Theory Forum
    Replies: 17
    Last Post: April 21st 2009, 09:09 PM
  5. Carmichael Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 25th 2007, 05:09 AM

Search Tags


/mathhelpforum @mathhelpforum