Carmichael's totient function conjecture: Difference between revisions

Revision as of 23:08, 1 April 2010

Revision as of 23:23, 1 April 2010

Line 1:

In mathematics, '''Carmichael's totient function conjecture''' concerns the [[Multiplicity (mathematics)|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 Daniel Carmichael|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.

==Examples==

ThisThe totient function φ(''n'') is equal to 2 when ''n'' is one of the three values 3, 4, and 6. ItThus, isif equalwe totake 4 when ''n'' isany one of thethese fourthree values 5, 8, 10, and 12. It is equal to 6 whenas ''n'', isthen oneeither of the fourother two values 7,can 9,be 14,used andas 18.the In''m'' eachfor case, there is more than one value ofwhich φ(''nm'' having the same value of ) = φ(''n'').

TheSimilarly, conjecturethe statestotient thatis thisequal phenomenonto 4 when ''n'' is one of repeatedthe four values holds5, for8, every10, ''n''.and 12, and Thatit is, forequal to 6 everywhen ''n'' is one of the four values 7, 9, 14, and 18. In each case, there is atmore leastthan one othervalue integerof ''m'' ≠ ''n'' suchhaving thatthe same value of φ(''m'') = φ(''n'').

[[Robert Daniel Carmichael|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.

The conjecture states that this phenomenon of repeated values holds for every ''n''.

Carmichael 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 10³⁷, and [[Victor Klee]] extended this result to 10⁴⁰⁰. Carmichael's conjecture has since been verified computationally for all ''n'' less than or equal to 10^10⁷ by Schlafly and Wagon. The current lower bound for a counterexample to the Conjecture is 10^10¹⁰, 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.

==Lower bounds==

There are very high [[lower bound]]s 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 10³⁷, and [[Victor Klee]] extended this result to 10⁴⁰⁰. Carmichael'sA conjecturelower hasbound since been verified computationally for all ''n'' less than or equal toof 10^10⁷ was given by Schlafly and Wagon., Theand currenta lower bound for a counterexample to the Conjecture isof 10^10¹⁰, 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'sThe Conjecturecomputational istechnique oneunderlying of the first among open problems with very highthese lower bounds and which are relatively easy to determine. The computational technique basically depends on some key results of Klee whichthat makesmake 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 2^''k''</sup>+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==

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 its totient value. Klee's results imply that 8 and Fermat primes (primes of the form 2^''k''</sup>+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).

Ford also proved that if there exists a counterexample to the Conjecture, then a positive fraction (that is infinitely many) of the integers are likewise counterexamples.

Although the conjecture is widely believed, [[Carl Pomerance]] gave a sufficient condition for an integer ''n'' to be a counterexample to the conjecture.{{cn|date=December 2008}} According to this condition, ''n'' is a counterexample if for every prime ''p'' such that ''p''&nbsp;&minus;&nbsp;1 divides &phi;(''n''), ''p''² 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</sup>, 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.