HMMT 二月 2016 · 冲刺赛 · 第 26 题
HMMT February 2016 — Guts Round — Problem 26
题目详情
- [ 14 ] For positive integers a, b , a ↑↑ b is defined as follows: a ↑↑ 1 = a , and a ↑↑ b = a if b > 1. Find the smallest positive integer n for which there exists a positive integer a such that a ↑↑ 6 6 ≡ a ↑↑ 7 mod n .
解析
- [ 14 ] For positive integers a, b , a ↑↑ b is defined as follows: a ↑↑ 1 = a , and a ↑↑ b = a if b > 1. Find the smallest positive integer n for which there exists a positive integer a such that a ↑↑ 6 6 ≡ a ↑↑ 7 mod n . Proposed by: Sammy Luo Answer: 283 We see that the smallest such n must be a prime power, because if two numbers are distinct mod n , they must be distinct mod at least one of the prime powers that divide n . For k ≥ 2, if a ↑↑ k and r r a ↑↑ ( k + 1) are distinct mod p , then a ↑↑ ( k − 1) and a ↑↑ k must be distinct mod φ ( p ). In fact they r φ ( p ) r need to be distinct mod if p = 2 and r ≥ 3 because then there are no primitive roots mod p . 2 Using this, for 1 ≤ k ≤ 5 we find the smallest prime p such that there exists a such that a ↑↑ k and a ↑↑ ( k + 1) are distinct mod p . The list is: 3 , 5 , 11 , 23 , 47. We can easily check that the next largest prime for k = 5 is 139, and also any prime power other than 121 for which a ↑↑ 5 and a ↑↑ 6 are distinct is also larger than 139. Now if a ↑↑ 6 and a ↑↑ 7 are distinct mod p , then p − 1 must be a multiple of 47 or something that is either 121or at least 139. It is easy to see that 283 is the smallest prime that satisfies this. If n is a prime power less than 283 such that a ↑↑ 6 and a ↑↑ 7 are distinct mod n , then the prime can r r − 1 be at most 13 and clearly this doesn’t work because φ ( p ) = p ( p − 1). To show that 283 works, choose a so that a is a primitive root mod 283 , 47 , 23 , 11 , 5 and 3. This is possible by the Chinese Remainder theorem, and it is easy to see that this a works by induction.