Skip to main content
OlympiadHQ

Browse · MathNet

Print

China Girls' Mathematical Olympiad

China number theory

Problem

Let be a subset of elements of , , such that for any , there exists with . Find all possible values of .
Solution
Let . As satisfies also the hypothesis, we may assume without loss of generality that . For any , . By taking , we have that for any , . As and are coprime, there exists a positive integer such that . Hence, Let . The above argument then implies that , therefore . For any positive factor of , this satisfies all the requirements. Hence, all the possible values of are , , , , .
Final answer
3, 9, 11, 33, 99

Techniques

Inverses mod nGreatest common divisors (gcd)Group Theory