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.
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)
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 resultsedit
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]
Sándor, Jozsef; Crstici, Borislav (2004), Handbook of number theory II, Dordrecht: Kluwer Academic, pp. 228–229, ISBN978-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.
carmichael, totient, function, conjecture, mathematics, concerns, multiplicity, values, euler, totient, function, which, counts, number, integers, less, than, coprime, states, that, every, there, least, other, integer, such, that, robert, carmichael, first, st. In mathematics Carmichael s totient function conjecture concerns the multiplicity of values of Euler s totient function f 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 f m f 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 Contents 1 Examples 2 Lower bounds 3 Other results 4 Notes 5 References 6 External linksExamples editThe totient function f 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 f m f 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 f n The conjecture states that this phenomenon of repeated values holds for every n k numbers n such that f n k sequence A032447 in the OEIS number of such ns sequence A014197 in the OEIS 1 1 2 22 3 4 6 34 5 8 10 12 46 7 9 14 18 48 15 16 20 24 30 510 11 22 212 13 21 26 28 36 42 616 17 32 34 40 48 60 618 19 27 38 54 420 25 33 44 50 66 522 23 46 224 35 39 45 52 56 70 72 78 84 90 1028 29 58 230 31 62 232 51 64 68 80 96 102 120 736 37 57 63 74 76 108 114 126 840 41 55 75 82 88 100 110 132 150 942 43 49 86 98 444 69 92 138 346 47 94 248 65 104 105 112 130 140 144 156 168 180 210 1152 53 106 254 81 162 256 87 116 174 358 59 118 260 61 77 93 99 122 124 154 186 198 964 85 128 136 160 170 192 204 240 866 67 134 270 71 142 272 73 91 95 111 117 135 146 148 152 182 190 216 222 228 234 252 270 17Lower bounds editThere 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 f 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 10 10 7 displaystyle 10 10 7 nbsp was given by Schlafly and Wagon and a lower bound of 10 10 10 displaystyle 10 10 10 nbsp 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 editFord 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 f 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 f n f then A f can never equal 1 Relatedly Waclaw Sierpinski 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 edit a b Sandor amp Crstici 2004 p 228 Sandor amp Crstici 2004 p 229References editCarmichael R D 1907 On Euler s f 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 f 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 f 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 a href Template Citation html title Template Citation citation a 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 Sandor 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 External links editWeisstein Eric W Carmichael s Totient Function Conjecture MathWorld Retrieved from https en wikipedia org w index php title Carmichael 27s totient function conjecture amp oldid 1068683664, wikipedia, wiki, book, books, library,
