2003 Indonesia MO Problems/Problem 7
Let be positive integers such that and the greatest common divisor of and is . Prove that if divides , then .
If divides , then we have Because , . That means Since , does not share any factors with . We can multiply both sides by the modular multiplicative inverse, so Thus, , where is an integer. After rearranging terms, we have If , then . This can not happen, so we can divide both sides by without losing any solutions. To finish the proof that , we will use induction. For the base case, letting results in , which satisfies the inequality.
For the inductive step, assume . Multiplying both sides by and dividing both sides by results in Adding both sides by results in Because , the value is less than 0. Thus, so we have The inductive step is complete, so we have proven that .
|2003 Indonesia MO (Problems)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8||Followed by|
|All Indonesia MO Problems and Solutions|