2003 Indonesia MO Problems/Problem 7
Problem
Let be positive integers such that and the greatest common divisor of and is . Prove that if divides , then .
Solution
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 .
See Also
2003 Indonesia MO (Problems) | ||
Preceded by Problem 6 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 | Followed by Problem 8 |
All Indonesia MO Problems and Solutions |