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

Final Answers
© 2000-2014   Gérard P. Michon, Ph.D.

Modular Arithmetic

Mathematics is the Queen of sciences,  
and arithmetic the Queen of mathematics.  

Carl Friedrich Gauss (1777-1855)   

Articles previously on this page:

  • Pseudoprimes to base a.
    The above articles have moved...  Click for the new location.
    blank
     border
     border

Related articles on this site:

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 On-Line Encyclopedia of Integer Sequences
Modular Arithmetic  at FactBites.com
 
border
border

Modular Arithmetic
from Fermat and Euler to Carmichael and beyond...


(2004-11-25)   The Chinese Remainder Theorem

Let the product of several pairwise coprime integers  m1, m2 ... mk  be  M.

It turns out that, up to a multiple of  M,  there is one and only one integer which leaves prescribed remainders when divided 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) of moduli (plural of modulus) is easily obtained by induction from the special case of two 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  + r
n  =  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 steps of Euclid's algorithm which lead to the greatest common factor [= 1] of m and m'.  This result is now known as  Bezout's Theorem.)  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.  (HINT:  Add umr to the square bracket to discover the remainder modulo m.)  Halmos

Note that, when the moduli are not pairwise coprime, some potential sets of "remainders" are ruled out:  For example, no integer can leave a remainder of 2 when divided by 6 and a remainder of 3 when divided by 4...


If  M  is the product of several pairwise coprime moduli such as  m,  an explicit formula (in terms of our Bézout function) can be given for the number  n  (defined up to a multiple of  M)  which leaves a remainder of rm when divided by  m :

Explicit Solution of the Chinese Remainder Problem
n     =     åm   M/m  bezout ( M/m , m )   rm

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  Halmos

For example, counting by 7's, 8's, 9's and 11's, we obtain:

n     =     792 r7  -  2079 r8  -  1232 r9  +  2520 r11   (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.


(2003-11-18)   Modular Arithmetic:  The Algebra of Congruences
Remainders in the divisions by a fixed modulus (m) obey simple rules...

 Carl F. Gauss 
 1777-1855 
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 so-called residue classes modulo m.  The residue class (or simply residue) of n is represented by the remainder (0 to m-1) 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   11n - 4n   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:

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 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, Bezout'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 p-1 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.


 Pierre de Fermat 
 (1601-1665) (2003-11-18)   Fermat's "Little Theorem"
For any a not multiple of a prime p,  (a p-1-1)  is divisible by p.

Fermat's so-called little theorem states that for any prime p, raising any number not divisible by p to the power of p-1 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  (see below).


(2003-11-18)   Euler's Totient Function   f         [ Sloane's A000010 ]
f(n) is the number of positive integers coprime to n, between 1 and n.
 
n 01 23456789 10111213141516 1718
f(n) 01 12242646 410412688 166

The key to generalizing Fermat's little theorem from a prime modulus p [above] to any positive modulus n [below] is an accurate count of how many integers between 1 and n are coprime to n.  Such numbers are called the totatives of n.  The number of totatives of n is denoted f(n) and is called the totient of n...

Every integer from 1 to p-1 is a totative of a prime p.  So:

f(p) = p-1.

When n is the power of a prime (pk ), the only numbers between 1 and n that are not coprime to n are the n/p multiples of p.  Therefore, f(n) = n-n/p.

f( pk )   =   pk-1 (p-1).

Finally, we observe that defining f over prime powers is enough, because it happens to be a multiplicative function, which is to say that if p and q are coprime integers, then  f(pq) = f(p)f(q).  This is a direct consequence of the Chinese Remainder Theorem, since each residue modulo pq which is coprime to pq is uniquely obtained by choosing independently one of the f(p) residues modulo p coprime to p and one of the f(q) residues modulo q coprime to q.

So, if  aa bb cg ...  is the factorization of a positive integer n into primes:

f (n)   =   f ( aa bb cg ...)   =   aa-1 (a-1) bb-1 (b-1) cg-1 (c-1)  ...

 Waclaw Sierpinski 
 1982-1969

Sierpinski's Conjecture  (now a theorem):

For any integer  m  greater than  1,  there is at least one integer  y  such that the equation   f(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 by A. Schnizel in 1961.  In 1998, the conjecture was finally proven by Kevin Ford  (arXiv:math/9907204v1).

Carmichael's Conjecture  (still an open question):

Does the above hold for  m=1 ?  Is there a totient with multiplicity  1 ?


(2003-11-18)   Euler's Generalization of Fermat's "Little Theorem"
For any number a coprime to n, a to the power of  f(n)  is 1 modulo n.

 Leonhard Euler 
 1707-1783 This is one of the most basic and most beautiful early results of Number Theory.

The residues modulo n that are coprime to n constitute a multiplicative  group, which is to say that the product of two such residues is also a residue coprime to n, and that any such residue has a reciprocal modulo n (whose value may be obtained by tracing backward the steps of Euclid's algorithm that lead to a greatest common divisor equal to unity).

Lagrange's Theorem (arguably the first great result of Group Theory) states that the order of any subgroup divides the order of the whole group.  In particular, we may consider the order of an element, defined as the order of the [multiplicative] subgroup it generates:  It's the least of its positive powers which equals unity.  The order of each coprime residue modulo n thus divides the order f(n) of the entire multiplicative group of coprime residues  (as specified above).

This implies, as advertised, that we obtain a unity residue when any residue coprime to n is raised (modulo n) to the power of f(n)Halmos

Order of a residue modulo n :

If the k-th power of a residue is unity, then this residue is coprime with the modulus  n  and  k  is necessarily a multiple of its order  (as defined above).


(2003-11-21)   Carmichael's Function   l   (Reduced Totient Function)
The least exponent that makes all coprime powers equal to 1, modulo n.

The Fermat-Euler theorem says that  a k  is congruent to 1 modulo n for any base a coprime to n if k = f(n).  It doesn't say that f(n) is the least such k...

The  least  exponent  k  with the above property is a particular divisor of the  totient  f(n),  called the "reduced totient of n", for which the notation  l(n)  was introduced in 1910 by R.D. Carmichael  (some authors use "y" instead of "l").  The  reduced totient function  l is called the Carmichael function (or Carmichael's lambda)  although it was known to  Gauss  much  earlier [Disquisitiones Arithmeticae, Art. 92].

n 123456789 1011121314151617 1819202122
l(n) 11224262 6410212644 166184610
f(n) 112242646 410412688166 1881210

The function  l  may be computed using the following rules:   [See A002322]

  • l(1) = 1;   l(2) = 1;   l(4) = 2;   l(2n ) = 2n-2   for n > 2.
  • l(q) = f(q)   if q is a power of an odd prime. 
  • If a and b are coprime, then  l(ab)  is the LCM of  l(a)  and  l(b). 

Unlike Euler's function (f), Carmichael's function (l) is not multiplicative.

In the vocabulary of  Group Theoryf(n) and l(n) are called, respectively, the  order  and the  exponent  of the group of  invertible  classes modulo n.


 Click Here 
 for Details (2004-01-24; Google query from a  Swedish student)
To which bases is 91 a pseudoprime?

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...


(2003-11-18)   Carmichael Numbers   (Absolute Pseudoprimes)
A Carmichael number is a composite number n dividing an-a for any a.

A Carmichael number is thus a pseudoprime to any base a to which it's coprime.

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.  The term "Carmichael number" was introduced by N.G.W.H. Beeger in 1950.

A Carmichael number is an odd squarefree number congruent to 1 modulo (p-1) 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 l(n) divides (n-1).  The way l(n) is explicitely computed shows this to be equivalent to Korselt's criterion.

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: 

  • 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 prime factors, namely:
 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 2004-11-22).


(2003-11-22)   The Chernik formulas for generic Carmichael numbers :
Explicit products that form Carmichael numbers iff all factors are prime.

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 Chernik-type Carmichael numbers: 

  • A046025:  Values which make (6k+1), (12k+1) & (18k+1) prime:
    1, 6, 35, 45, 51, 55, 56, 100, 121, 195, 206, 216, 255, 276, 370 ...
  • A033502:  3-prime Carmichael numbers   (6k+1)(12k+1)(18k+1) :
    1729, 294409, 56052361, 118901521, 172947529, 216821881 ...
    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.
     
  • Values which make  (6k+1)(12k+1)(18k+1)  a Carmichael number:
    1, 5, 6, 11, 15, 22, 33, 35, 45, 51, 55, 56, 61, 85, 96, 100, 103, 105, 115, 121, 195, 206, 216, 225, 242, 255, 276, 370 ... A101187
  • Carmichael numbers of the form  (6k+1)(12k+1)(18k+1) :
    1729, 172081, 294409, 1773289, 4463641, 13992265, 47006785, 56052361, 118901521, 172947529, 216821881 ...


(2003-11-23)   Generic Carmichael Numbers
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 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" 4-factor Carmichael numbers, discovered and posted here by the author on 2003-11-23.

Generic Carmichael numbers with 4 prime factors
4-Factor Carmichael NumberAcceptable 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 ...
(60k+1)(240k+1)(300k+1)(600k+1)* 111, 247, 553, 583, 835, 902, 910, 1407, 1479, 1617, 1875, 2149, 2597, 2659 ...
(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.

3-Factor Formulas :

"Generic" forms for 3-factor 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:

A formula giving Carmichael numbers whenever the 3 factors are prime
Carmichael NumberAcceptable 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, the highest 9-digit value for k (999 999 223) yields a 40-digit Carmichael number (3887636054124102392503405910694993617809) with 14-digit prime factors: 12935989955323.14783988520369.20327984215507.

For k = 9999999999999999999999999994976  (31 digits)  we would get a 106-digit Carmichael number which is the product of three 36-digit primes.

With   k = 10 329 - 4624879   we obtain a 1000-digit 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:  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 a nontrivial primality test is required  [for lack of a small divisor]  its duration is proportional to the square or 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 the square of that with ordinary computer implementations).  All told, this method is thus not very efficient to generate extremely 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 are 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 same 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)  DrGottfried 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 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)   Generating Large Carmichael Numbers
Efficient ways to find very large Carmichael numbers.

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  n  =  k l(n) + 1  and if some divisor d of k is such that the number   p  =  d l(n) + 1  happens to be prime, then pn is another Carmichael number.

 Come back later, we're
 still working on this one...

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)


(2003-11-18)   Facts and Conjectures about Carmichael Divisors
Does any odd prime p have a Carmichael multiple?   [True if p < 10000]
Is the same true of any odd number coprime to its Euler 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 the reciprocal of n modulo q.  Such a reciprocal exists if and only if n and q are coprime, which is thus a necessary condition for n to divide any Carmichael number.  It's also necessary for n to be odd and squarefree.  We may call a Carmichael 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 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 the smallest number I had not been able to deal with was 885...  Here's part of the story:

Looking for a Carmichael number divisible by  885 = 3 . 5 . 59

The above general considerations imply that a Carmichael multiple of 885 must be of the form  885 (116k+89)  [since 116 = LCM(3-1,5-1,59-1) 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 p-1 divides k-1.

Proof:   By Korselt's criterion, there's an integer  m  for which  m(p-1) = kp-1.  This means, indeed, that  (m-k)(p-1) = k-1   Halmos

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  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 number when p-1 divides 885q-1 (and q-1 divides 885p-1).  So, we may just let  q  run through the aforementioned "allowed" values and examine the 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 own prior work to search quickly through numbers  n  which divide  2n-2.

24354644805191195265   =   3 . 5 . 59 . 449 . 1373 . 205553 . 217169

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-01 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 2007-08-04    ;-)

weaker conjecture applies only to prime numbers and merely states that:

Any odd prime has Carmichael multiples.

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:

Any odd cyclic number has Carmichael multiples.

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.


References

  1. Carl Friedrich Gauss
    "Disquisitiones Arithmeticae"   (1801). 
  2. A. Korselt  ( Alwin Reinhold Korselt, 1864-1947;  Ph.D. in 1902)
    "Problème Chinois"
    L'Intermédiaire des Mathématiciens6, pp.142-143 (1899). 
  3. Robert D. Carmichael
    "Note on a new number theory function"   (1910)
    Bulletin of the American Mathematical SocietyXVI, pp.232-238. 
  4. Robert D. Carmichael
    "On composite numbers which satisfy the Fermat congruence"
    American Mathematical MonthlyXIX, pp.22-27 (1912). 
  5. N.G.W.H. Beeger   [MR-12:159e]   "On composite numbers n
    for which   an-1 º 1 (mod n)   for every a prime to n
    "
    Scripta Mathematica16, pp.133-135 (1950). 
  6. William R. Alford, Andrew Granville, Carl Pomerance
    "There are infinitely many Carmichael numbers"   (1992 result)
    Annals of Mathematics139, pp.703-722 (1994).  [pdf]
  7. Richard G.E. Pinch   "The Carmichael Numbers up to 1015 "
    Mathematics of Computation61, pp.381-391 (1993).
  8. Richard G.E. Pinch   "The Carmichael Numbers up to 1016 "
    ftp://ftp.dpmms.cam.ac.uk/pub/Carmichael/  (ArXiv, 1998-03-18)
  9. Harvey Dubner
    "Carmichael numbers of the form   (6m+1)(12m+1)(18m+1) "
    Journal of Integer Sequences5, art.02.2.1 (2002).
border
border
visits since Dec. 1, 2003
 (c) Copyright 2000-2014, Gerard P. Michon, Ph.D.