Carmichael NumbersDate: 10/31/97 at 12:45:54 From: Jerry TAO Subject: About Carmichael number Why must a Carmichael number be the product of at least three distinct primes? Why is n a Carmichael number iff (p-1) divides (n-1) for every prime p dividing n? I understand why a Carmichael number must be square free. Thanks. Date: 10/31/97 at 13:47:51 From: Doctor Rob Subject: Re: About Carmichael number Let G(N) be the multiplicative group of units modulo N. The Carmichael function lambda(N) is the exponent of this group; that is, the smallest number e such that a^e = 1 (mod N) for all a in G(N). A Carmichael number is defined as a composite number N for which lambda(N) divides N-1. If prime p|N, then it is true that for every b in G(N), b^(p-1) = 1 (mod p), and there exists at least one b such that p-1 is the minimum positive exponent that works. Such b's are called primitive roots modulo p, and there are phi(p-1) of them. Then b^(p-1) = 1 (mod p), and we are picking b to be a primitive root modulo p. Now find a in G(N) such that a = b (mod p) and a = 1 (mod N/p), which you can do by using the Chinese Remainder Theorem. (Note that GCD(p,N/p) = 1 since N is squarefree.) Then a is also a primitive root modulo p. Now a^lambda(N) = 1 (mod N) implies a^(N-1) = 1 (mod N) (since lambda(N)|N-1), which implies that a^(N-1) = 1 (mod p) (since p|N). Together with the last paragraph, this implies that a^[s*(p-1)+t*(N-1)] = 1 (mod p), for all integers s and t, so a^GCD(p-1,N-1) = 1 (mod p) (since GCD(u,v) = s*u+t*v for some integers s and t). But 0 < GCD(p-1,N-1) <= p-1, and p-1 is minimal, so GCD(p-1,N-1) = p-1, so p-1|N-1. Suppose now that N = p*q, 1 < p < q. We know that q-1|N-1. Write N = d*(q-1) + 1 = p*q, with d > 1 (since p > 1). Reducing modulo q, d = 1 (mod q). Write d = e*q + 1, with e > 1 (since d > 1), so N = (e*q+1)*(q-1) + 1 = e*q^2 - e*q + q = (e*q-e+1)*q, so p = e*(q-1) + 1 > e*(p-1) + 1 > (p-1) + 1 = p, since q > p and e > 1, a contradiction. This contradiction means that no Carmichael number N can be of the form N = p*q, 1 < p < q. You are aware that Carmichael numbers must be squarefree. The definition prohibits Carmichael number from being prime. The only remaining possibility is that they are the product of at least three distinct primes. Examples with exactly three distinct primes are many, the smallest being 561 = 3*11*17. -Doctor Rob, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/