Congruences Involving the Totient Function

For any integer n>1 let ϕ(n) denote the number of positive integers less than and relatively prime to n.  This is called Euler's totient function.  There are some interesting congruences involving ϕ(n) that don't seem to be mentioned in most of the standard reference texts.  For example,

Proposition 1:  If  n>6  then  ϕ(n)/2 = 1 (mod 6)  iff  n = p^2d  or  2p^2d  where d is a positive integer and p is a prime congruent to 11 (mod 12).

Proof:  For any integer n > 6 with the prime factorization

where the p_i are distinct primes and the a_i are positive integers we have

Since we require ϕ(n)/2 = 1 (mod 6), it's clear that ϕ(n)/2 must be odd, and therefore n can have no more than one distinct odd prime divisor.  Also, while a single power of 2 in n has no effect on the totient of n, any additional power of 2 multiplies the totient by 2.  Hence, if n is greater than 6, it must be of the form p^r or 2p^r, where p is an odd prime (not equal to 3) and r is a positive integer.  It only remains to determine any restrictions on p and r imposed by the requirement that

Every odd prime other than 3 is congruent to either +1 or –1 modulo 6, but if p were congruent to +1 (mod 6) the quantity (p-1)/2 would be divisible by 3, which would prevent ϕ(n)/2 from being congruent to 1 (mod 6).  Therefore, p must be congruent to –1 modulo 6, from which it follows that (p-1)/2 is congruent to either +2 or –1 (mod 6).  However, considering the requirement

it's clear that (p-1)/2 must be congruent to -1 (mod 6).  From this is follows that (–1)^r–1 must be congruent to –1 (mod 6), so the exponent r must be even.  Consequently, the necessary and sufficient conditions for ϕ(n)/2 to be congruent to 1 (mod 6) are that n be of the form p^2d or 2p^2d where d is a positive integer and p is a prime such that (p-1)/2 is congruent to –1 modulo 6.  Since (p–1)/2 = –1 + 6j for some integer j, we have the equivalent condition p = –1 + 12j, viz, the prime p is congruent to 11 (mod 12).

Notice that the first part of the above proof applies to any odd residue modulo 6.  It isn't difficult to adapt the remainder of the argument to prove the following two propositions.

Proposition 2:  ϕ(n)/2 = 3 (mod 6)  iff  n = p^d   or   2p^d  where either d is a positive integer and p is a prime congruent to 7 (mod 12), or else p = 3 and d is an integer greater than 1.

Proposition 3:  ϕ(n)/2 = 5 (mod 6)  iff  n = p^2d–1  or  2p^2d–1  where d is a positive integer and p is a prime congruent to 11 (mod 12).

Together, these three propositions cover all odd residues of ϕ(n)/2 (mod 6).  (Notice that Proposition 2 includes the degenerate family of solutions with p = 3, because in that case the necessary and sufficient condition is just that ϕ(n)/2 is odd and divisible by 3.)  Following is a tabulation of the residues (mod 6) of ϕ(n)/2 for n ranging from 1 to 1000.

--112132325203442334055440302432420003022034055234

40232002520304043440500020003432502342200405040302

24300250020020240504104020320052030224304500200022

30000003420334455002002404425000020024005200002034

02022300003445000004003002500202202400520130040042

50234420000554204020340242030024340000420020200204

03400030005000002424400003020434050000440030425200

02242405503020003400000242003005540000202042000302

20040004024000200050030244040050004000320050234020

24050000042034025002020000055400020330005220000434

45502200240202002040203405021200042042000302003404

04000020004252230220304040040400200250024020040052

00004430000003402030050040000030020202022430005020

00202400520302002400000000240240502300043405042040

20044202020200044550030042303000030200300050200404

34400003402004050200402000020022000434400000402024

02000042203000020004243020500200002005504040000404

02000220300550202004000000034420304550020004200200

22020034005020000032020003022004452000042024005000

40202445023000003400500300202005542200003000020302

Similar congruences relations involving ϕ(n) can easily be determined for any modulus of the form 2q where q is an odd prime.  For example, suppose we wish to determine the integers n such that ϕ(n)/2 = 1 modulo 2q.  By the same argument as given above, we know that n must be of the form p^r or 2p^r for some odd prime p and positive integer r.  Hence we seek values of p and r such that

This shows that p and (p–1)/2 must both be odd, so the only possible residue classes for p are 3, 7, 11, 15, 19,..., i.e., numbers of the form of the form 4k-1.  Of course, p and p-1 must also be co-prime to q.  Multiplying through by 2, we have

We know that p is an odd residue modulo 4q, and it cannot be congruent to 1 or q.  It can, however, be congruent to 3 (assuming q is not 3), in which case the above congruence is

This is a solution for any value of r such that 3^r–1 = 1 (mod 4q).  Now, the order of 3 (mod 4q) is a divisor of ϕ(q). 

For example, if q = 5, the order of 3 is a divisor of ϕ(5) = 4.  Indeed we find that the powers of 3 modulo 20 are 1, 3, 9, 27, 1,..., so the order is exactly 4.  Hence for any prime p congruent to 3 (mod 20) we have ϕ(p^r) = ϕ(2p^r) = 1 (mod 20) if and only if r = 1, 5, 9, 13, ...1 + 4j.  The next possibility is that p is congruent to 7 modulo 4q, in which case we have the congruence

This is satisfied for r = 2, 6, 10,... 4j + 2.  For the next possible residue class (with q = 5) we can exclude 11 and 15 because 11-1 and 15 are both divisible by 5.  Therefore, the next residue class for p is 19, which leads to the congruence

In this case we must have r = 2, 4, 6, ..., 2j + 2, because the order of 19 (mod 5) is just 2.

The same approach can be used to find all the integers n such that ϕ(n)/2 = k (mod 2q) for any odd k, except that there is another class of solutions in the special case when k = q.  In this case we can set p = q, and the basic congruence condition can be written as

Dividing through by q, this gives

for an arbitrary integer j.  Hence the left hand side is only required to be an odd integer, which it is, provided (as always) that (q-1)/2 is odd, and that the exponent r is greater than or equal to 2.  For example, with q = 7, this implies that each of the numbers 7², 7³, 7⁴, ... etc, (and twice each of these numbers) satisfies the congruence ϕ(n) = 7 (mod 14).  This is in addition to the obvious solutions of the form p^d and 2p^d where p = 2q+1 (mod 4q) and d is any integer.

Return to MathPages Main Menu