HMMT 二月 2022 · ALGNT 赛 · 第 10 题

10. Compute the smallest positive integer n for which there are at least two odd primes p such that n X ν ( k !) p ( − 1) < 0 . k =1 Note: for a prime p and a positive integer m , ν ( m ) is the exponent of the largest power of p that p divides m ; for example, ν (18) = 2. 3 Proposed by: Krit Boonsiriseth Answer: 229 P n ν ( k !) p Solution: Say n is p -good if ( − 1) < 0, where p is an odd prime. k =1 Claim. n is p -good iff k X 2 i +1 n + 1 = a p , i i =0 where a is an even integer with | a | < p . i i The proof of this claim will be deferred to the end of the solution as it is rather technical, and we P n ν ( k !) p believe that it would be more illuminating for the reader to graph the function n 7 → ( − 1) k =1 and examine its properties, instead of focusing on the formal proof. 2 k − 1 2 k A consequence of the claim is that if n is p -good then p divides n + 1, and p < n + 1 < p for

some k ∈ Z . 2 Now suppose n is p -good and q -good for distinct odd primes p < q . Then n + 1 ≥ pq > p , so we must 3 have n + 1 > p . Checking p = 3, the smallest potential n + 1’s are 3 • 2 · 3 − 2 · 3 = 48, which does not have a prime factor q > 3. 3 • 2 · 3 = 54, which does not have a prime factor q > 3. 3 • 2 · 3 + 2 · 3 = 60, which does not work because 60 is the wrong size for q = 5. 5 3 The next value 2 · 3 − 2 · 3 − 2 · 3 is already bigger than 230. Checking p = 5, the smallest potential n + 1’s are 3 • 2 · 5 − 4 · 5 = 230, which works for q = 23. 3 For p ≥ 7 , n + 1 ≥ p > 230 , so 229 is the smallest value of n . It suffices to prove the claim. We argue via a series of lemmas. We introduce the notation of S ( a, b ) = P b − 1 ν ( k !) p ( − 1) . Note that n is p -good if and only if S (0 , n + 1) ≤ 0. k = a 2 Lemma 1. If n ≤ p , S (0 , n ) is the distance to the nearest even multiple of p . 2 Proof. This follows straightforwardly from the fact that ν ( k !) = ⌊ k/p ⌋ for n ≤ p . p ν ( a ) ν ( a !) p p Lemma 2. If a and b are positive integers so that b ≤ p , then S ( a, a + b ) = ( − 1) S (0 , b ). Proof. Note that for 0 < k < b , ν ( a + k ) = ν ( k ), so it follows that ν (( a + k )!) = ν ( a !) + ν ( k !). The p p p p p result follows. 2 Lemma 3. For any nonnegative integer a , ν (( ap )!) is the same parity as ν ( a !). p p 2 Proof. Note that ν (( ap )!) − ν ( a !) = ap + a = a ( p + 1), which is even as p is odd. p p 2 2 ν ( a !) p Lemma 4. For a nonnegative integer a , S ( ap , ( a + 1) p ) = p ( − 1) . Proof. Combine Lemmas 1, 2, and 3. 2 Lemma 5. For a nonnegative integer a , S (0 , ap ) = pS (0 , a ). Proof. Apply Lemma 4 and sum. 2 2 ν ( a !) p Lemma 6. If a, b are nonnegative integers with b < p , then S (0 , ap + b ) = pS (0 , a )+( − 1) S (0 , b ). Proof. Combine Lemmas 2, 3, and 5. P k 2 i +1 We are now ready to prove the claim. Call a nonnegative integer neat if it can be written as a p i i =0 for integers a with | a | < p . For a nonnegative integer n , let P ( n ) be the following statements: i i • S (0 , n ) ≥ 0. • S (0 , n ) = 0 if and only if n is neat. In this case, ν ( n !) is even. p • S (0 , n ) = 1 if and only if n + 1 is neat or n − 1 is neat. If n + 1 is neat, then ν ( n !) is odd. If p n − 1 is neat, then ν ( n !) is even. p It suffices to show P ( n ) for all n , which we will prove by induction on n . The base case of n = 0 is obvious. 2 2 Now take some n > 0 and suppose n = ap + b for 0 ≤ b < p . Lemma 6 tells us that S (0 , n ) = ν ( a ) p pS (0 , a ) + ( − 1) S (0 , b ). Since 0 ≤ S (0 , b ) ≤ p (by Lemma 1), the only way for S (0 , n ) to be less ν ( a ) p than 0 is if S (0 , a ) = 0 and ( − 1) = − 1, which is impossible since P ( a ) holds. There are two ways for S (0 , n ) = 0 to be true. The first case is that S (0 , a ) = S (0 , b ) = 0, which implies by P ( a ) and Lemma 1 that a is neat and b is a multiple of 2 p . This captures the neat numbers 2 with a ≥ 0. Note that in this case ν ( n !) = ν (( ap )!) + ν ( b !) (by the same logic as Lemma 2), which 0 p p p 2 is even as ν (( ap )!) is even by P ( a ) and Lemma 3 and ν ( b !) = b/p which is even. p p ν ( a !) p The second way for S (0 , n ) to be 0 is if S (0 , a ) = 1, S (0 , b ) = p , and ( − 1) = − 1. By the inductive hypothesis, this is equivalent to a + 1 being neat and b being an odd multiple of p . This captures 2 exactly the neat numbers with a < 0. Also, ν ( n !) = ν (( ap )!) + ν ( b !), which is even as ν ( a !) is 0 p p p p odd and ν ( b !) is odd. p Analyzing the possibilities where S (0 , n ) = 1 is almost exactly the same as the above, so we will omit it here. We encourage the reader to fill in the details.