Carmichael's totient function conjecture: Difference between revisions

Revision as of 21:26, 25 August 2011

Revision as of 19:44, 13 December 2011

Line 10:

==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 &phi;(''n'') is different from the totients of all other numbers) must be at least 10³⁷, and [[Victor Klee]] extended this result to 10⁴⁰⁰. A lower bound of 10<supmath>10^{^{10^7}</supmath>} was given by Schlafly and Wagon, and a lower bound of 10<supmath>10^{^{10^{10}}}</supmath> was determined by Kevin Ford in 1998.

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 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).