HMMT 十一月 2015 · 团队赛 · 第 10 题
HMMT November 2015 — Team Round — Problem 10
题目详情
- [ 7 ] A number n is bad if there exists some integer c for which x ≡ c (mod n ) has no integer solutions for x . Find the number of bad integers between 2 and 42 inclusive.
解析
- [ 7 ] A number n is bad if there exists some integer c for which x ≡ c (mod n ) has no integer solutions for 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, none of 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 k x ≡ 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 k x 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 x value modulo p (as p , p are relatively prime). We then claim that x ≡ p c (mod n ) is not solvable. 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 .