Carmichael's totient function conjecture: Difference between revisions

Revision as of 03:47, 9 July 2021

Latest revision as of 17:54, 27 March 2024

(5 intermediate revisions by 4 users not shown)

Line 1:

{{shortShort description|mathematicsProblem conceptin 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'').

Line 143:

==Other results==

Ford also proved that if there exists a counterexample to the Conjectureconjecture, then a positive proportion (in the sense of 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 177:

}}.

*{{citation

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

| doi = 10.2307/121103

| issue = 1

Line 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 225:

==External links==

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

[[Category:Multiplicative functions]]