2006 OIM Problems/Problem 4

Problem

Find all pairs $(a, b)$ of positive integers such that $2a + 1$ and $2b - 1$ are relative primes and $a + b$ divides $4ab + 1$ .

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

We are given that $a+b$ divides $4ab+1$ ; thus $a+b$ must also divide $4ab+2(a+b)+1=(2a+1)(2b+1)$ . But notice that since $\gcd(2a+1,2b-1)=1$ , by the Euclidean Algorithm, we must also have $\gcd(2a+1,2b-1)=\gcd((2a+1,(2a+1)+(2b-1))=\gcd(2a+1,2(a+b))=1$ Clearly $2\nmid 2a+1$ ; thus $\gcd(a+b,2a+1)=1$ . Therefore, from earlier, we know that $(a+b)|(2a+1)(2b+1)$ ; what we just found implies that $(a+b)|(2b+1)$ This fact is equivalent to $\frac{2b+1}{a+b}\in\mathbb{Z}$ But $\frac{2b+1}{a+b}=1+\frac{b-a+1}{a+b}$ which implies that $\frac{b-a+1}{a+b}\in\mathbb{Z}$ Let the expression above equal some integer $k$ . Rearranging gives us the equation $a(k+1)+b(k-1)=1$ If $k\ge1$ , then $a(k+1)+b(k-1)\ge2a\ge2>1$ a contradiction. Similarly, if $k\le-1$ , then $a(k+1)+b(k-1)\le -2b\le -2<1$ also a contradiction, which implies that $k=0$ . Substituting into the above yields $a-b=1$ .

Finally, we check that these solutions work. If $a-b=1$ , then $a+b=2b+(a-b)=2b+1$ , and $4ab+1=4(b+1)b+1=4b^2+4b+1=(2b+1)^2$ thus the condition is clearly true, so our solution set is $\boxed{(t+1,t)}$ for all positive integers $t$ .

~ eevee9406

Page

Toolbox

Search

2006 OIM Problems/Problem 4

Problem

Solution

See also