Let $a,b,c$ be given positive integers. Prove that there exists some positive integer $N$ such that \[ a\mid Nbc+b+c,\ b\mid Nca+c+a,\ c\mid Nab+a+b \] if and only if, denoting $d=\gcd(a,b,c)$ and $a=dx$, $b=dy$, $c=dz$, the positive integers $x,y,z$ are pairwise coprime, and also $\gcd(d,xyz) \mid x+y+z$. (Dan Schwarz)
Problem
Source: 4th stars of mathematics,problem4
Tags: number theory proposed, number theory
01.01.2012 13:38
From $a\mid Nbc + b + c$ we have $x\mid Ndyz + y + z$. If $\gcd(x,y) = m$, then $m\mid z$, so $m = 1$, hence $x,y,z$ are pairwise coprime (because $x\mid Ndyz + y + z$, $y\mid Ndzx + z + x$, $z\mid Ndxy + x + y$). Consider $T = Ndyz + Ndzx + Ndxy + x + y + z$; then $x\mid T$, $y\mid T$, $z\mid T$, so $xyz\mid T$. Suppose $\gcd(d,xyz) = r$; then $r\mid T=Ndyz + Ndzx + Ndxy + x + y + z$, so $r\mid x + y + z$, and we're done.
01.01.2012 14:59
But the problem requires "if and only if". It only has been proved that, if $N$ exists satisfying the former divisibility conditions, then the latter conditions on $a,b,c$ are also satisfied. It remains to prove that, under those latter conditions, some $N$ exists satisfying the former divisibility conditions.
02.01.2012 15:56
If $\gcd (d,xyz)\mid x + y + z$ and $x,y,z$ are pairwise corprime, then $\gcd \left( {xy + yz + zx,xyz} \right) = 1$. By Bézout's relation there exist $N,k$ satisfying $kxyz - Nd(xy + yz + zx) = x + y + z$, so $xyz\mid x + y + z + Nd(xy + yz + zx)$, hence we have $x\mid Ndyz + y + z$, $y\mid Ndzx + z + x$, $z\mid Ndxy + x + y$, and we're done.