Carmichael numbers

**jamix** · April 12th 2009, 02:06 PM

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).

**Media_Man** · April 15th 2009, 12:36 PM

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

**jamix** · April 15th 2009, 01:13 PM

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).?

**Media_Man** · April 17th 2009, 09:58 AM

do there exist any carmichael numbers n, such that n = 3mod4?

64377991
8346731851
48874811311
68926289491

**jamix** · April 17th 2009, 11:20 AM

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?

**Media_Man** · April 17th 2009, 12:33 PM

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.

**jamix** · April 17th 2009, 07:18 PM

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)$

**aidan** · April 18th 2009, 08:58 AM

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 *

**Media_Man** · April 18th 2009, 12:04 PM

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?

**jamix** · April 18th 2009, 02:08 PM

Originally Posted by Media_Man

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$

Originally Posted by Media_Man

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.

**Media_Man** · April 18th 2009, 05:49 PM

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.

**jamix** · April 18th 2009, 08:36 PM

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?

**Media_Man** · April 19th 2009, 06:51 AM

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$

**jamix** · April 19th 2009, 02:39 PM

Originally Posted by Media_Man

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.

Originally Posted by Media_Man

$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).

**Media_Man** · April 21st 2009, 11:31 AM

Originally Posted by jamix

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.

Originally Posted by jamix

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.

Thread: Carmichael numbers

LinkBack

Thread Tools

Display

Carmichael numbers

False for n>20,000

Examples

Random Theorem

For what sets a,b does this theorem hold?

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

On the right track...

Similar Math Help Forum Discussions

proof with carmichael numbers

two definitions of Carmichael numbers

why is this argument about carmichael numbers true

carmichael numbers

Carmichael Numbers

Search Tags