Cyclic Remainders

Question

When I was doing my math team training, I encountered a hard question again.

Let $x,y,z$ be positive integers that $x<y<z$ with $$\begin{cases} yz\equiv1\mod x\\ zx\equiv1 \mod y\\xy\equiv1\mod z\end{cases}$$Find all triples $(x,y,z)$ such that the above equation holds.

Coach's hint

First, if one of the variable equals to $1$, then at least one of the other variable equals $1$ (I don't know why, so please explain also), which contradicts with they are distinct.

I have no idea how to do the question. I just found that $(2,3,5)$ is a solution but I can't find any other solutions. But I can't find any prove to prove that there are no other solutions.

Thanks for any help!

Answer 1

So we have $z\mid xy-1$ and so on... If we "multiply" all those realtions we get: $$xyz\mid x^2y^2z^2-xyz(x+y+z)+xy+yz+zx-1$$

so $$xyz\mid xy+yz+zx-1$$

since right side is $> 0$ we have $$xyz\leq xy+yz+zx-1 <xz+yz+zx$$ so $$xy <2x+y \implies y<{2x\over x-1}$$

iff $x\ne 1$. So for $x\geq 3$ we have $y<3$ so $y=1$ or $2$ which can not be. So $x\in \{1,2\}$ And now should be easier:

• If $x=2$ we get $y< 4$ so $y=3$ which can we check it manualy...
• If $x=1$ we get $z\mid y-1$. Since $y>1$ we get $z\leq y-1<y$ which is impossibile.

Answer 2

The congruences give you the following divisibility relations: $$x\mid yz-1,\qquad y\mid zx-1,\qquad z\mid xy-1.$$ Multiplying these together shows that $xyz$ divides \begin{eqnarray*} (yz-1)(zx-1)(xy-1) &=&x^2y^2z^2-xyz^2-xy^2z-x^2yz+yz+zx+xy-1\\ &=&xyz(xyz-x-y-z)+xy+yz+zx-1, \end{eqnarray*} and hence $xyz$ also divides $xy+yz+zx-1$. This means their ratio $$\frac{yz+zx+xy-1}{xyz}=\frac1x+\frac1y+\frac1z-\frac{1}{xyz},\tag{1}$$ is an integer. Of course it is positive because both $xyz$ and $yz+zx+xy-1$ are positive. But $x<y<z$ also implies $x\geq1$, $y\geq2$ and $z\geq3$, and so $$\frac1x+\frac1y+\frac1z-\frac{1}{xyz}<\frac1x+\frac1y+\frac1z\leq\frac11+\frac12+\frac13<2.$$ This shows that the ratio $(1)$ must equal $1$. If $x\geq3$ then $y\geq4$ and $z\geq5$ so $$\frac1x+\frac1y+\frac1z-\frac{1}{xyz} <\frac1x+\frac1y+\frac1z \leq\frac13+\frac14+\frac15<1,$$ which shows that $x\leq2$. Can you finish from here?

Answer 3

First, notice that $xy\equiv 1\pmod z$ shows that $x$ and $y$ are coprime, and so are $y$ and $z$. Similarly, $x$ and $z$ are coprime. Thus, $x$, $y$ and $z$ are pairwise coprime.

Next, we observe that the integer $N:=xy+yz+zx$ satisfies $N\equiv yz\equiv 1\pmod x$ and, similarly, $N\equiv 1\pmod y$ and $N\equiv 1\pmod z$. This means that $N-1$ is divisible by each of $x,y,z$, and since they are pairwise coprime, $N-1$ is in fact divisible by their product: $xyz\mid (N-1)$; therefore $$ xy+yz+zx=N\ge xyz+1 > xyz. \tag{$\ast$} $$ Dividing through by $xyz$, $$ \frac 3x > \frac1x + \frac1y + \frac1z >1 $$ showing that $x<3$ and therefore $x=2$ (as we know that $x\ne 1$). Substituting into ($\ast$), $yz+2y+2z>2yz$, implying $$ \frac2y > \frac1y + \frac 1z > \frac12; $$ thus, $y<4$ and therefore $y=3$. Substituting again into ($\ast$), we get $3z+6+2z>6z$, whence $z<6$; since $x,y$ and $z$ are pairwise co-prime, we have in fact $z=5$.