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 = 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 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 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 (p1)/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 (p1)/2 is congruent to either +2 or 1 (mod 6). However, considering the requirement 

_{} 

it's clear that (p1)/2 must be congruent to 1 (mod 6). From this is follows that (1)^{r1} 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 p^{2d} or 2p^{2d} where d is a positive integer and p is a prime such that (p1)/2 is congruent to 1 modulo 6. Since (p1)/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: f(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: f(n)/2 = 5 (mod 6) iff n = p^{2d1} or 2p^{2d1} 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. 

112132325203442334055440302432420003022034055234 
40232002520304043440500020003432502342200405040302 
24300250020020240504104020320052030224304500200022 
30000003420334455002002404425000020024005200002034 
02022300003445000004003002500202202400520130040042 
50234420000554204020340242030024340000420020200204 
03400030005000002424400003020434050000440030425200 
02242405503020003400000242003005540000202042000302 
20040004024000200050030244040050004000320050234020 
24050000042034025002020000055400020330005220000434 
45502200240202002040203405021200042042000302003404 
04000020004252230220304040040400200250024020040052 
00004430000003402030050040000030020202022430005020 
00202400520302002400000000240240502300043405042040 
20044202020200044550030042303000030200300050200404 
34400003402004050200402000020022000434400000402024 
02000042203000020004243020500200002005504040000404 
02000220300550202004000000034420304550020004200200 
22020034005020000032020003022004452000042024005000 
40202445023000003400500300202005542200003000020302 

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 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 (p1)/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 4k1. Of course, p and p1 must also be coprime 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^{r1} = 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(p^{r}) = f(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 111 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 (q1)/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^{2}, 7^{3}, 7^{4}, ... 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 p^{d} and 2p^{d} where p = 2q+1 (mod 4q) and d is any integer. 
