Carmichael's totient function conjecture: Difference between revisions

Revision as of 05:06, 4 September 2008

Revision as of 05:44, 4 September 2008

Line 3:

This function φ(''n'') is equal to 2 when ''n'' is one of the three values 3, 4, and 6. It is equal to 4 when ''n'' is one of the four values 5, 8, 10, and 12. It is equal to 6 when ''n'' is one of the four values 7, 9, 14, and 18. In each case, there is more than one value of ''n'' having the same value of φ(''n'').

The conjecture assertsstates that this phenomenon of repeated values holds for every ''n''. That is, 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 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.

Carmichael proved that any counterexample to his conjecture (that is, a value ''n'' such that φ(''n'') is different from the totients of all other numbers) must be at least 10³⁷, and [[Victor Klee]] extended this result to 10⁴⁰⁰. Carmichael's conjecture has since been verified computationally for all ''n'' less than or equal to 10^10⁷ by Schlafly and Wagon.

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

A(''f'') denotes the number of positive integers ''n'' for which φ(''n'') = ''f'', then A(''f'') can never equal 1. Relatedly, [[Wacław Sierpiński]] conjectured that every positive integer other than 1 occurs as a value of A(''f''), a conjecture that was proven in 1999 by Kevin Ford.

==References==

*{{citation

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

| doi = 10.1090/S0002-9904-1907-01453-2

| id = {{MR|1558451}}

| issue = 5

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

| pages = 241–243

| title = On Euler's φ-function

| volume = 13

| year = 1907}}.

*{{citation

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

| doi = 10.1090/S0002-9904-1922-03504-5

| id = {{MR|1560520}}

| issue = 3

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

| pages = 109–110

| title = Note on Euler's φ-function

| volume = 28

| year = 1922}}.

*{{citation

| last = Ford | first = K.

| doi = 10.2307/121103

| id = {{MR|1715326}}

| issue = 1

| journal = [[Annals of Mathematics]]

| pages = 283–311

| title = The number of solutions of φ(''x'') = ''m''

| volume = 150

| year = 1999}}.

*{{citation

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

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

| id = {{MR|0022855}}

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

| pages = 1183–1186

| title = On a conjecture of Carmichael

| volume = 53

| year = 1947}}.

*{{citation

| last1 = Schlafly | first1 = A.

| last2 = Wagon | first2 = S.

| doi = 10.2307/2153585

| id = {{MR|1226815}}

| issue = 207

| journal = [[Mathematics of Computation]]

| pages = 415–419

| title = Carmichael's conjecture on the Euler function is valid below 10^10,000,000

| volume = 63

| year = 1994}}.

==External links==

*Weisstein, Eric W. "{{mathworld|title=Carmichael's Totient Function Conjecture." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/|urlname=CarmichaelsTotientFunctionConjecture.html}}

[[Category:Multiplicative functions]]