Carmichael's totient function conjecture: Difference between revisions

Revision as of 20:31, 15 December 2018

Latest revision as of 17:54, 27 March 2024

(16 intermediate revisions by 15 users not shown)

Line 1:

{{Short description|Problem in number theory on equal totients}}

In mathematics, '''Carmichael's totient function conjecture''' concerns the [[Multiplicity (mathematics)|multiplicity]] of values of [[Euler's totient function]] ''φ''(''n''), which counts the number of integers less than and [[coprime]] to ''n''. It states that, 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 (mathematics)|conjecture]] in 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]].

==Examples==

Line 10 ⟶ 12:

{|class="wikitable"

|''nk''

|numbers ''kn'' such that ''φ''(''kn'') = ''nk'' {{OEIS|id=A032447}}

|number of such ''kn''s {{OEIS|id=A014197}}

|-

|1

Line 136 ⟶ 138:

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

==Other results==

Ford also proved that if there exists a counterexample to the Conjectureconjecture, then a positive fractionproportion (thatin isthe infinitelysense manyof asymptotic density) of the integers are likewise counterexamples.<ref name=HBII228/>

Although the conjecture is widely believed, [[Carl Pomerance]] gave a sufficient condition for an integer ''n'' to be a counterexample to the conjecture {{harv|Pomerance|1974}}. 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&nbsp;''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&nbsp;1&nbsp;(mod&nbsp;''q'') (where ''q'' is a prime) are all less than ''q''^''k''+1, 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 Conjectureconjecture. However if it exists then infinitely many counterexamples exist as asserted by Ford.

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

Line 161 ⟶ 163:

| volume = 13

| year = 1907

| mr = 1558451}}.| doi-access = free

}}.

*{{citation

| last = Carmichael | first = R. D. | author-link = Robert Daniel Carmichael

Line 171 ⟶ 174:

| volume = 28

| year = 1922

| mr = 1560520}}.| doi-access = free

}}.

*{{citation

| last = Ford | first = K. | author-link = Kevin Ford (mathematician)

| doi = 10.2307/121103

| issue = 1

Line 185 ⟶ 189:

* {{citation |last=Guy | first=Richard K. | authorlink=Richard K. Guy | title=Unsolved problems in number theory | publisher=[[Springer-Verlag]] |edition=3rd | year=2004 |isbn=978-0-387-20860-2 | zbl=1058.11001 | at=B39 }}.

*{{citation

| last = Klee | first = V. L., Jr. | author-link = Victor Klee

| doi = 10.1090/S0002-9904-1947-08940-0

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

Line 193 ⟶ 197:

| year = 1947

| mr = 0022855 | zbl=0035.02601

| issue = 12}}.| doi-access = free

}}.

*{{citation

| last1 = Pomerance | first1 = Carl | author-link = Carl Pomerance

Line 204 ⟶ 209:

| zbl=0254.10009

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

| doi=10.2307/2038881| jstor = 2038881 }}.

* {{citation | last1=Sándor | first1=Jozsef | last2=Crstici | first2=Borislav | title=Handbook of number theory II | ___location=Dordrecht | publisher=Kluwer Academic | year=2004 | isbn=978-1-4020-2546-74 | zbl=1079.11001 | pages=228–229 }}.

*{{citation

| last1 = Schlafly | first1 = A.

Line 220 ⟶ 225:

==External links==

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

[[Category:Multiplicative functions]]

[[Category:Conjectures]]

[[Category:Unsolved problems in number theory]]