Problem:
For a given integer n≥2, let a1​,a2​,…,am​ be the set of positive integers less than n that are relatively prime to n. Prove that if every prime that divides m also divides n, then a1k​+a2k​+⋯+amk​ is divisible by m for every positive integer k.
Solution:
The integer m in the statement of the problem is φ(n), where φ is the Euler totient function. Throughout our proof we write ps∥m, if s is the greatest power of p that divides m.
We begin with the following lemma:
Lemma 1. If p is a prime and ps divides n for some positive integer s, then 1k+2k+⋯+nk is divisible by ps−1 for any integer k≥1.
Proof. Let a1​,a2​,…,am​ be a complete reduced residue set modulo ps and m=ps−1(p−1). First we prove by induction on s that for any positive integer k,a1k​+a2k​+⋯+amk​ is divisible by ps−1. The base case s=1 is true. Suppose the statement holds for some value of s. Consider the statement for s+1. Note that
{a1​,…,am​,ps+a1​,…,ps+am​,…,ps(p−1)+a1​,…,ps(p−1)+am​}
is a complete reduced residue set modulo ps+1. Therefore, the desired sum of k-th powers is equal to
a1k​+⋯+amk​+⋯+(ps(p−1)+a1​)k+⋯+(ps(p−1)+am​)k≡p(a1k​+⋯+amk​)≡0(modps),
where we have used the induction hypothesis for the second congruence. This gives the induction step.
Now we are ready to prove the lemma. Because numbers from 1 to n can be split into blocks of consecutive numbers of length ps, it is enough to show that 1k+2k+⋯+(ps)k is divisible by ps−1 for any positive integer k. We use induction on s. The statement is true for s=1. Assume the statement is true for s−1. The sum
1k+2k+⋯+(ps)k=a1k​+a2k​+⋯+amk​+pk(1k+2k+⋯+(ps−1)k)
is divisible by ps−1, because ps−1∣a1k​+⋯+amk​ and by the induction hypothesis ps−2∣1k+⋯+ (ps−1)k.
Now we proceed to prove a second lemma, from which the statement of the problem will immediately follow:
Lemma 2. Suppose p is a prime dividing n. Let a1​,…,am​ be a complete reduced residue set modn, and define s by ps∥m. Then ps divides a1k​+⋯+amk​ for any integer k≥1.
Proof. We fix p, and use induction on the number of prime factors of n (counted by multiplicity) that are different from p. If there are no prime factors other than p, then n=ps+1,m=ps(p−1), and we proved in Lemma 1 that a1k​+⋯+amk​ is divisible by ps. Now suppose the statement is true for n. We show that it is true for nq, where q is a prime not equal to p.
Case 1. q divides n. We have ps∥φ(n) and ps∥φ(nq), because φ(nq)=qφ(n). If a1​,a2​,…,am​ is a complete reduced residue set modulo n, then
{a1​,…,am​,n+a1​,…,n+am​,…,n(q−1)+a1​,…,n(q−1)+am​}
is a complete reduced residue set modulo nq. The new sum of k-th powers is equal to
a1k​+⋯+amk​+⋯+(n(q−1)+a1​)k+⋯+(n(q−1)+am​)k=mnk(1k+⋯+(q−1)k)+
(1k​)nk−1(1k−1+⋯+(q−1)k−1)(a1​+⋯+am​)+⋯+q(a1k​+⋯+amk​)
This sum is divisible by ps because ps∥m and ps∣a1j​+a2j​+⋯+amj​ for any positive integer j.
Case 2. q doesn't divide n. Suppose pb∥q−1, where b≥0. Note that φ(nq)=φ(n)(q−1), so ps∥φ(n) and ps+b∥φ(nq). Let {a1​,…,am​} be a complete reduced residue set modulo n. The complete reduced residue set modulo nq consists of the mq numbers
{a1​,…,am​,n+a1​,…,n+am​,…,n(q−1)+a1​,…,n(q−1)+am​}
with the m elements qa1​,qa2​,…,qam​ removed.
The new sum of k-th powers is equal to
a1k​+⋯+amk​+⋯+(n(q−1)+a1​)k+⋯+(n(q−1)+am​)k−qk(a1k​+⋯+amk​)=mnk(1k+⋯+(q−1)k)+(1k​)nk−1(1k−1+⋯+(q−1)k−1)(a1​+⋯+am​)+⋯⋯+(k−1k​)n(1+⋯+(q−1))(a1k−1​+⋯+amk−1​)+q(a1k​+⋯+amk​)−qk(a1k​+⋯+amk​)​
Each term
(jk​)nk−j(1k−j+⋯+(q−1)k−j)(a1j​+⋯+amj​)
for 0≤j≤k−1, is divisible by ps+b because p∣∣∣​nk−j,ps∣∣∣​a1j​+⋯+amj​, and pb−1∣1k−j+⋯+ (q−1)k−j by Lemma 1 .
Also (qk−q)(a1k​+⋯+amk​) is divisible by ps+b because pb∣q−1∣qk−q and ps∣a1k​+⋯+amk​. Thus ps+b divides our sum and our proof is complete.
Remark. In fact, one can also show the converse statement: if a1​,a2​,…,am​ is as defined in the problem and a1k​+a2k​+⋯+amk​ is divisible by m for every positive integer k, then every prime that divides m also divides n.
The problems on this page are the property of the MAA's American Mathematics Competitions