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

Also if m=pCarmichael'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 a 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
p_{1} < p_{2} < ··· < p_{j} of primes in S(n), together with corresponding non-negative integers γ_{1}, ... , γ_{j} as follows:

e_{1} = p_{1}^{γ1}(p_{1}-1) divides n_{0} = n;

e_{2} = p_{2}^{γ2}(p_{2}-1) divides n_{1} =n_{0}/e_{1};

···

e_{j} = p_{j}^{γj}(p_{j}-1) divides n_{j-1} =n_{j-2}/e_{j-1}.

Then e_{1}e_{2}···e_{j} divides n and with y =
p_{1}^{γ1+1}···p_{j}^{γj+1}, we have e_{1}e_{2}···e_{j} = φ(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 (p_{j},γ_{j},n_{j-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)

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

*Last modified 9th September 2010*

Return to number-theoretic functions page