Let the product of severalpairwise coprime integers m1, m2 ... mk be M.
It turns out that, up to a multiple of M, there isone and only one integer which leaves prescribed remainders whendivided by each of these.
This result is universally known as the Chinese Remainder Theorem, although it is sometimes butchered and/or generalized beyond recognition.
Proof:
The general result for any number (k) ofmoduli(plural ofmodulus) is easily obtained by induction from the special case oftwo coprime moduli m and m'. Leaving this induction up to the reader, we'll only prove the k = 2 case:
Given the remainders r and r', we want an n such that (for some q,q'):
n = q m + rn = q'm' + r'
Since m and m' are known to be coprime, there are integers u and v such that um + vm' =1. (One possibility for u and v may be obtained explicitly by retracing backwards the stepsof Euclid's algorithm which lead to the greatest common factor [= 1]of m and m'. This result is now known as Bezout's Lemma.) So:
n = vm'(qm+r) + um(q'm'+r') = (uq'+vq)mm' + [umr'+vm'r]
This shows that n is equal to the integer [umr'+vm'r] up to a multiple of mm'. Conversely, any such number is easily shown to leave the correct remainders. (: Add umr to the square bracket to discover the remainder modulo m.)
Note that, when the moduli arenot pairwise coprime, some potential setsof "remainders" are ruled out: For example, no integer can leave a remainder of 2 when divided by 6 and a remainderof 3 when divided by 4...
If M is the product of several pairwise coprime moduli such as m, an explicit formula (in terms of ourBézout function) can be givenfor the number n (defined up to a multiple of M) which leaves a remainder of rmwhen divided by m :
Explicit Solution of theChinese Remainder Problem
n = mM/mbezout(M/m , m ) rm
If you've read the rest of this page or are otherwise familiar withmodular arithmetic, you may memorize and/or prove the above formulaby recalling that bezout (x,y) is essentially the reciprocal of x modulo y
For example, counting by 7's, 8's, 9's and 11's, we obtain:
There's one important trivial case (often used in schoolwork or inrecreationalmathematics) where the whole computational machinery is not needed: When the remainders areall equal to x (e.g., x=1) then the number itself must be equal to x (modulo M). With coprime moduli, the Chinese Remainder Theorem guarantees that this obvious solution is the only one.
(2003-11-18) Remainders in the divisions by a fixedmodulus (m) obey simple rules...
The first clean presentation of modular arithmetic was publishedby Carl Friedrich Gauss [ the name rhymes with house ] inDisquisitiones Arithmeticae (1801).
The basic observation is that anyinteger n belongs to oneof m so-calledresidue classes modulo m. Theresidue class (or simplyresidue) of n is represented by theremainder (0 to m-1)obtained when wedivide m into n.
Thus, two numbers that differ by a multiple of m havethe same residue modulo m. (You may use this to find the residue of anegative number.)
The interesting thing is that a sum [or a product]has the same residue as the sum [or the product] of the residues involved...
For example, the last digit of apositive integer identifies itsresidue modulo 10. If you want to know what the last digit is when you multiply12546549023 by 9802527, just multiply 3 by 7 and take the last digit ofthat. Much easier.
Another example: Provequicklythat 11n 4n is divisible by 7. Answer.
Notations:
Various notations are used to indicate that "9802527 iscongruent to 7 modulo 10". Formally, congruences have the structure of equations:
9802527
7 [10]
9802527
7 (mod 10)
9802527 mod 10
=
7
[9802527] 10
=
[7] 10
When the modulus used is otherwise specified, every number may stand forits own residue class and straight equations can be writtenwhich would look strange outside of this context. For example, modulo 10:
9802527 = 79802527 = -312546549023 - 9802527 = 6
Dividing Residue Classes:
When n iscoprime to the modulus m,Bézout's Theoremstates there are integers x and y such that
n x + m y = 1
(In practice, such values for x and y may be obtained by tracing back thesteps of Euclid's algorithm in the computation ofthe greatest common divisor of n and m.)
This is to say that the residue of n has areciprocal modulo m,namely the residue class of x. Modulo 10, for example, the reciprocal of 7 is 3,whereas 1 and 9 are their own reciprocals (the residues 0,2,4,5,6,8 are not coprime to 10 and havethereforeno reciprocal modulo 10). Prime moduli are especially interesting,because all nonzero residues have a reciprocal (we're dealing with afield).
With a prime modulus p, the p-1 nonzero residues thus forma multiplicativegroup. This fact may be used to prove the very importantLittle Theoremof Fermat presented in the next article,and it suggests ageneralization due to Euler.
(2003-11-18) For anya not multiple of a prime p, (a p11) is divisible by p.
Fermat's so-calledlittle theorem states that, for any prime p, raising any integer not divisible by p to the power of p-1gives a result which is just one unit above a multiple of p. This was first stated without proof by Fermat in 1640. A proper proof was given in 1736 by Euler,generalized to any modulus p, prime or not (seenext section).
The Many Converses of Fermat's Little Theorem:
They're all derived from the simplest of them (which is very inefficient):
Fermat's Little Theorem Converse : If a positive integer p divides (a p11) for every positive integer a less than itself, then it is prime.
Proof : The relation k p = a p11 implies that a is coprime with p (by Bézout's lemma). Thus, if the premise is true, no integer a between 1 and p can possibly divide p, whichmeansthat p is prime.
Applied directly, the statement would make a poor primality test becauseit seems to require even more trial exponentiations than there are trial divisions in the most naive primality test (taught to schoolchildren).
However, we can use the fact that thenonzero residue classes modulo p form a multiplicative group of order p-1. The number p is primeif and only if that group is cyclic,which is to say that it has onegeneratora.
By Lagrange's theorem, the order of an element divides the order of the group. Therefore, to check that the order of a is indeed p-1, it's enough to check that allproperdivisors of p-1 are ruled out. Furthermore, since every proper divisor divides a maximal one,it suffices to check the maximal proper divisors, namely the numbers of the form (p-1)/q for every prime factor q of (p-1). That's due to Edouard Lucas (1842-1891).
Lucas' theorem (Lucas, 1891) : p is prime if and only if there's a number a such that, for any prime factor q of (p-1) we have:
a (p-1)/q is not congruent to 1 modulo p.
a (p-1) is congruent to 1 modulo p.
Such a number a is called a witness of [the primality of] p.
To prove nonderministically that a number p is prime, using that theorem,we may guess a witness and guess the prime factorization of p-1 (the primality of each factor being checked recursively by the same procedure). The collection of such guesses is known as a Pratt primality certificate and it's the key to a standardized rigorous proof that a given number is prime.
A random number between 1 and p-1 will be a witness of p > 3 with probability (p-1) / (p-3) where is Euler's Totient Function (defined in the next section). Except for a set of very special cases, that proportion tends to zero inversely as ln p which is a practical flaw when is comes to testing the primality of very large number.
To remedy that, Maurice Kraitchik (1882-1957) and D.H. Lehmer (1905-1991) proved a much better theorem which reads very much like the above but allowsdifferent values of a for different prime factors of p-1.
Lehmer-Kraitchik theorem : p is prime if and only if, for any prime factor q of (p-1) there's a number a such that we have:
a (p-1)/q is not congruent to 1 modulo p.
a (p-1) is congruent to 1 modulo p.
(2003-11-18) [Sloane'sA000010 ] (n) is the number of positive integerscoprime to n, between 1 and n.
The key to generalizing Fermat'slittle theoremfrom a prime modulus p [above]to any positive modulus n [below] is an accurate count ofhow many integers between 1 and n arecoprime to n. Such numbers are called thetotatives of n. The number of totatives of n is denoted (n)and is called thetotient of n...
Every integer from 1 to p-1 is atotative of a prime p. So:
(p) = p-1.
When n is the power of a prime (pk), the only numbers between 1 and nthat arenot coprime to n are the n/p multiples of p. Therefore, (n) = n-n/p.
( pk) = pk-1 (p-1).
Finally, we observe that defining over prime powers isenough, because it happens to be amultiplicative function, which is to saythat if p and q arecoprime integers, then (pq) = (p)(q). This is a direct consequence of theChinese Remainder Theorem,since each residue modulo pq which is coprime to pq isuniquely obtained by choosing independently one of the(p)residues modulo p coprime to p and one of the(q) residues modulo q coprime to q.
So, if abc... is the factorization of a positive integer n into primes:
(n) = (abc...) = a(a-1)b(b-1)c(c-1) ...
Sierpinski'sConjecture (now a theorem):
For any integer m greater than 1, there is at least one integer y such that the equation (x) = y has exactly m solutions in x.
This was originally conjectured by Waclaw Sierpinski (1882-1969) in the 1950s. A conditional proof was given in 1961, by Andrzej Schnizel (b.1937). In 1998, Kevin Ford (b.1967) finally proved that conjecture (arXiv:math/9907204v1).
Carmichael's Conjecture (still an open question):
Does the above hold for m=1 ? Is there a totient with multiplicity 1 ?In other words, is there an integer which is the totient of only one number?
(2003-11-18) For any numberacoprime to n,a to the power of (n) is 1 modulo n.
This is one of the most basic and most beautiful early results ofNumber Theory.
The residues modulo n that are coprime to n constitute amultiplicativegroup,which is to say that the product of two such residues isalso a residue coprime to n,and that any such residue has a reciprocal modulo n (whose value may be obtained bytracing backward the steps of Euclid's algorithmthat lead to agreatest common divisor equal to unity).
Lagrange's Theorem(arguably the first great result ofGroup Theory)states that the order of any subgroup divides the order of the whole group. In particular, we may consider theorder of an element,defined as the order of the [multiplicative] subgroup it generates: It's theleast of its positive powers which equals unity. The order of each coprime residue modulo n thus divides theorder(n) of theentire multiplicative group of coprime residues (as specifiedabove).
This implies, as advertised, that we obtain a unity residue when any residue coprime ton is raised (modulo n) to the power of(n).
Order of a residue modulo n :
If the k-th power of a residue is unity, then this residue is coprimewith the modulus n and k is necessarilya multiple of itsorder (as defined above).
(2003-11-21) (Reduced Totient Function) The least exponent that makesallcoprimepowers equal to 1, modulo n.
TheFermat-Euler theoremsays that a k is congruent to 1 modulo nfor any basea coprime to n if k = (n). It doesn't say that (n) is theleast such k...
The least exponent k with the above property is aparticular divisor of the totient (n), called the "reduced totient of n", forwhich the notation (n) was introduced in1910 by R.D. Carmichael (some authors use ""instead of ""). The reduced totient function is called theCarmichael function (or Carmichael'slambda) although it was known to Gaussmuch earlier[Disquisitiones Arithmeticae,Art. 92].
n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(n)
1
1
2
2
4
2
6
2
6
4
10
2
12
6
4
4
16
6
18
4
6
10
(n)
1
1
2
2
4
2
6
4
6
4
10
4
12
6
8
8
16
6
18
8
12
10
The function may be computed using thefollowing rules: [SeeA002322]
(1) = 1; (2) = 1; (4) = 2; (2n) = 2n2 for n 2.
(q) = (q) if q is a power of an odd prime.
Ifa andb are coprime, then (ab) is theLCMof (a) and (b).
Unlike Euler's function (),Carmichael's function () isnotmultiplicative.
In the vocabulary of Group Theory, (n) and (n) are called,respectively, the order and the exponent of the group of invertible classes modulo n.
91 is a pseudoprime to basea if and only if a 90 is congruent to 1, modulo 91. This happens ifa belongs to one ofthe following 36 residues classes, modulo 91:
There are 72 residuescoprime to 91 ( 72 is theEuler totient of 91 ). This is exactly twice as many as above. Such a simple ratio isthe rule...
(2022-03-28) It's always congruent to 8, modulo 9. A cute easy-to-prove fact...
Among the three consecutive integers n-1, n and n+1, there is a multiple of 3. If n-1 and n+1 are primes greater than 3, neither is divisible by 3, So, n must be. Let's denote it n = 3m. We have:
(n1) (n+1) = n2 1 = 9 m2 1
So, this product is congruent to -1 or 8 modulo 3, as advertised.
(2003-11-18) A Carmichael number is a composite number n dividingana for anya.
A Carmichael number is thus apseudoprimeto any basea to which it'scoprime. The term "Carmichael number" was introduced in1950,by N.G.W.H. Beeger (discoverer of the second Wieferich prime in 1922).
In1899, Korselt conjectured the existence of such numbers andcharacterized them (see "Korselt's criterion" below). The smallest of these (561) was discovered in 1910 by Robert D. Carmichael,who subsequently found fifteen examples and conjectured there were infinitely many, a fact which was finally proved by Alford, Granville and Pomerance,in 1992.
A Carmichael number is an oddsquarefree numbercongruent to 1 modulo (p-1) for any prime p dividing it(Korselt's criterion). Thus, 1729 is a Carmichael number because its prime factorizationis 7.13.19 while 1728 happens to be divisible by 6, 12 and 18.
Theabovedefinition of Carmichael's function ()tells that Carmichael numbers are the composite numbers n for which(n)divides(n-1). The way(n)is explicitely computed shows this to be equivalent toKorselt's criterion.
Here are the first Carmichael numbers. [Sloane'sA002997sequence]
Other integer sequences related to Carmichael numbersinclude the following:
A055553 Number of Carmichael numbers with n decimal digits or less: 0, 0, 1 (561 has 3 digits), 7,16, 43, 105, 255, 646, 1547, 3605, 8241, 19279,44706, 105212, 246683, and 585355 with 16 digits or less...
A006931 Least Carmichael numbers with n primefactors, namely:
(2003-11-22) Explicit products that form Carmichael numbersiffall factors are prime.
In 1939, J. Chernik remarked thatthe product (6k+1)(12k+1)(18k+1) is a Carmichael number if the three factors are prime. Furthermore, the thing may be multiplied by(36k+1) ifthat factor is also prime,to produce another Carmichael number with 4 prime factors. For k = 1 this does give two Carmichael numbers:
1729 = 7.13.19 63973 = 7.13.19.37
It has beenwrongly reported [in at least onepublished paper] that the process would continue with an additional (72k+1) prime factor. The above example (k = 1) shows that this is not so: 73 is prime, but the number 7.13.19.37.73 (4670029) is not congruent to 1modulo 72 and is thereforenot a Carmichael number. In fact, a fifth prime factor (72k+1) is acceptable if and only if k hasan even value. Similarly, a sixth prime factor (144k+1) would yield yet another Carmichaelnumber only when k is a multiple of 4. A seventh prime factor (288k+1) is fine whenever k is a multiple of 8...
Such restrictions on k for extensions of Chernik's formula beyond 4 factorsmay or may not have been an oversight of Chernik himself (we've not checked)but this elementary mistake is tainting some otherwise nice discussions of the subject.
Here are integer sequences related to Chernik-typeCarmichael numbers:
Carmichael numbers of the form (6k+1)(12k+1)(18k+1) : 1729, 172081, 294409, 1773289, 4463641, 13992265, 47006785,56052361, 118901521, 172947529, ...
(2003-11-23) Other explicit expressions in the spirit of Chernik's formulas.
When the 4 factors are prime, (ak+1)(bk+1)(ck+1)(dk+1) is a Carmichael number provided a,b,c andd all dividetheir ownsymmetric functions: (a+b+c+d),(ab+ac+ad+bc+bd+cd) and(abc+abd+acd+bcd). A similar sufficient condition holds for products of at least 3 factors of this type.
Here's the complete list of the 6 types of such "generic" 4-factor Carmichaelnumbers, discovered and posted here by the author on 2003-11-23.
"Generic" forms for 3-factor Carmichael numbers are easy to construct.
For example, in hispresentation of all Carmichael numbers below10 000 000 000 000 000, Richard G.E. Pinch notes that theCarmichael number whose lowest prime factor is highest in this rangehappens to be 9585921133193329, which is a product of 3 prime factors of the form:
( 7m + 1 ) ( 8m + 1 ) ( 11m + 1 )
It's not difficult to show that such a product of 3 primes is a Carmichaelnumber if and only if m iscongruent to 314 modulo 616. Furthermore, m must be divisible by 3, or else at least one of the factors would be. All told, m must be 1848k+942 for some k, which gives a product of the form shownin the following table. The number noted by Pinch is for k = 13,which is the lowest value that makes the 3 factors prime:
A formulagiving Carmichael numberswhenever the 3 factors are prime
Here are the highest acceptablevalues of k having a given number of digits: 13,928,9996,99778,999588,9999963,99999466,999999223,9999997803,99999997841,999999999166,9999999998098,99999999997131,999999999996618,9999999999998481,99999999999999018,etc.
For example, k = 999 999 223 yieldsa 40-digit Carmichael number (3887636054124102392503405910694993617809) with three 14-digit prime factors: 12935989955323 . 14783988520369 . 20327984215507.
For k = 9999999999999999999999999994976 (31 digits) we would geta 106-digit Carmichael number which is the product of three 36-digit primes.
With k = 10 329 4624879 we obtain a 1000-digit Carmichael numberwith three prime factors that are each 334 digits in length:
Using a 600 MHz computer, it took us about 2 days to reach this result,after testing for primality 4624879 triplets of factors. The expected number of such tests is roughly proportional to thecube of the target number of digits. Hard testing may be skipped when k is congruent to aresidue that makes one of the 3 factors divisible by 5, 13, 17, 19, 23, etc. These residues are: 0, 2, 4 (mod 5); 1, 7, 9 (mod 13); 1, 11, 16 (mod 17); 3, 4, 7 (mod 19); 9, 17, 19 (mod 23); etc. (Shunning these five explicit cases makes the search about 5 times faster.) Nevertheless, when anontrivial primality test is required [for lack of a small divisor] its duration is proportional to the squareor the cube of the number of digits involved(depending on the duration of a single multiplication,which could theoretically be proportional to the number of digits,but is proportional to thesquare of thatwith ordinary computer implementations). All told, this method is thus not very efficient to generateextremely large Carmichael numbers...
Below is the sequence of the values of m for which (7m+1)(8m+1)(11m+1) is a Carmichael number(A101188). Underlined values indicate Carmichael numberswith at least 4 prime factors, which arenot discussed above:
Of course, there's nothing special about 7, 8 and 11. The above idea can be used with other triplets of pairwise coprime integers to construct 3-factor Carmichael numbers with special features. In a private communication (on 2012-07-10) Dr. Gottfried Barthelused the technique with the triplet 999, 1000, 1001 to obtain an example ofa Carmichael number whose factors would be only about 0.2% apart from each other. He obtained a 42-digit Carmichael number with 3 prime factors, after only 95 trials:
870980350028752028326948209713490300000001 = (999 m + 1) (1000 m + 1) (1001 m + 1) with m = 95 (999 . 1000 . 1001) + 499998000 = 95499903000
(2003-11-29) Efficient ways to findvery large Carmichael numbers.
Generic Carmichael numbers are obtained from the methods presented in thepreceding articles whenseveral predeterminednumbers are simultaneously prime, a rarely satisfied condition whensuch numbers are extremely large.
A similar remark applies to an interesting general approach,known as Chernik's extension method, which is based on the following observation: If a Carmichael number n is considered in its canonical form n = k (n) + 1 and if some divisor d of k is such that the number p = d (n) + 1 happens to be prime, then pn isanother Carmichael number.
(2022-06-27) Parametrization of 3-factor Carmichael numbers.
Yu Jianchun is an impoverished native ofHenanwith a benevolent uncle whose help he stubbornly refused. He has a lifelong passion for elementary mathematics but no formal training.
He has besieged several mathematics departments to no avail, but one of his hand-deliveredfinally piqued the interest of Professor Cai Tianxin, who teaches number theory at Zhejiang University (ZJU). Tianxin invited Jianchun to speak at a seminar in front of colleagues and graduate students. This was apparently enough for the popular press, in China and elsewhere,to herald Jianchun as the newest undiscovered genius. Comparing him toEinstein orRamanujan, no less.
This episode apparently led to a number job offers which helped Yu Jianchun out ofdire straits. As of2017,he was reported to be working as a data analyst in Southeast Asia for $1500/month.
As the media didn't bother with the science behind the "human interest" story, nothing is left of it besides a handwrittennote in Chinese and whatever can be reconstructed from that a two-line quote in Tianxin's book.
It's unclear to me if he ever presented anything much beyond what's dicussed in the previoussection. Proving that a product of algebraic factors is a Carmichael numberassuming those factors are prime is usually just a homework-level exercise. The note seem to promise a classification into 5 categoriesof such algebraic formulas for 3-factor Carmichael numbers, which would be far more exciting. I can't comment with so little information at hand.
(2003-11-18) Does any odd prime p have a Carmichael multiple? [True if p 10000] Is the same true of any odd numbercoprimeto itsEuler totient?
Consider a number n and let q be the lowest common multiple of the numbers(p-1)for all the prime factors p of n. Any multiple of n may be expressed in the form n(qk+r). For such a multiple of n to be a Carmichael number, it must be congruent to 1 modulo any(p-1)and thus also modulo the lowest common multiple of all those quantities, which is q. This means that nr must be congruent to 1 modulo q. In other words, r must be thereciprocal of n modulo q. Such a reciprocal exists if and only if n and q arecoprime,which is thus a necessary condition for n to divide any Carmichael number. It's also necessary for n to be odd andsquarefree. We may call aCarmichael divisor a number that has a Carmichael multiple,and combine both conditions into one short statement:
Carmichael divisors are odd numbers coprime to their totients.
I've been conjecturing (since 1980 or so) that the converse holds, namely: Any odd numbercoprime to its Euler totient dividessome Carmichael number.
With encouragements from Max Alexseyev (thanks!) I teamed up with Joe Crumpinthe last days of 2007 and we did check the conjecture for all relevant numbersbelow 10000. For many years, the smallest number I had not been able to deal with was 885... Here's part of the story:
On Carmichael numbers divisible by 885 = 3 . 5 . 59
The above general considerations imply that a Carmichael multiple of 885 must be of theform 885 (116k+89) [since 116 = LCM(3-1,5-1,59-1) and 89 is the reciprocal of885 modulo 116]. Such a Carmichael number can't be divisible by 7,because this would make its totient divisible by 6and thus not coprime with itself (since 885 is not coprime with 6). Similarly, no prime factor of (116k+89) can be of the form 6m+1, 10m+1 or 118m+1.
Furthermore, a prime divisor can't be 3, 5 or 59 (as those divide 885). It can't be 29 either, because 29 divides the totient of 885. All told, such a prime factor is different from 29 and 59and is congruent to 17, 23 or 29 modulo 30 (all primes congruent to1 modulo 59 must also be ruled out, starting with 827 and 1889).
If p is prime and kp is a Carmichael number, then p-1 divides k-1.
Proof: ByKorselt's criterion,there's an integer m for which m(p-1) = kp-1. This means, indeed, that (m-k)(p-1) = k-1
A consequence of that lemma is thatthere are no Carmichael numbers of the form 885 p where p is prime. Indeed, such a prime would make p-1 equal to one of the 12 divisors of 884. This restriction leaves only two possible prime values for p, besides 3 and 5 (namely, 53 and 443) and neither of them works!
Similarly, if both p and q are prime, then 885 pq can only be a Carmichael numberwhen p-1 divides 885q-1 (and q-1 divides 885p-1). So, we may just let q run through the aforementioned "allowed" values and examinethe finitely many values of p which make p-1 a divisor of 885q-1.
Although the smallest Carmichael multiple of 885 remains unknown,one explicit example was discovered on 2007-12-21 by Joe K. Crump who used his ownprior workto search quickly through numbers n whichdivide 2n-2.
Starting with a multiple of 2517 (found on 2007-12-20, with the same tactics) Joe plugged the gaps which had been present since 2003-12-01in my owntable of Carmichael multiples byproviding Carmichael multiples of 885, 2391, 2517, 2571, 2589, 2595, 2685 and 2949 (we put together jointly alarger table shortly thereafter). Although Joe Crump's approach doesn't necessarily provide the least such multiples,his breakthrough provides strongercomputational support for my conjecture (formulated around 1980) that such Carmichael multiplesexist for all odd numbers coprime to their Euler totient.
Joe's attention had been caught by MaxAlekseyev ("Maxal") who posted "Michon's conjecture" in theOpen Problem Garden on 2007-08-04
A weaker conjecture applies only to prime numbers and merely states that:
Any odd prime has Carmichael multiples.
See ourtable of the leastCarmichael multiples of odd primes below 10000.
I came up with the above conjectures around 1980. At the time, it was not yet known that there were infinitely many Carmichael numbers. Therefore, an early proof of either conjecture would have establishedthat...
Numbers coprime to their Euler totients are sometimes called cyclic numbers (A003277) because a group whose order is such a number mustbe cyclic. The number 2 is cyclic but all the other cyclic numbers are odd. Thus,the main conjecture is that 2 is the onlycyclic number withoutCarmichael multiples. This can be stated even more compactly:
Any odd cyclic number has Carmichael multiples.
A formulation stressing that this is a necessary and sufficientcondition is: A positive integer has Carmichael multiples if and only if it's odd and cyclic.
One simple corollary is an obfuscated weaker form of the conjecture: Any divisor of a Carmichael number divides infinitely many of them.
References
Carl Friedrich Gauss "Disquisitiones Arithmeticae" (1801).
A. Korselt (Alwin Reinhold Korselt, 1864-1947; Ph.D. in1902) "Problème Chinois" L'Intermédiaire des Mathématiciens, 6, pp.142-143 (1899).
Robert D. Carmichael "Note on a new number theory function" (1910) Bulletin of the American Mathematical Society, XVI, pp.232-238.
Robert D. Carmichael "On composite numbers which satisfy the Fermat congruence" American Mathematical Monthly, XIX, pp.22-27 (1912).
N.G.W.H. Beeger [MR-12:159e] "On composite numbers n for which an-1 1 (mod n) for everya prime to n" Scripta Mathematica, 16, pp.133-135 (1950).
William R. Alford, Andrew Granville,Carl Pomerance "There are infinitely many Carmichael numbers" (1992 result) Annals of Mathematics, 139, pp.703-722 (1994). [pdf]
Richard G.E. Pinch "The Carmichael Numbers up to 1015" Mathematics of Computation, 61, pp.381-391 (1993).
