Let be a positive integer. Then is defined to be the smallest positive integer such that for all such that
Note that always exists because satisfies the equation above, by Euler's theorem. So In fact, by a standard division algorithm argument: let then it's clear that for all coprime to This contradicts minimality of unless
Values of Carmichael's lambda function can be calculated using the following formulas:
where the are distinct positive prime numbers.
These formulas will be proved in the next section. Two immediate consequences are as follows:
- If then
Find the smallest positive integer such that for any relatively prime to
Note in this example that for all since all either divide or depending on whether is divisible by respectively.
Let be an odd prime. An element of order in is called a primitive root. The wiki on primitive roots contains the full classification of integers for which there is a primitive root mod in particular, there is a primitive root mod when is an odd prime power. Since the smallest positive integer power of that is congruent to is this shows that Since from the discussion in the previous section, this shows that they are equal.
When the primitive roots wiki shows that for and an easy induction shows that so the order of does not divide but it is a power of 2, so it is This shows that
The last statement is a straightforward application of the Chinese remainder theorem. In particular, if then for any choice of primitive roots and if is a power of 2 greater than 4 there is a unique element mod that is congruent to each of the mod and it is easy to show that the order of equals the LCM of the On the other hand, a similar Chinese remainder theorem argument shows that any element raised to that LCM must be mod since it is modulo all the prime powers.
One important fact that is immediate from the proof is there is always an element whose multiplicative order equals Such are sometimes called primitive lambda-roots.
Find a primitive lambda-root modulo
Start with The idea is to find primitive lambda-roots modulo and and apply the Chinese remainder theorem. always works modulo powers of and is actually a primitive root modulo as well. For a primitive root mod will suffice. So now solve to get the solution This is not unique (exercise: how many different primitive lambda-roots are there?).
Since Fermat's little theorem implies that for all positive integers less than a given prime a natural test for primality is as follows: given a large number pick an integer and compute If the answer is not then is not prime.
But if and is it possible to say that is prime? The answer is no; for instance, but On the other hand, so varying the choice of takes care of
Unfortunately, there are some composite values of for which any choice of relatively prime to will result in an inconclusive test. If say then so no choice of will show that is composite. A composite number which cannot be proved composite by this primality test is called a Carmichael number. By a division algorithm argument (similar to the one given earlier in this wiki), the converse of this criterion is true as well: is a Carmichael number if and only if
which divides So is a Carmichael number (in fact, it is the smallest Carmichael number).
See the Carmichael numbers wiki for more details.