HMMT 二月 2016 · 冲刺赛 · 第 26 题

英文解析

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 .
    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 andr ra ↑↑ ( k + 1) are distinct mod p , then a ↑↑ ( k − 1) and a ↑↑ k must be distinct mod φ ( p ). In fact theyrφ ( p )
    need to be distinct mod if p = 2 and r ≥ 3 because then there are no primitive roots mod p .r
    Using this, for 1 ≤ k ≤ 5 we find the smallest prime p such that there exists a such that a ↑↑ k and 2
    a ↑↑ ( k + 1) are distinct mod p . The list is: 3 , 5 , 11 , 23 , 47. We can easily check that the next largestprime for k = 5 is 139, and also any prime power other than 121 for which a ↑↑ 5 and a ↑↑ 6 aredistinct 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 iseither 121 or 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 canr 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 ispossible by the Chinese Remainder theorem, and it is easy to see that this a works by induction.