Results 1 to 3 of 3

Math Help - Question about Carmichael number

  1. #1
    Banned
    Joined
    Nov 2008
    Posts
    63

    Question about Carmichael number

    Definition:
    An absolute Fermat pseudoprime, also known as a Carmichael number, is a composite number which passes the Fermat test for any base a s.t.
    (a,N) = 1.


    Question:
    How many values of a are necessary to determine the primality or compositeness of those N in the trial range  <10^6
    which are not absolute Fermat pseudoprimes?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by silversand View Post
    Definition:
    An absolute Fermat pseudoprime, also known as a Carmichael number, is a composite number which passes the Fermat test for any base a s.t.
    (a,N) = 1.


    Question:
    How many values of a are necessary to determine the primality or compositeness of those N in the trial range  <10^6
    which are not absolute Fermat pseudoprimes?
    Since Carmichael numbers have a minimum of 3 factors, the cube root of 10^6 or about 100.

    If you do NOT get a factor within that range, you can be sure that it is NOT a Carmichael number.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Nov 2008
    Posts
    63

    more

    Quote Originally Posted by aidan View Post
    Since Carmichael numbers have a minimum of 3 factors, the cube root of 10^6 or about 100.

    If you do NOT get a factor within that range, you can be sure that it is NOT a Carmichael number.

    still havent totally got it.

    why did the question ask "how many values of a" ?

    i tried to make a program like this,

    Step 1: filter out those prime N by trial division, then filter those N with least prime factor > 100.

    S2: find the GCD of all a from 2 to N-1 and each N.

    S3: filter those a, with GCD > 1.

    S4: find  a^{N-1} mod N with the rest of a .

    if all of them =1 , then N is a carmichael.


    i thought you mean, in S2, we only need to find GCD of all a from 2 to 100?
    is that what you meant?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Carmichael Number Question
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 7th 2010, 01:59 PM
  2. program to find carmichael number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 8th 2009, 09:45 AM
  3. carmichael numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 9th 2009, 07:52 PM
  4. Carmichael number
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 18th 2008, 02:12 PM
  5. Carmichael number
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 17th 2008, 11:42 AM

Search Tags


/mathhelpforum @mathhelpforum