HMMT 十一月 2015 · 团队赛 · 第 10 题

英文解析

10. [ 7 ] A number n is bad if there exists some integer c for which x ≡ c (mod n ) has no integer solutionsfor x . Find the number of bad integers between 2 and 42 inclusive.
    Proposed by: Sam Korsky
    Answer: 25
    Call a number good if it is not bad . We claim all good numbers are products of distinct primes, noneof which are equivalent to 1 modulo another.
    We first show that all such numbers are good . Consider n = p p . . . p , and let x be a number satisfying
    1 2 kx ≡ c (mod p p . . . p ) and x ≡ 1 (mod ( p − 1)( p − 1) . . . ( p − 1)). Since, by assumption, p p . . . p
    1 2 k 1 2 k 1 2 kx 1
    and ( p − 1)( p − 1) . . . ( p − 1) are relatively prime, such an x must exist by CRT. Then x ≡ c = c
    1 2 k
    (mod n ), for any c , as desired.
    We now show that all other numbers are bad . Suppose that there exist some p , p | n such that
    1 2
    gcd( p , p − 1) 6 = 1 (which must hold for some two primes by assumption), and hence gcd( p , p − 1) = p .
    1 2 1 2 1
    Consider some c for which p c is not a p th power modulo p , which must exist as p c can take any
    1 1 2 1
    value modulo p (as p , p are relatively prime). We then claim that x ≡ p c (mod n ) is not solvable.x
    2 1 2 1
    x x
    Since p p | n , we have x ≡ p c (mod p p ), hence p | x . But then x ≡ p c is a p th power modulo
    1 2 1 1 2 1 1 1
    p as p | x , contradicting our choice of c . As a result, all such numbers are bad .
    2 1
    Finally, it is easy to see that n is bad if it is not squarefree. If p divides n twice, then letting c = p
    1 1
    makes the given equivalence unsolvable.
    Hence, there are 16 numbers (13 primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41; and 3 semiprimes:
    3 · 5 = 15, 3 · 11 = 33, 5 · 7 = 35) that are good , which means that 41 − 16 = 25 numbers are bad .