﻿

# Carmichael's totient function conjecture

In mathematics, Carmichael's totient function conjecture concerns the multiplicity of values of Euler's totient function &phi;("n"), which counts the number of integers less than and coprime to "n".

This function &phi;("n") is equal to 2 when "n" is one of the three values 3, 4, and 6. It is equal to 4 when "n" is one of the four values 5, 8, 10, and 12. 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 &phi;("n").

The conjecture states that this phenomenon of repeated values holds for every "n". That is, for every "n" there is at least one other integer "m" ≠ "n" such that &phi;("m") = &phi;("n").
Robert Carmichael first stated this conjecture 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.Carmichael proved that any counterexample to his conjecture (that is, a value "n" such that &phi;("n") is different from the totients of all other numbers) must be at least 1037, and Victor Klee extended this result to 10400. Carmichael's conjecture has since been verified computationally for all "n" less than or equal to 10107 by Schlafly and Wagon. The current lower bound for a counterexample to the Conjecture is 101010, which was determined by Kevin Ford in 1998. Ford went on to prove that if there exists a counterexample to the Conjecture, then a positive fraction (that is infinitely many) of the integers are likewise counterexamples.

Carmichael's Conjecture is one of the first among open problems with very high lower bounds and which are relatively easy to determine. The computational technique basically depends on some key results of Klee which makes it possible to show that the smallest counterexample must be divisible by squares of the primes dividing it. Klee's results imply that 8 and Fermat primes (primes of the form 2"k"+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).

Although the conjecture is widely believed, Carl Pomerance gave a sufficient condition for an integer "n" to be a counterexample to the conjecture. According to this condition, "n" is a counterexample if for every prime "p" such that "p" − 1 divides &phi;("n"), "p"2 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 "q""k"+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, ifA("f") denotes the number of positive integers "n" for which &phi;("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.

References

*citation
last = Carmichael | first = R. D. | author-link = Robert Daniel Carmichael
doi = 10.1090/S0002-9904-1907-01453-2
id = MR|1558451
issue = 5
journal = Bulletin of the American Mathematical Society
pages = 241–243
title = On Euler's φ-function
volume = 13
year = 1907
.

*citation
last = Carmichael | first = R. D. | author-link = Robert Daniel Carmichael
doi = 10.1090/S0002-9904-1922-03504-5
id = MR|1560520
issue = 3
journal = Bulletin of the American Mathematical Society
pages = 109–110
title = Note on Euler's φ-function
volume = 28
year = 1922
.

*citation
last = Ford | first = K.
doi = 10.2307/121103
id = MR|1715326
issue = 1
journal = Annals of Mathematics
pages = 283–311
title = The number of solutions of φ("x") = "m"
volume = 150
year = 1999
.

*citation
last = Klee | first = V. L., Jr. | author-link = Victor Klee
doi = 10.1090/S0002-9904-1947-08940-0
id = MR|0022855
journal = Bulletin of the American Mathematical Society
pages = 1183–1186
title = On a conjecture of Carmichael
volume = 53
year = 1947
.

*citation
last1 = Schlafly | first1 = A.
last2 = Wagon | first2 = S.
doi = 10.2307/2153585
id = MR|1226815
issue = 207
journal = Mathematics of Computation
pages = 415–419
title = Carmichael's conjecture on the Euler function is valid below 1010,000,000
volume = 63
year = 1994
.

*mathworld|title=Carmichael's Totient Function Conjecture|urlname=CarmichaelsTotientFunctionConjecture

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Euler's totient function — For other functions named after Euler, see List of topics named after Leonhard Euler. The first thousand values of φ(n) In number theory, the totient φ(n) of a positive integer n is defined to be the number of positive integers less than or equal …   Wikipedia

• List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

• Liste de conjectures mathématiques — Ce qui suit est une liste de conjectures mathématiques, non exhaustive. Elles sont divisées en quatre sections, en accord avec leur état en 2011. Voir aussi : Conjecture d Erdős (en), qui liste des conjectures de Paul Erdős et de ses… …   Wikipédia en Français

• Indicatrice d'Euler — Les mille premières valeurs de φ(n) En mathématiques, l indicatrice d Euler est une fonction de la théorie des nombres. Elle intervient en mathématiques pures, à la fois en théorie des groupes, en théorie algébrique des nombres et en théorie… …   Wikipédia en Français

• Prime number — Prime redirects here. For other uses, see Prime (disambiguation). A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is… …   Wikipedia

• List of number theory topics — This is a list of number theory topics, by Wikipedia page. See also List of recreational number theory topics Topics in cryptography Contents 1 Factors 2 Fractions 3 Modular arithmetic …   Wikipedia