Solving φ(x)=n, where φ(x) is Euler's totient function - testing Carmichael's conjecture

Euler's function φ(m) is the number of integers x, 1 ≤ x ≤ m satisfying gcd(x,m)=1. Thus

φ(1)=1, φ(2)=1, φ(3)=2, φ(4)=2, φ(5)=4, φ(6)=2, φ(7)=6, φ(8)=4, φ(9)=6, φ(10)=4.

Also if m=p1a1⋯ptat is the prime-power factorization of m, then φ(m)=p1a1-1(p1-1)⋯ptat-1(pt-1).

Carmichael's Totient Function Conjecture (1922, first stated in reference 6 below) states that Euler's function takes each value at least twice.

In April 1997, Anthony J. Towns, then a student in my MP206 class, wrote an amazingly clever C program for solving φ(x)=n and which also finds the y > 1 such that φ(y) divides n.

The BCMATH and BC versions start by determining the primes p such that p-1 divides n. The algorithm then traverses the tree described in section 4 of reference 1 below, from left to right.

One limitation of our implementation is the use of a primitive factoring program which uses the Brent-Pollard algorithm and Pollard's p-1 algorithm. It should work on integers with no more than 20 digits. See the CALC version that works on larger numbers.

e=0 determines solubility and prints out all solutions x of φ(x)=n, while e=1 tests Carmichael's conjecture.
f=0 determines solubility and prints out all solutions y of φ(y) divides n, while f=1 prints only the x satisfying φ(x)=n.

The algorithm deals with the set S(n) of primes p such that p-1 divides n. It produces sequences p1 < p2 < ··· < pj of primes in S(n), together with corresponding non-negative integers γ1, ... , γj as follows:
e1 = p1γ1(p1-1) divides n0 = n;
e2 = p2γ2(p2-1) divides n1 =n0/e1;
···
ej = pjγj(pj-1) divides nj-1 =nj-2/ej-1.
Then e1e2···ej divides n and with y = p1γ1+1···pjγj+1, we have e1e2···ej = φ(y) divides n.

Either a branch ends with a y such that φ(y) < n, or a y with φ(y) = n

Here is the tree when n = 8, traversed from left to right. The solutions y, apart from 1, such that φ(y) divides 8, are listed, as are the corresponding (pj,γj,nj-1):

2, 6, 30 10, 4, 12, 20, 8, 24, 16, 3, 15, 5,

with the boldfaced integers being the solutions x of φ(x)=8.

(2,0,8)     →    (2,1,4)      →     (2,2,2)    →    (2,3,1)    →    (3,0,4)    →    (5,0,2)
   ↓↑↘↖            ↓↑ ↘↖            ↓↑                                       ↓↑
   ↓↑    ↘↖        ↓↑     ↘↖        ↓↑                                       ↓↑
(3,0,4) (5,0,2) (3,0,2)  (5,0,1)  (3,0,1)                                (5,0,1)
   ↓↑
(5,0,1)

References

  1. Complexity of inverting the Euler function, Scott Contini, Ernie Croot and Igor Shparlinski, Math. Comp 75 (2006) 983-996.
  2. The number of solutions of φ(x) = m, Kevin Ford, Annals of Math. 150 (1999), 283-311.
  3. Carmichael's conjecture on the Euler function is valid below 1010,900,000, Aaron Schafly and Stan Wagon, Math. Comp. 63 (1994) 415-419.
  4. On Carmichael's conjecture, Carl Pomerance, Proc. Amer. Math. Soc. 43 (1974) 297-298.
  5. Sur l'equation φ(x)=m, André Schinzel, Elemente der Mathematik, 11 (1956) 75-78.
  6. On a conjecture of Carmichael, V.L. Klee Jr., Bull. Amer. Math. Soc. 53 (1947) 1183-1186.
  7. Note on Euler's φ-function, R.D. Carmichael, Bull. Amer. Math. Soc. 28 (1922) 109-110.
  8. On Euler's φ-function, R.D. Carmichael, Bull. Amer. Math. Soc. 28 (1907) 241-243.
Enter n (≥ 1):
Enter e (0 or 1):
Enter f (0 or 1):

Last modified 9th September 2010
Return to number-theoretic functions page