Page 1 of 2 12 LastLast
Results 1 to 15 of 18

Math Help - Carmichael numbers

  1. #1
    Member
    Joined
    Jun 2008
    Posts
    148

    Carmichael numbers

    Let n be a Carmichael number, and p_n be the smallest odd prime factor of n-1.

    Prove the following (or find a counterexample if false):

    p_n is always less than or equal to 17.

    PS: Don't spend to much time this one. I have no idea if it is solvable (if its true).
    Follow Math Help Forum on Facebook and Google+

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

    False for n>20,000

    Just to clarify, you're conjecturing that given a Carmichael Number n, all prime factors of n are greater than or equal to 17? This is false.

    Counterexamples: 294409, 56052361, 118901521

    Carmichael Number -- from Wolfram MathWorld
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2008
    Posts
    148
    I'm conjecturing on the factors of n-1 (not n) when n is a Carmichael number. Specifically, I'm conjecturing that the smallest odd prime factor of n-1 is bounded by 17.

    I actually just took a look at some Carmichaels on wiki. It wouldn't surprise me if this bound was actually smaller than 17 (like 7 or 11 maybe).

    Here is a simple but interesting question.

    Do there exist any Carmichael numbers n, such that n = 3mod4.

    If so, do you think there are infinitely many of them (note: this second question is probably too difficult to solve).?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Examples

    do there exist any carmichael numbers n, such that n = 3mod4?
    64377991
    8346731851
    48874811311
    68926289491
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jun 2008
    Posts
    148
    Heh he, I figured as such. btw how easy was it to find those? My guess is that less than 5% of all Carmichaels are 3mod4.

    Can you find an integer n=3mod4 that is a 2,3,-strong pseudoprime? What about a 2,3,5-strong pseudopime?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Random Theorem

    Nope. We know that if p=(6k+1), q=(12k+1), r=(18k+1) are all three prime, then n=pqr is a Carmichael Number.

    I found a random uncredited theorem on GMU (Google, Master of the Universe), giving us another arithmetic progression to work with:

    p=(60k+43), q=(180k+127), r=(300k+211)

    All three of these happen to be 3 (mod 4), and multiplying them you get 4k(...)+27 which is also 3 (mod 4).

    You don't have to go very far with k before finding a few solutions.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jun 2008
    Posts
    148
    Interesting stuff. I wasn't aware of that one.

    I've noticed that when dealing with Carmichael numbers (or even 2,3-pseudoprimes), the number of small factors of n-1 is usually quite large (ie its divisible by 2,3,4,5,6 etc.). This shouldn't be too surprising, since when n is a Carmichael number, we have that

    lcm(p_1-1,....p_k-1)                                  |<br />
 n-1, where p_1,....p_k are the distinct prime factors of n.

    Hence any small factor contained in p_i-1, will also be small factor of n-1. Indeed, if I gave the condition that n \equiv 11 (\bmod 12), we would probably find even fewer Carmichaels than n such that n \equiv 3 (\bmod 4)
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Any questions about Carmichael Numbers probably can be answered by:

    Richard G.E. Pinch
    ...research interests have been in computational number theory, the arithmetic of elliptic curves, algebraic combinatorics and public-key cryptography. ... current personal research is on Carmichael numbers and pseudoprimes.

    Do a google search and you can get his table of Carmichael Numbers:
    * The Carmichael numbers up to 10 to the 21 *
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408
    This is interesting: http://www.mathhelpforum.com/math-he...l-numbers.html

    That's a third construction method I've come across. Let {a_1,a_2,a_3,...,a_k} and {b_1,b_2,b_3,...,b_k} be sets of integers. If for some m, p_i=a_im+b_i is an odd prime for all i, then n=p_1p_2p_3...p_k is a Carmichael Number.

    Three known solutions:
    a={6,12,18} b={1,1,1}
    a={60,180,300} b={43,127,211}
    a={1,2,3} b={0,-1,-2}

    Are there other sets a and b satisfying this theorem? Infinite number of sets? A way of constructing the constructing sets? Does each produce an infinite number of Carmichaels? Each of these three solutions were proved in different ways - is there a single method to prove these do indeed construct Carmichaels?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Jun 2008
    Posts
    148
    Quote Originally Posted by Media_Man View Post
    This is interesting: http://www.mathhelpforum.com/math-he...l-numbers.html

    That's a third construction method I've come across. Let {a_1,a_2,a_3,...,a_k} and {b_1,b_2,b_3,...,b_k} be sets of integers. If for some m, p_i=a_im+b_i is an odd prime for all i, then n=p_1p_2p_3...p_k is a Carmichael Number.
    Interesting statement. Unfortunately this theorem will only hold if we have the additional constraint that p_i - 1 divides n - 1 for each prime p_i.

    For example, consider the case when m=5, and
    a={2,3,5} b={1,2,4}
    We have that p_1 = 11, p_2 = 17, and p_3= 29 which are all prime. Thus n=5423. However 11-1=10, which clearly doesn't divide n - 1 = 5422


    Quote Originally Posted by Media_Man View Post
    Each of these three solutions were proved in different ways - is there a single method to prove these do indeed construct Carmichaels?
    Good question. We should review these three current solutions to see if some common properties are used in order to discover general method. One thing for finding a general method is clear though, we would need to find primes p_1,p_2,p_3...,p_k such that gcd(p_1 -1,p_2 - 1,...,p_k - 1) is fairly large. I believe this idea is already generally used in constructing Carmichaels.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    For what sets a,b does this theorem hold?

    Unfortunately this theorem will only hold if we have the additional constraint that divides for each prime
    Just to clarify, I am not claiming that this works for all sets a and b. I am asking for which sets it does work. If 6k+1, 12k+1, and 18k+1 are all three primes, then their product is always a Carmichael. This is also true of these other two examples. I am asking for what other arithmetic progressions this happens. I doubt these are three magical ways to construct Carmichael numbers. There must be other similar arithmetic tricks. Or, perhaps these three fall into some special class of numbers that can be generalized to describe all Carmichaels instead of just a small subset.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Jun 2008
    Posts
    148
    I'll have to think about that one. Making things simpler, lets fix k=3 say and let b_i = 1 for all i. For just this, do you think the only solution is a_1=6, a_2 = 12 and a_3 = 18?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    There are a lot of different directions to go here...

    My major short-term interest is finding a fourth or fifth construction a_1k+b_1, a_2k+b_2, a_3k+b_3 that generates Carmichaels for all k, with the condition that each factor is prime. Perhaps it is possible to find a finite, mutually exclusive set of generating sets for three-factor Carmichaels. If infinite, can we find a constructive way of generating all of them? The ultimate logic here is coming up with a way to partition the Carmichael numbers into classes based on their construction. Results about them can then be easily determined by looking at some countable list of ways they can be constructed. This is probably going to be a very difficult problem, as there are 20 million Carmichaels under 10^{21} , ranging from 3 to 12 factors.

    Let me phrase my previous question more rigorously: *Sorry, in these posts I am switching letters around.

    For what sets of integers a={ a_1,a_2,a_3,...,a_m} and b={ b_1,b_2,b_3,...,b_m} does the following theorem hold: For all k=0,1,2,... let p_i=a_ik+b_i for i=1,2,3,...,m. If p_i is prime for all i, then n=p_1p_2p_3...p_m is a Carmichael number.

    Here's a path I can see going somewhere with this problem:

    1. For the three known solutions, find a common property about them, and use this property to write a single proof that these three generate Carmichaels when all factors are prime.
    2. Find a few other solutions using the common properties we find from (1)
    3. Try to generalize this property to describe all solutions a,b, at least for m=3, whether finite or not.

    Here are some simple results, based on known properties...
    Carmichaels are non-square: If a_i=a_j , then b_i \neq b_j
    gcd(a_i,b_i)=1

    60k+43=6*1*(10k+7)+1
    180k+127=6*3*(10k+7)+1
    300k+211=6*5*(10k+7)+1
    Last edited by Media_Man; April 19th 2009 at 08:20 AM.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Jun 2008
    Posts
    148
    Quote Originally Posted by Media_Man View Post
    My major short-term interest is finding a fourth or fifth construction a_1k+b_1, a_2k+b_2, a_3k+b_3 that generates Carmichaels for all k, with the condition that each factor is prime. Perhaps it is possible to find a finite, mutually exclusive set of generating sets for three-factor Carmichaels. If infinite, can we find a constructive way of generating all of them?
    Interesting question.


    Quote Originally Posted by Media_Man View Post
    60k+43=6*1*(10k+7)+1
    180k+127=6*3*(10k+7)+1
    300k+211=6*5*(10k+7)+1
    What you have written on the right hand side here is an interesting way to express these three numbers. Indeed, if a_i,b_i are such that when we let s_i=gcd(a_i,b_i-1), we have that a=\frac{a_i}{s_i} and b=\frac{b_i-1}{s_i} both constant regardless of i, then it follows that we can express p_i=a_im +b_i as p_i=s_i(am+b) +1.

    This suggests that we need only look at integers of the form p_i=a_ik +1. This simplifes things greatly I believe. Indeed for m=3, in order to satisfy the criteria lcm(p_1-1,p_2-1,p_3-1) |<br />
n-1,

    we need only find  a_1, a_2, a_3 such that lcm(a_1,a_2,a_3) |<br />
gcd(a_1a_2 + a_1a_3 + a_2a_3, a_1 + a_2 + a_3).

    Do you see why (hint: it can be found by multiplying out the three primes and expressing it as a cubic polynomial with respect to k).
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    On the right track...

    Quote Originally Posted by jamix View Post
    it follows that we can express p_i=a_im +b_i as p_i=s_i(am+b) +1.

    This suggests that we need only look at integers of the form p_i=a_ik +1.
    This is true, but then we'd have to add the criterion that k \equiv b (\bmod a). After all, we can express (60m+43)(180m+127)(300m+211) as (6k+1)(18k+1)(30k+1) via your algorithm. But then, letting k=1, we get 7*19*31=4123, which is not a Carmichael, despite 7,19, and 31 being prime.


    Quote Originally Posted by jamix View Post
    we need only find  a_1, a_2, a_3 such that lcm(a_1,a_2,a_3) |<br />
gcd(a_1a_2 + a_1a_3 + a_2a_3, a_1 + a_2 + a_3).

    Do you see why (hint: it can be found by multiplying out the three primes and expressing it as a cubic polynomial with respect to k).
    Well done. Furthermore, I believe that if a_1, a_2, a_3 are relatively prime, then gcd(a_1a_2 + a_1a_3 + a_2a_3, a_1 + a_2 + a_3)=1 (can we prove this?), adding yet another constraint.

    By the way, here is a resource for some raw data: Notes - Carmichael Numbers . I was able to break this up into manipulable form without much trouble on excel, but the file was too big to send you.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

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. two definitions of Carmichael numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 27th 2009, 11:18 AM
  3. why is this argument about carmichael numbers true
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 11th 2009, 04:00 AM
  4. carmichael numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 9th 2009, 07:52 PM
  5. Carmichael Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 25th 2007, 06:09 AM

Search Tags


/mathhelpforum @mathhelpforum