Carmichael's totient function conjecture
In mathematics, Carmichael's totient function conjecture concerns the multiplicity of values of Euler's totient function φ(n), which counts the number of integers less than and coprime to n. It states that, for every n there is at least one other integer m ≠ n such that φ(m) = φ(n). Robert Carmichael first stated this conjecture in 1907, but as a theorem rather than as a conjecture. However, his proof was faulty, and in 1922, he retracted his claim and stated the conjecture as an open problem.
Examples
The totient function φ(n) is equal to 2 when n is one of the three values 3, 4, and 6. Thus, if we take any one of these three values as n, then either of the other two values can be used as the m for which φ(m) = φ(n).
Similarly, the totient is equal to 4 when n is one of the four values 5, 8, 10, and 12, and it is equal to 6 when n is one of the four values 7, 9, 14, and 18. In each case, there is more than one value of n having the same value of φ(n).
The conjecture states that this phenomenon of repeated values holds for every n.
| k | numbers n such that φ(n) = k (sequence A032447 in the OEIS) | number of such ns (sequence A014197 in the OEIS) |
| 1 | 1, 2 | 2 |
| 2 | 3, 4, 6 | 3 |
| 4 | 5, 8, 10, 12 | 4 |
| 6 | 7, 9, 14, 18 | 4 |
| 8 | 15, 16, 20, 24, 30 | 5 |
| 10 | 11, 22 | 2 |
| 12 | 13, 21, 26, 28, 36, 42 | 6 |
| 16 | 17, 32, 34, 40, 48, 60 | 6 |
| 18 | 19, 27, 38, 54 | 4 |
| 20 | 25, 33, 44, 50, 66 | 5 |
| 22 | 23, 46 | 2 |
| 24 | 35, 39, 45, 52, 56, 70, 72, 78, 84, 90 | 10 |
| 28 | 29, 58 | 2 |
| 30 | 31, 62 | 2 |
| 32 | 51, 64, 68, 80, 96, 102, 120 | 7 |
| 36 | 37, 57, 63, 74, 76, 108, 114, 126 | 8 |
| 40 | 41, 55, 75, 82, 88, 100, 110, 132, 150 | 9 |
| 42 | 43, 49, 86, 98 | 4 |
| 44 | 69, 92, 138 | 3 |
| 46 | 47, 94 | 2 |
| 48 | 65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210 | 11 |
| 52 | 53, 106 | 2 |
| 54 | 81, 162 | 2 |
| 56 | 87, 116, 174 | 3 |
| 58 | 59, 118 | 2 |
| 60 | 61, 77, 93, 99, 122, 124, 154, 186, 198 | 9 |
| 64 | 85, 128, 136, 160, 170, 192, 204, 240 | 8 |
| 66 | 67, 134 | 2 |
| 70 | 71, 142 | 2 |
| 72 | 73, 91, 95, 111, 117, 135, 146, 148, 152, 182, 190, 216, 222, 228, 234, 252, 270 | 17 |
Lower bounds
There are very high lower bounds for Carmichael's conjecture that are relatively easy to determine. Carmichael himself proved that any counterexample to his conjecture (that is, a value n such that φ(n) is different from the totients of all other numbers) must be at least 1037, and Victor Klee extended this result to 10400. A lower bound of was given by Schlafly and Wagon, and a lower bound of was determined by Kevin Ford in 1998.[1]
The computational technique underlying these lower bounds depends on some key results of Klee that make it possible to show that the smallest counterexample must be divisible by squares of the primes dividing its totient value. Klee's results imply that 8 and Fermat primes (primes of the form 2k + 1) excluding 3 do not divide the smallest counterexample. Consequently, proving the conjecture is equivalent to proving that the conjecture holds for all integers congruent to 4 (mod 8).
Other results
Ford also proved that if there exists a counterexample to the conjecture, then a positive proportion (in the sense of asymptotic density) of the integers are likewise counterexamples.[1]
Although the conjecture is widely believed, Carl Pomerance gave a sufficient condition for an integer n to be a counterexample to the conjecture (Pomerance 1974). According to this condition, n is a counterexample if for every prime p such that p − 1 divides φ(n), p2 divides n. However Pomerance showed that the existence of such an integer is highly improbable. Essentially, one can show that if the first k primes p congruent to 1 (mod q) (where q is a prime) are all less than qk+1, then such an integer will be divisible by every prime and thus cannot exist. In any case, proving that Pomerance's counterexample does not exist is far from proving Carmichael's conjecture. However if it exists then infinitely many counterexamples exist as asserted by Ford.
Another way of stating Carmichael's conjecture is that, if A(f) denotes the number of positive integers n for which φ(n) = f, then A(f) can never equal 1. Relatedly, Wacław Sierpiński conjectured that every positive integer other than 1 occurs as a value of A(f), a conjecture that was proven in 1999 by Kevin Ford.[2]
Notes
- Sándor & Crstici (2004) p. 228
- Sándor & Crstici (2004) p. 229
References
- Carmichael, R. D. (1907), "On Euler's φ-function", Bulletin of the American Mathematical Society, 13 (5): 241–243, doi:10.1090/S0002-9904-1907-01453-2, MR 1558451.
- Carmichael, R. D. (1922), "Note on Euler's φ-function", Bulletin of the American Mathematical Society, 28 (3): 109–110, doi:10.1090/S0002-9904-1922-03504-5, MR 1560520.
- Ford, K. (1999), "The number of solutions of φ(x) = m", Annals of Mathematics, 150 (1): 283–311, doi:10.2307/121103, JSTOR 121103, MR 1715326, Zbl 0978.11053.
- Guy, Richard K. (2004), Unsolved problems in number theory (3rd ed.), Springer-Verlag, B39, ISBN 978-0-387-20860-2, Zbl 1058.11001.
- Klee, V. L., Jr. (1947), "On a conjecture of Carmichael", Bulletin of the American Mathematical Society, 53 (12): 1183–1186, doi:10.1090/S0002-9904-1947-08940-0, MR 0022855, Zbl 0035.02601
{{citation}}: CS1 maint: multiple names: authors list (link). - Pomerance, Carl (1974), "On Carmichael's conjecture" (PDF), Proceedings of the American Mathematical Society, 43 (2): 297–298, doi:10.2307/2038881, JSTOR 2038881, Zbl 0254.10009.
- Sándor, Jozsef; Crstici, Borislav (2004), Handbook of number theory II, Dordrecht: Kluwer Academic, pp. 228–229, ISBN 978-1-4020-2546-4, Zbl 1079.11001.
- Schlafly, A.; Wagon, S. (1994), "Carmichael's conjecture on the Euler function is valid below 1010,000,000", Mathematics of Computation, 63 (207): 415–419, doi:10.2307/2153585, JSTOR 2153585, MR 1226815, Zbl 0801.11001.