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 |