2009 Indonesia MO Problems/Problem 7
Solution
Since , by Bézout's Identity, there exists integers
and
such that
.
Since , we get
. Similarly,
.
As a result, for any integers ,
,
, and
Lemma: There exists certain integers ,
such that
, for some integer
.
Let , and
, then
, and
.
Since , replacing
with
gives us
.
It's worth noting that from the original Bézout's Identity, , where
, so exactly one of
is positive and the other is negative. WLOG, suppose that
is positive and
is negative. Then
is a negative number. Thus,
.
Replacing and
with
gives us
Let and
, then
,
.
and
for obvious reasons.
Verifying the conditions, since , and
. Thus,
Similarly, since , and
. Thus,
This means and
.
, using Euclidean algorithm. If
, then Bezout's identity
should have both sides divisible by such number, but 1 is not divisible by any integer besides 1 and -1. Thus,
. Similarly,
.
Thus, and