home 
index 
units 
counting 
geometry 
algebra 
trigonometry & functions 
calculus
analysis  sets & logic  number theory  recreational  misc  nomenclature & history  physics 
Final Answers

Related Links (Outside this Site)The Prime Pages by Chris Caldwell (University of Tennessee at Martin)Pseudoprimes and Carmichael Numbers by Richard G.E. Pinch Carmichael Numbers by Jerry Lin & Dan Tam (EECS 203 students) Sloane's OnLine Encyclopedia of Integer Sequences Modular Arithmetic at FactBites.com 
If you've read the rest of this page or are otherwise familiar with modular arithmetic, you may memorize and/or prove the above formula by 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: n = 792 r_{7}  2079 r_{8}  1232 r_{9} + 2520 r_{11} (modulo 5544) There's one important trivial case (often used in schoolwork or in recreational mathematics) where the whole computational machinery is not needed: When the remainders are all 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. Remainders in the divisions by a fixed modulus (m) obey simple rules... The first clean presentation of modular arithmetic was published by Carl Friedrich Gauss [ the name rhymes with house ] in Disquisitiones Arithmeticae (1801). The basic observation is that any integer n belongs to one of m socalled residue classes modulo m. The residue class (or simply residue) of n is represented by the remainder (0 to m1) obtained when we divide m into n. Thus, two numbers that differ by a multiple of m have the same residue modulo m. (You may use this to find the residue of a negative number.) The modulus m is usually positive, but there's no great difficulty in allowing negative moduli (classes modulo m and m are the same). For a zero modulus, there would be infinitely many residue classes, each containing only one element. [This need not be disallowed.] 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 a positive integer identifies its residue modulo 10. If you want to know what the last digit is when you multiply 12546549023 by 9802527, just multiply 3 by 7 and take the last digit of that. Much easier. Another example: Prove quickly that 11^{n}  4^{n} is divisible by 7. Answer. Notations:Various notations are used to indicate that "9802527 is congruent to 7 modulo 10". Formally, congruences have the structure of equations:
When the modulus used is otherwise specified, every number may stand for its own residue class and straight equations can be written which would look strange outside of this context. For example, modulo 10: 9802527 = 7 9802527 = 3 12546549023  9802527 = 6 Dividing Residue Classes:When n is coprime to the modulus m, Bézout's Theorem states 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 the steps of Euclid's algorithm in the computation of the greatest common divisor of n and m.) This is to say that the residue of n has a reciprocal 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 have therefore no reciprocal modulo 10). Prime moduli are especially interesting, because all nonzero residues have a reciprocal (we're dealing with a field). With a prime modulus p, the p1 nonzero residues thus form a multiplicative group. This fact may be used to prove the very important Little Theorem of Fermat presented in the next article, and it suggests a generalization due to Euler. For any a not multiple of a prime p, (a^{ p1}1) is divisible by p. Fermat's socalled little theorem states that, for any prime p, raising any integer not divisible by p to the power of p1 gives 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 (see next section). The Many Converses of Fermat's Little Theorem:

n  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22 

l(n)  1  1  2  2  4  2  6  2  6  4  10  2  12  6  4  4  16  6  18  4  6  10 
f(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 l may be computed using the following rules: [See A002322]
Unlike Euler's function (f), Carmichael's function (l) is not multiplicative.
In the vocabulary of Group Theory, f(n) and l(n) are called, respectively, the order and the exponent of the group of invertible classes modulo n.
91 is a pseudoprime to base a if and only if a^{ 90 } is congruent to 1, modulo 91. This happens if a belongs to one of the following 36 residues classes, modulo 91:
1, 3, 4, 9, 10, 12, 16, 17, 22, 23, 25, 27, 29, 30, 36, 38, 40, 43, 48,
51, 53, 55, 61, 62, 64, 66, 68, 69, 74, 75, 79, 81, 82, 87, 88, 90.
There are 72 residues coprime to 91 ( 72 is the Euler totient of 91 ). This is exactly twice as many as above. Such a simple ratio is the rule...
A Carmichael number is thus a pseudoprime to any base a to which it's coprime. The term "Carmichael number" was introduced in 1950, by N.G.W.H. Beeger (discoverer of the second Wieferich prime in 1922).
In 1899, Korselt conjectured the existence of such numbers and characterized 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 odd squarefree number congruent to 1 modulo (p1) for any prime p dividing it (Korselt's criterion). Thus, 1729 is a Carmichael number because its prime factorization is 7.13.19 while 1728 happens to be divisible by 6, 12 and 18.
The above
definition of Carmichael's function (l)
tells that Carmichael numbers are the composite numbers n for which
Here are the first Carmichael numbers. [Sloane's A002997 sequence]
561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461, 530881, 552721, 656601, 658801, 670033, 748657, 825265, 838201, 852265, 997633, 1024651...
Other integer sequences related to Carmichael numbers include the following:_{ }
3 factors: 561 = 3.11.17 4 factors: 41041 = 7.11.13.41 5 factors: 825265 = 5.7.17.19.73 6 factors: 321197185 = 5.19.23.29.37.137 7: 5394826801 = 7.13.17.23.31.67.73 8: 232250619601 = 7.11.13.17.31.37.73.163 9: 9746347772161 = 7.11.13.17.19.31.37.41.641 10: 1436697831295441 = 11.13.19.29.31.37.41.43.71.127 11: 60977817398996785 = 5.7.17.19.23.37.53.73.79.89.233 12: 7156857700403137441 = 11.13.17.19.29.37.41.43.61.97.109.127 13: 1791562810662585767521 = 11.13.17.19.31.37.43.71.73.97.109.113.127 14: 87674969936234821377601 = 7.13.17.19.23.31.37.41.61.67.89.163.193.241 15: 11.13.17.19.29.31.41.43.61.71.73.109.113.127.181 16: 17.19.23.29.31.37.41.43.61.67.71.73.79.97.113.199 17: 13.17.19.23.29.31.37.41.43.61.67.71.73.97.113.127.211 18: 13.17.19.23.29.31.37.41.43.61.67.71.73.97.127.199.281.397 19: 13.17.19.23.29.31.37.41.43.61.67.71.73.109.113.127.151.281.353 20: 11.13.17.19.29.31.37.41.43.61.71.73.97.101.109.113.151.181.193.641 21: 13.17.19.23.29.31.37.41.43.61.67.71.73.89.97.113.181.211.241.331.353 13.17.19.23.29.31.37.41.43.61.67.71.73.89.97.101.113.127.181.193.211.1153
The largest of these were established systematically by Richard G.E. Pinch, who has found the next items in this list as well (up to 34 factors, as of 20041122).
In 1939, J. Chernik remarked that the 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) if that 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 been wrongly reported [in at least one published 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 1 modulo 72 and is therefore not a Carmichael number. In fact, a fifth prime factor (72k+1) is acceptable if and only if k has an even value. Similarly, a sixth prime factor (144k+1) would yield yet another Carmichael number 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 factors may 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 Cherniktype Carmichael numbers:_{ }
n  Number of these with n or fewer digits (by Harvey Dubner)  

3 4 5 6 7 8 9 10 11 12 
0 1 1 2 2 3 7 10 16 25 
13 14 15 16 17 18 19 20 21 22 
50 86 150 256 436 783 1435 2631 4765 8766 
23 24 25 26 27 28 29 30 31 32 
16320 30601 57719 109504 208822 400643 771735 1494772 2903761 5658670 
33 34 35 36 37 38 39 40 41 42 
11059937 21696205 ? 42670184 ? 84144873 ? 166369603 329733896 655014986 1303918824 2601139051 5198859223 
A036060 is erroneously based on preliminary results of H. Dubner, since corrected in print. 
When the 4 factors are prime, (ak+1)(bk+1)(ck+1)(dk+1) is a Carmichael number provided a, b, c and d all divide their own symmetric 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" 4factor Carmichael numbers, discovered and posted here by the author on 20031123.
4Factor Carmichael Number  Acceptable Values of k  

(6k+1)(12k+1)(18k+1)(36k+1)  1, 45, 56, 121, 206, 255, 380, 506, 511, 710, 871, 1025, 1421, 1515, 1696 ...  
(18k+1)(36k+1)(108k+1)(162k+1)  1, 71, 155, 176, 241, 346, 420, 540, 690, 801, 1145, 1421, 1506, 2026, 2066 ...  
(24k+1)(72k+1)(192k+1)(288k+1)  99, 105, 355, 600, 729, 795, 949, 1635, 2014, 3224, 5100, 5320, 5559, 7550 ...  
(60k+1)(90k+1)(300k+1)(450k+1)  11, 39, 97, 98, 212, 256, 279, 296, 303, 319, 336, 361, 466, 592, 900, 902 ...  
(42k+1)(252k+1)(588k+1)(882k+1)  10, 51, 114, 151, 399, 405, 440, 494, 726, 741, 934, 1140, 1176, 1275, 1290 ...  
* Products of the form (20m+1) (80m+1) (100m+1) (200m+1) are allowed by the sole divisibility of the symmetric functions but m has to be divisible by 3 (m = 3k) or else at least one factor would be so divisible. 
"Generic" forms for 3factor Carmichael numbers are easy to construct.
For example, in his presentation of all Carmichael numbers below 10 000 000 000 000 000, Richard G.E. Pinch notes that the Carmichael number whose lowest prime factor is highest in this range happens 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 Carmichael number if and only if m is congruent 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 shown in the following table. The number noted by Pinch is for k = 13, which is the lowest value that makes the 3 factors prime:
Carmichael Number  Acceptable Values of k (A101186) 

(12936k+6595)(14784k+7537)(20328k+10363)  13, 123, 218, 223, 278, 411, 513, 551, 588, 733, 743, 796, 856, 928, 1168, 1226, 1263, 1401, 1533, 1976, 1981, 2013, 2096, 2138, 2241, 2376, 2556, 2676, 2703, 3626, 3703, 3718, 3971, 4008, 4121, 4138, 4163, 4188, 4211, 4313, 4423, 4653, 4656, 4901, 5018, 5278, 5411, 5423, 5538, 5776, 5863, 5908, 6186, 6283, 6623, 6753, 6933, 7501, 7688, 7986, 8181, 8398, 8476, 8651, 8816, 8916, 8923, 8963, 9273, 9441, 9496, 9626, 9628, 9676, 9823, 9891, 9996, 10163, 10166, 10633, 10688, ... 
Here are the highest acceptable values 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 yields a 40digit Carmichael number (3887636054124102392503405910694993617809) with three 14digit prime factors: 12935989955323 . 14783988520369 . 20327984215507.
For k = 9999999999999999999999999994976 (31 digits) we would get a 106digit Carmichael number which is the product of three 36digit primes.
With k = 10^{ 329 } 4624879 we obtain a 1000digit Carmichael number with three prime factors that are each 334 digits in length:
(12936´10^{ 329} 59827428149) (14784´10^{ 329} 68374203599) (20328´10^{ 329} 94014529949)
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 the
cube of the target number of digits.
Hard testing may be skipped when k is congruent to a
residue that makes one of the 3 factors divisible by 5, 13, 17, 19, 23, etc.
These residues are:
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 numbers with at least 4 prime factors, which are not discussed above:
18, 216, 24966, 228246, 299790, 403806, 413046, 446310, 514686, 760470, 948966, 1019190, 1087566, 1355526, 1374006, 1471950, 1582830, 1715886, 2159406, 2266590, 2334966, 2589990, 2833926, 3652590, 3661830, 3720966, 3874350, 3951966, 4142310, 4391790, 4724430, 4946190, 4996086, 5206142, 6701790, 6844086, 6871806...
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 3factor Carmichael numbers with special features. In a private communication (on 20120710) Dr. Gottfried Barthel used the technique with the triplet 999, 1000, 1001 to obtain an example of a Carmichael number whose factors would be only about 0.2% apart from each other. He obtained a 42digit 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
Generic Carmichael numbers are obtained from the methods presented in the preceding articles when several predetermined numbers are simultaneously prime, a rarely satisfied condition when such 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
Constructing a
Ten Billion Factor Carmichael Number
by Steven Hayman & Andrew Shallue
(July 2012)
A new algorithm for constructing large Carmichael numbers
by Günter Löh & Wolfgang Niebuhr (1996)
A
New Method for Producing Large Carmichael Numbers
by H. Dubner (1989)
Consider a number n and let q be the lowest common multiple of the numbers
I've been conjecturing (since 1980 or so) that the converse holds, namely: Any odd number coprime to its Euler totient divides some Carmichael number.
With encouragements from Max Alexseyev (thanks!) I teamed up with Joe Crump in the last days of 2007 and we did check the conjecture for all relevant numbers below 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 . 59The above general considerations imply that a Carmichael multiple of 885 must be of the form 885 (116k+89) [since 116 = LCM(31,51,591) and 89 is the reciprocal of 885 modulo 116]. Such a Carmichael number can't be divisible by 7, because this would make its totient divisible by 6 and 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 59 and is congruent to 17, 23 or 29 modulo 30 (all primes congruent to 1 modulo 59 must also be ruled out, starting with 827 and 1889). Few prime factors remain allowed: 17, 23, 47, 53, 83, 89, 107, 113, 137, 149, 167, 173, 179, 197, 227, 233, 239, 257, 263, 269, 293, 317, 347, 353, 359, 383, 389, 419, 443, 449, 467, 479, 503, 509, 557, 563, 569, 587, 593, 599, 617, 647, 653, 659, 677, 683, 719, 743, 773, 797, 809, 839, 857, 863, 887... Lemma: If p is prime and kp is a Carmichael number, then p1 divides k1. Proof: By Korselt's criterion, there's an integer m for which m(p1) = kp1. This means, indeed, that (mk)(p1) = k1 A consequence of that lemma is that there are no Carmichael numbers of the form 885 p where p is prime. Indeed, such a prime would make p1 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 number when p1 divides 885q1 (and q1 divides 885p1). So, we may just let q run through the aforementioned "allowed" values and examine the finitely many values of p which make p1 a divisor of 885q1.
Although the smallest Carmichael multiple of 885 remains unknown,
one explicit example was discovered on 20071221 by Joe K. Crump
who used his own
prior work
to search quickly through numbers n which
divide 24354644805191195265 = 3 . 5 . 59 . 449 . 1373 . 205553 . 217169 Starting with a multiple of 2517 (found on 20071220, with the same tactics) Joe plugged the gaps which had been present since 20031201 in my own table of Carmichael multiples by providing Carmichael multiples of 885, 2391, 2517, 2571, 2589, 2595, 2685 and 2949 (we put together jointly a larger table shortly thereafter). Although Joe Crump's approach doesn't necessarily provide the least such multiples, his breakthrough provides stronger computational support for my conjecture (formulated around 1980) that such Carmichael multiples exist for all odd numbers coprime to their Euler totient. Joe's attention had been caught by Max Alekseyev ("Maxal") who posted "Michon's conjecture" in the Open Problem Garden on 20070804 
A weaker conjecture applies only to prime numbers and merely states that:
See our table of the least Carmichael 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 established that...
Numbers coprime to their Euler totients are sometimes called cyclic numbers (A003277) because a group whose order is such a number must be cyclic. The number 2 is cyclic but all the other cyclic numbers are odd. Thus, the main conjecture is that 2 is the only cyclic number without Carmichael multiples. This can be stated even more compactly:
A formulation stressing that this is a necessary and sufficient condition is: A positive integer has Carmichael multiples if and only if it's odd and cyclic.