φ(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 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
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)
↓↑↘↖ ↓↑ ↘↖ ↓↑   ↓↑
↓↑ ↘↖ ↓↑ ↘↖ ↓↑   ↓↑
(3,0,4) (5,0,2) (3,0,2) (5,0,1) (3,0,1) (5,0,1)
Last modified 9th September 2010
Return to number-theoretic functions page