Content deleted Content added
La Pianista (talk | contribs) m Added {{nofootnotes}} tag to article. using Friendly |
remove inane tag. The lack of footnotes is a stylistic issue; most of the facts in this article are clearly associated with specific references. Put a {{cn}} tag on one para that's less clear. |
||
Line 1:
In mathematics, '''Carmichael's totient function conjecture''' concerns the [[multiplicity]] of values of [[Euler's totient function]] φ(''n''), which counts the number of integers less than and [[coprime]] to ''n''.
Line 10 ⟶ 9:
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 it. Klee's results imply that 8 and Fermat primes (primes of the form 2<sup>''k''</sup></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).
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'' − 1 divides φ(''n''), ''p''<sup>2</sup> 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''<sup>''k''+1</sup></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.
Another way of stating Carmichael's conjecture is that, if
| |||