2018 USAMO Problems/Problem 3

Problem 3

For a given integer let be the set of positive integers less than that are relatively prime to Prove that if every prime that divides also divides then is divisible by for every positive integer

Solution (NO FORMATTING)

https://maa.org/sites/default/files/pdf/AMC/usamo/2018/2018USAMO.pdf The integer m in the statement of the problem is ϕ(n), where ϕ is the Euler totient function. Throughout our proof we write p s || 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 p s divides n for some positive integer s, then 1k + 2k + · · · + n k is divisible by p s−1 for any integer k ≥ 1. 2018 USAMO – Solutions 4 Proof. Let {a1, a2, . . . , am} be a complete reduced residue set modulo p s and m = p s−1 (p − 1). First we prove by induction on s that for any positive integer k, a k 1 + a k 2 + · · · + a k m is divisible by p s−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 p s+1. Therefore, the desired sum of k-th powers is equal to a k 1 + · · · + a k m + · · · + (p s (p − 1) + a1) k + · · · + (p s (p − 1) + am) k ≡ p(a k 1 + · · · + a k m) ≡ 0 (mod p s ), 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 p s , it is enough to show that 1k + 2k +· · · + (p s ) k is divisible by p s−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 1 k + 2k + · · · + (p s ) k = a k 1 + a k 2 + · · · + a k m + p k � 1 k + 2k + · · · + (p s−1 ) k � is divisible by p s−1 , because p s−1 | a k 1 + · · · + a k m and by the induction hypothesis p s−2 | 1 k + · · · + (p s−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 mod n, and define s by p s || m. Then p s divides a k 1 + · · · + a k m 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 = p s+1 , m = p s (p − 1), and we proved in Lemma 1 that a k 1 +· · ·+a k m is divisible by p s . 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 p s || ϕ(n) and p s || ϕ(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 a k 1 + · · · + a k m + · · · + (n(q − 1) + a1) k + · · · + (n(q − 1) + am) k = mnk � 1 k + · · · + (q − 1)k � + 2018 USAMO – Solutions 5 � k 1 � n k−1 � 1 k−1 + · · · + (q − 1)k−1 � (a1 + · · · + am) + · · · + q(a k 1 + · · · + a k m). This sum is divisible by p s because p s || m and p s | a j 1 + a j 2 + · · · + a j m for any positive integer j. Case 2. q doesn’t divide n. Suppose p b || q − 1, where b ≥ 0. Note that ϕ(nq) = ϕ(n)(q − 1), so p s || ϕ(n) and p s+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 a k 1 + · · · + a k m + · · · + (n(q − 1) + a1) k + · · · + (n(q − 1) + am) k − q k (a k 1 + · · · + a k m) = mnk � 1 k + · · · + (q − 1)k � + � k 1 � n k−1 � 1 k−1 + · · · + (q − 1)k−1 � (a1 + · · · + am) + · · · · · · + � k k − 1 � n (1 + · · · + (q − 1)) (a k−1 1 + · · · + a k−1 m ) + q(a k 1 + · · · + a k m) − q k (a k 1 + · · · + a k m). Each term � k j � n k−j � 1 k−j + · · · + (q − 1)k−j � (a j 1 + · · · + a j m), for 0 ≤ j ≤ k − 1, is divisible by p s+b because p | n k−j , p s | a j 1 + · · · + a j m, and p b−1 | 1 k−j + · · · + (q − 1)k−j by Lemma 1. Also (q k − q)(a k 1 + · · · + a k m) is divisible by p s+b because p b | q − 1 | q k − q and p s | a k 1 + · · · + a k m. Thus p s+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 a k 1 + a k 2 + · · · + a k m is divisible by m for every positive integer k, then every prime that divides m also divides n. The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

2018 USAMO (Problems • Resources)
Preceded by Problem 2	Followed by Problem 4
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions