Carmichael's totient function conjecture: Difference between revisions

Revision as of 17:39, 17 September 2008

Revision as of 17:53, 17 September 2008

Line 7:

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.

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''&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 every prime and thus non-existent.

Another way of stating Carmichael's conjecture is that, if