IMO 2011 #5
by Wolstenholme, Oct 30, 2014, 3:38 PM
Let 
be a function from the set of integers to the set of positive integers. Suppose that, for any two integers 
and 
, the difference 
is divisible by 
. Prove that, for all integers and with 
, the number 
is divisible by 
.
Proof:
In the following proof,
will be used to denote the positive greatest common divisor of integers 
and 
.
Lemma 1:
for all 
Proof: We proceed with induction on
. Note that the base case of 
is trivial. Since 
we have that 
which completes the induction.
Lemma 2:
for all 
Proof: By an easy extension Lemma 1 we have that
and similarly 
which implies the desired result.
Lemma 3: For all
, there exists 
such that 
Proof: This is Euclid's Lemma
Now consider any two positive integers
and the corresponding integers 
such that 
. Then 
and 
By Lemma 1 we have that 
divides both 
and 
so one of and is equal to 
Assume WLOG that 
Then 
by repeated applications of Lemma 1 as desired.
Note I kind of ignored cases and negatives because I'm lazy but hopefully this general idea works.
be a function from the set of integers to the set of positive integers. Suppose that, for any two integers 
and 
, the difference 
is divisible by 
. Prove that, for all integers and with 
, the number 
is divisible by 
.Proof:
In the following proof,
will be used to denote the positive greatest common divisor of integers 
and 
.Lemma 1:
for all 
Proof: We proceed with induction on
. Note that the base case of 
is trivial. Since 
we have that 
which completes the induction.Lemma 2:
for all 
Proof: By an easy extension Lemma 1 we have that
and similarly 
which implies the desired result.Lemma 3: For all
, there exists 
such that 
Proof: This is Euclid's Lemma
Now consider any two positive integers
and the corresponding integers 
such that 
. Then 
and 
By Lemma 1 we have that 
divides both 
and 
so one of and is equal to 
Assume WLOG that 
Then 
by repeated applications of Lemma 1 as desired.Note I kind of ignored cases and negatives because I'm lazy but hopefully this general idea works.
August 2016
June 2016