## Extended criterion for Carmichael numbers

Expand Messages
• It has been proven that an odd number N is a Carmichael number if and only if, for each prime divisor p, (p-1) divides N-1. Let N = q1 q2 q3 ...qj be a
Message 1 of 1 , Dec 18 3:21 PM
It has been proven that an odd number N is a Carmichael number
if and only if, for each prime divisor p,
(p-1) divides N-1.

Let N = q1 q2 q3 ...qj be a Carmichael number.

(q1 - 1) divides N-1

(q1 - 1) divides q1 q2 q3 ...qj - 1

There exist c such that q1 q2 q3...qj - 1 = c(q1-1) = c q1 - c

c q1 - (q2 q3 ... qj) q1 - c = -1

Add q2 q3 ... qj to both sides of equation.

c q1 - (q2 q3 ... qj) q1 - c + (q2 q3 ... qj) = (q2 q3 ... qj) - 1

Factor left side of equation.

(c - ( q2 q2 ... qj ) ) (q1 - 1) = (q2 q3 .... qj) - 1

(q1 - 1) divides (q2 q3 .... qj) - 1

Since q1 represents any one of the divisors of N,

we have the extended criterion
that

each prime divisor, p, of the Carmichael number N,

(p-1) divides (N/p) -1

For the smallest Carmichael number
561 = 3 * 11 * 17,

(3-1) divides (561/3 - 1) = 187 - 1 = 186 = 2*93

(11-1) divides (561/11 - 1) = 51 - 1 = 50 = 5*10

(17-1) divides (561/17 - 1) = 33 - 1 = 32 = 2*16

Kermit
Your message has been successfully submitted and would be delivered to recipients shortly.