Carmichael's totient function conjecture: Difference between revisions

Revision as of 22:24, 16 June 2010

Revision as of 07:08, 7 August 2010

Line 16:

Ford also proved 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.{{cn|date=December 2008pomerance}} 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 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

Line 76:

| url = http://jstor.org/stable/2153585

| publisher = Mathematics of Computation, Vol. 63, No. 207}}.

*{{citation

| last1 = Pomerance | first1 = Carl

| id = {{pomerance}}

| issue = 2

| journal = [[Proceedings of the American Mathematical Society]]

| pages = 297–298

| title = On Carmichael's conjecture

| volume = 43

| year = 1974

| url = http://www.math.dartmouth.edu/~carlp/PDF/carmichaelconjecture.pdf

| publisher = Proceedings of American Mathematical Society, Vol. 43, No. 2}}.

==External links==

*{{mathworld|title=Carmichael's Totient Function Conjecture|urlname=CarmichaelsTotientFunctionConjecture}}