2009 Indonesia MO Problems/Problem 7

Solution

Since $\gcd(a, b) = 1$ , by Bézout's Identity, there exists integers $x$ and $y$ such that $ax+by=1$ .

Since $ax=1-by$ , we get $a|1-by$ . Similarly, $b|1-ax$ .

As a result, for any integers $p$ , $q$ , $a|pab-by+1$ , and $b|qab-ax+1$ $a|(pa-y)b+1$ $b|(qb-x)a+1$

Lemma: There exists certain integers $p$ , $q$ such that $pa-y=qb-x=k$ , for some integer $k\neq 0$ .

Let $p=x(y-x)$ , and $q=y(x-y)$ , then $pa-y=ax(y-x)-y$ , and $qb-x=by(x-y)-x$ .

Since $ax+by=1$ , replacing $ax$ with $1-by$ gives us

$k=pa-y=ax(y-x)-y=y-x-by^2+byx=by(x-y)-x=qb-x$ .

It's worth noting that from the original Bézout's Identity, $ax+by=1$ , where $a,b>1$ , so exactly one of $x,y$ is positive and the other is negative. WLOG, suppose that $y$ is positive and $x$ is negative. Then $ax(y-x)-y$ is a negative number. Thus, $k\neq 0$ .

Replacing $(pa-y)$ and $(qb-x)$ with $k$ gives us $a|kb+1$ $b|ka+1$

Let $m = ka$ and $n = kb$ , then $a|n+1$ , $b|m+1$ . $a|m$ and $b|n$ for obvious reasons.

Verifying the conditions, since $m=ka$ , and $b|m+1$ . Thus, $kb|m(m+1)$

Similarly, since $n=kb$ , and $a|n+1$ . Thus, $ka|n(n+1)$

This means $n|m^2+m$ and $m|n^2+n$ .

$\gcd(a, n)=\gcd(a, kb)=\gcd(a,ax(y-x)-y)=\gcd(a,-y)$ , using Euclidean algorithm. If $\gcd(a, y)>1$ , then Bezout's identity $ax+by=1$ should have both sides divisible by such number, but 1 is not divisible by any integer besides 1 and -1. Thus, $\gcd(a, n)=\gcd(a,-y)=1$ . Similarly, $\gcd(b, m)=\gcd(b,-x)=1$ .

Thus, $a\nmid n$ and $b\nmid m$

Page

Toolbox

Search

2009 Indonesia MO Problems/Problem 7

Solution