HMMT 十一月 2025 · 团队赛 · 第 7 题

HMMT November 2025 — Team Round — Problem 7

[45] Let S be the set of all positive integers less than 143 that are relatively prime to 143. Compute the number of ordered triples ( a, b, c ) of elements of S such that a + b = c .

解析

[45] Let S be the set of all positive integers less than 143 that are relatively prime to 143. Compute the number of ordered triples ( a, b, c ) of elements of S such that a + b = c . Proposed by: Jacopo Rizzo Answer: 5940 2 Solution: Let n = 143. Let T be the set of all pairs ( x, y ) ∈ S with x + y relatively prime to n . Note that whenever x + y is relatively prime to n , so is ( n − x ) + ( n − y ) = 2 n − ( x + y ). Therefore, the elements of T can be paired up by pairing ( x, y ) with ( n − x, n − y ). Note that exactly one of x + y and 2 n − ( x + y ) is less than n , so exactly one of each such pair yields a triple ( x, y, z ) with x + y = z . Therefore, the answer is | T | / 2, so it suffices to compute | T | . By the Chinese Remainder Theorem, we can consider modulo 11 and modulo 13 independently. There are 10 choices for x modulo 11 (any nonzero residue). Once x is chosen, there are 9 choices for y modulo 11 (any nonzero residue except − x ), so there are 10 · 9 = 90 possibilities for x and y modulo