# Thread: Carmichael numbers

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

2. ## 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

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

4. ## Examples

do there exist any carmichael numbers n, such that n = 3mod4?
64377991
8346731851
48874811311
68926289491

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

6. ## 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.

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

$\displaystyle lcm(p_1-1,....p_k-1) | n-1$, where $\displaystyle p_1,....p_k$ are the distinct prime factors of n.

Hence any small factor contained in $\displaystyle p_i-1$, will also be small factor of $\displaystyle n-1$. Indeed, if I gave the condition that $\displaystyle n \equiv 11 (\bmod 12)$, we would probably find even fewer Carmichaels than n such that $\displaystyle n \equiv 3 (\bmod 4)$

8. 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 *

9. This is interesting: http://www.mathhelpforum.com/math-he...l-numbers.html

That's a third construction method I've come across. Let $\displaystyle {a_1,a_2,a_3,...,a_k}$ and $\displaystyle {b_1,b_2,b_3,...,b_k}$ be sets of integers. If for some m, $\displaystyle p_i=a_im+b_i$ is an odd prime for all $\displaystyle i$, then $\displaystyle 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?

10. 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 $\displaystyle {a_1,a_2,a_3,...,a_k}$ and $\displaystyle {b_1,b_2,b_3,...,b_k}$ be sets of integers. If for some m, $\displaystyle p_i=a_im+b_i$ is an odd prime for all $\displaystyle i$, then $\displaystyle 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 $\displaystyle p_i - 1$ divides $\displaystyle n - 1$ for each prime $\displaystyle p_i$.

For example, consider the case when m=5, and
a={2,3,5} b={1,2,4}
We have that $\displaystyle p_1 = 11$,$\displaystyle p_2 = 17$, and $\displaystyle p_3= 29$ which are all prime. Thus n=5423. However $\displaystyle 11-1=10$, which clearly doesn't divide $\displaystyle 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 $\displaystyle p_1,p_2,p_3...,p_k$ such that $\displaystyle gcd(p_1 -1,p_2 - 1,...,p_k - 1)$ is fairly large. I believe this idea is already generally used in constructing Carmichaels.

11. ## 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.

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

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

My major short-term interest is finding a fourth or fifth construction $\displaystyle a_1k+b_1$, $\displaystyle a_2k+b_2$, $\displaystyle 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 $\displaystyle 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 $\displaystyle a=${$\displaystyle a_1,a_2,a_3,...,a_m$} and $\displaystyle b=${$\displaystyle b_1,b_2,b_3,...,b_m$} does the following theorem hold: For all $\displaystyle k=0,1,2,...$ let $\displaystyle p_i=a_ik+b_i$ for $\displaystyle i=1,2,3,...,m$. If $\displaystyle p_i$ is prime for all $\displaystyle i$, then $\displaystyle 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 $\displaystyle a_i=a_j$ , then $\displaystyle b_i \neq b_j$
$\displaystyle gcd(a_i,b_i)=1$

$\displaystyle 60k+43=6*1*(10k+7)+1$
$\displaystyle 180k+127=6*3*(10k+7)+1$
$\displaystyle 300k+211=6*5*(10k+7)+1$

14. Originally Posted by Media_Man
My major short-term interest is finding a fourth or fifth construction $\displaystyle a_1k+b_1$, $\displaystyle a_2k+b_2$, $\displaystyle 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
$\displaystyle 60k+43=6*1*(10k+7)+1$
$\displaystyle 180k+127=6*3*(10k+7)+1$
$\displaystyle 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 $\displaystyle a_i,b_i$ are such that when we let $\displaystyle s_i=gcd(a_i,b_i-1),$ we have that $\displaystyle a=\frac{a_i}{s_i}$ and $\displaystyle b=\frac{b_i-1}{s_i}$ both constant regardless of i, then it follows that we can express $\displaystyle p_i=a_im +b_i$ as $\displaystyle p_i=s_i(am+b) +1$.

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

we need only find $\displaystyle a_1, a_2, a_3$ such that $\displaystyle lcm(a_1,a_2,a_3) | 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).

15. ## On the right track...

Originally Posted by jamix
it follows that we can express $\displaystyle p_i=a_im +b_i$ as $\displaystyle p_i=s_i(am+b) +1$.

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

Originally Posted by jamix
we need only find $\displaystyle a_1, a_2, a_3$ such that $\displaystyle lcm(a_1,a_2,a_3) | 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 $\displaystyle a_1, a_2, a_3$ are relatively prime, then $\displaystyle 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.

Page 1 of 2 12 Last