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 2: f(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 3: f(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.
--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 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.