PUMaC 2023 · 数论（B 组） · 第 8 题
PUMaC 2023 — Number Theory (Division B) — Problem 8
题目详情
- How many positive integers n ≤ lcm(1 , 2 , . . . , 100) have the property that n gives different remainders when divided by each of 2 , 3 , . . . , 100? Name: Team: Write answers in table below: Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 1
解析
- How many positive integers n ≤ lcm(1 , 2 , . . . , 100) have the property that n gives different remainders when divided by each of 2 , 3 , . . . , 100? Proposed by Daniel Zhu Answer: 1025 Observe that, of the remainders 0 , 1 , ..., 99, exactly one will not be used. Moreover, notice that choosing a remainder for each integer 2 , 3 , ..., 100 uniquely determines n ≤ lcm(1 , 2 , ..., 100) by Chinese Remainder Theorem. If 0 isn’t the excluded remainder, let a be the unique number that n leaves a remainder of 0 divided by, so a | n . Clearly, a must be prime, as otherwise n would also leave a remainder when divided by a factor of a greater than 1. Assume for now that a > 2. Considering the remainders of n modulo 2 , 3 , 4 , ..., a − 1, we note that they are fixed; because 0 is already used modulo a , the only possible remainder modulo 2 is 1; since 0 and 1 are already used, the only possible remainder modulo 3 is 2, and so on. Looking at n (mod a + 1), because a is prime a + 1 isn’t, so by Chinese Remainder Theorem n must be − 1 modulo the factors of a + 1 meaning n ≡ a (mod a + 1). Now, if 2 a ≤ 100, because a | n we must have that n modulo 2 a is either 0 or a , contradiction as both of these remainders have already used. Thus, a must be a prime between 50 and 100. Now, suppose that n is odd, meaning n ≡ 1 (mod 2). We claim that n ≡ k − 1 (mod k ) for all 2 ≤ k ≤ 100 such that k is not a prime between 50 and 100. This follows by strong induction. The base case k = 2 holds by assumption. Then, for higher k , if k is composite then by Chinese Remainder Theorem on its factors and the inductive hypothesis we have n ≡ − 1 (mod k ). Contrarily, if k is prime, by induction the possible unused remainders are 0 and k − 1, but we showed earlier that if 0 is a remainder it must be mod 2 or a prime greater than 50, so it can’t be the remainder of n modulo k . This establishes the claim. Next, let p < p < · · · < p denote the primes between 50 and 100. We thus want to find the number 1 2 10 of ways to allocate all but one of the elements in the set { 0 } ∪ { p − 1 , ..., p − 1 } as remainders 1 10 of n modulo the elements in { p , ..., p } . Assigning the remainder to p first, then p , etc., up 1 10 1 2 10 to p , note there are two choices at each step, for a total of 2 distinct allocations. 10 The remaining case is that n is even; we claim this forces n ≡ k − 2 (mod k ) for all 2 ≤ k ≤ 100. But, we see by induction the even remainders are fixed, and then by induction again for odds k we see that k − 1 , k − 2 are the only possible remainders, but k − 1 is the remainder modulo the even number k + 1, so it must be k − 2. Thus, this contributes one additional possible 10 value for n , making our answer 2 + 1 = 1025. 4