Carmichael's totient function conjecture: Difference between revisions

Revision as of 00:35, 8 January 2019

Revision as of 01:24, 8 January 2019

Line 136:

==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 <math>10^{10^7}</math>was given by Schlafly and Wagon, and a lower bound of <math>10^{10^{10}}</math> was determined by [[Kevin Ford (mathematician)|Kevin Ford]] in 1998.<ref name=HBII228>Sándor & Crstici (2004) p.&nbsp;228</ref>

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''&nbsp;+&nbsp;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&nbsp;4&nbsp;(mod&nbsp;8).