Congruences Involving the Totient Function


For any integer n>1 let f(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 f(n) that don't seem to be mentioned in most of the standard reference texts.  For example,


Proposition 1:  If  n>6  then  f(n)/2 = 1 (mod 6)  iff  n = p2d  or  2p2d  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 pi are distinct primes and the ai are positive integers we have



Since we require f(n)/2 = 1 (mod 6), it's clear that f(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 pr or 2pr, 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 f(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 f(n)/2 to be congruent to 1 (mod 6) are that n be of the form p2d or 2p2d 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 2f(n)/2 = 3 (mod 6)  iff  n = pd   or   2pd  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 3f(n)/2 = 5 (mod 6)  iff  n = p2d-1  or  2p2d-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 f(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 f(n)/2 is odd and divisible by 3.)  Following is a tabulation of the residues (mod 6) of f(n)/2 for n ranging from 1 to 1000.























Similar congruences relations involving f(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 f(n)/2 = 1 modulo 2q.  By the same argument as given above, we know that n must be of the form pr or 2pr 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 3r-1 = 1 (mod 4q).  Now, the order of 3 (mod 4q) is a divisor of f(q). 


For example, if q = 5, the order of 3 is a divisor of f(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 f(pr) = f(2pr) = 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 f(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 72, 73, 74, ... etc, (and twice each of these numbers) satisfies the congruence f(n) = 7 (mod 14).  This is in addition to the obvious solutions of the form pd and 2pd where p = 2q+1 (mod 4q) and d is any integer.


Return to MathPages Main Menu