PUMaC 2017 · 数论（B 组） · 第 8 题
PUMaC 2017 — Number Theory (Division B) — Problem 8
题目详情
- Find the least positive integer N such that the only values of n for which 1 + N · 2 is prime are multiples of 12. 1
解析
- Let’s look at the period of powers of 2 modulo various odd primes p . If p = 3 then the period 0 2 0 4 is 2, since 2 ≡ 2 (mod 3). Similarly, p = 5 has period 4, since 2 ≡ 2 (mod 5). Why is this n n + P p useful? We know that if N · 2 + 1 ≡ 0 (mod p ) and p has period P then N · 2 + 1 ≡ 0 p as well. Thus we want to “cover” the nonzero modulo-12 residue classes with various primes. This will give us what we want: if we can find a prime p for each m a non-multiple of 12 such that there is 0 < r < 12 with m ≡ r (mod p ) then we will have succeeded. We use the following periods: P = 2 , P = 4 , P = 3 , P = 12. We start by placing the 3s to not cover 3 5 7 13 the 0 residue: 0 1 2 3 4 5 6 7 8 9 10 11 3 3 3 3 3 3 We now place the 5s as to be as non-redundant as possible, and also not cover the 0 residue: 0 1 2 3 4 5 6 7 8 9 10 11 3 5 3 3 5 3 3 5 3 We now have choices to place the 7s; the 13 will then be placed in the last remaining spot: 2 0 1 2 3 4 5 6 7 8 9 10 11 3 5 3 3 5 3 3 5 3 7 13 7 7 7 7 7 7 13 7 (The latter two rows are the two possibilities.) Thus we must solve the linear systems (using the Chinese Remainder Theorem) and choose the viable value that is least: 2 N ≡ − 1 (mod 3) 2 N ≡ − 1 (mod 3) 4 N ≡ − 1 (mod 5) 4 N ≡ − 1 (mod 5) 4 N ≡ − 1 (mod 7) 2 N ≡ − 1 (mod 7) 16 N ≡ − 1 (mod 13) 256 N ≡ − 1 (mod 13) = ⇒ N ≡ 901 (mod 1365) = ⇒ N ≡ 556 (mod 1365) N = 556 is the minimal value satisfying the desired property, and we are done. Problem written by Zack Stier If you believe that any of these answers is incorrect, or that a problem had multiple reasonable interpretations or was incorrectly stated, you may appeal at http://tinyurl.com/PUMaCappeal2017. All appeals must be in by 1 PM to be considered. 3