On 12/18/2010 12:13 PM, Peter Kosinar wrote:
>> Given p1 = 3, p2 = 11, what are the primes p3 such that
>> 3 * 11 * p3 is a Carmichael number.
>> [Kermit's method]
> Alternatively, use the original of Korselt's criterion (P will denote p3
> in Kermit's notation) to get "(P-1) divides (33P - 1)" straight away.
> Then, factoring and checking the other conditions implied by Korselt's
> criterion gives us the answer(s).
Thank you very much for this simplification.
It enables us to extend Korselt's criterion.
p1 p2 p3 is a Carmichael
if and only if
(p1 - 1) divides both (p2 p3 - 1) and (p1 p2 p3 - 1).
(p2 - 1) divides both (p1 p3 - 1) and (p1 p2 p3 - 1).
(p3 - 1) divides both (p1 p2 - 1) and (p1 p2 p3 - 1).
With out loss of generality, we may take p1 and p2 as given,
and prove that
if (p3-1) divides (p1 p2 p3 - 1)
then (p3-1) also divides (p1 p2 - 1).
Given: (p3-1) divides (p1 p2)p3 - 1.
C(p3-1) = (p1 p2) p3 - 1
c p3 - c = (p1 p2) p3 - 1
c p3 - c - (p1 p2) p3 = -1
Add p1 p2 to both sides of the equation.
c p3 - c - (p1 p2) p3 + p1 p2 = p1 p2 - 1
Factor Left side of equation.
(p3 - 1) (c - p1 p2) = p1 p2 - 1
(p3 - 1) divides (p1 p2 - 1)
In the case of 561 = 3 * 11 * 17,
(3-1) divides 11 * 17 - 1
(11-1) divides 3 * 17 - 1
(17-1) divides 3 * 11 - 1
Probably with a little more work, we can extend this to Carmichael
numbers that are the product of more than three primes.