Carmichael's totient function conjecture: Difference between revisions

Revision as of 12:11, 4 September 2008

Revision as of 21:58, 12 September 2008

Line 5:

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 φ(''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.

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.

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