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
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).
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
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).?
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.
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
, where are the distinct prime factors of n.
Hence any small factor contained in , will also be small factor of . Indeed, if I gave the condition that , we would probably find even fewer Carmichaels than n such that
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 *
This is interesting: http://www.mathhelpforum.com/math-he...l-numbers.html
That's a third construction method I've come across. Let and be sets of integers. If for some m, is an odd prime for all , then 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?
Interesting statement. Unfortunately this theorem will only hold if we have the additional constraint that divides for each prime .
For example, consider the case when m=5, and
a={2,3,5} b={1,2,4}
We have that , , and which are all prime. Thus n=5423. However , which clearly doesn't divide
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 such that is fairly large. I believe this idea is already generally used in constructing Carmichaels.
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.Unfortunately this theorem will only hold if we have the additional constraint that divides for each prime
My major short-term interest is finding a fourth or fifth construction , , 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 , 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 { } and { } does the following theorem hold: For all let for . If is prime for all , then 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 , then
Interesting question.
What you have written on the right hand side here is an interesting way to express these three numbers. Indeed, if are such that when we let we have that and both constant regardless of i, then it follows that we can express as .
This suggests that we need only look at integers of the form . This simplifes things greatly I believe. Indeed for m=3, in order to satisfy the criteria ,
we need only find such that .
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).
This is true, but then we'd have to add the criterion that . After all, we can express as via your algorithm. But then, letting , we get , which is not a Carmichael, despite 7,19, and 31 being prime.
Well done. Furthermore, I believe that if are relatively prime, then (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.