2

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!

Servaes
  • 63,261
  • 7
  • 75
  • 163
Culver Kwan
  • 2,785
  • The "one implies another one" is seen by looking at the congruence modulo the largest number: the result must be $1$, so the multiplication of $1$ by some number smaller than the modulus must result in $1$, giving the result stated in the hint. – abiessu Jul 13 '19 at 13:37
  • If $x=1$, then $yz \equiv 1 mod 1$, so $yz = 1$ and since they are positive, $y=z=1$. This is a contradiction to your assumption $x<y<z$. – Daniel W. Jul 13 '19 at 13:39
  • 1
    @DanielW.: Surely every integer $n$ satisfies $n\equiv 1\bmod 1$? – TonyK Jul 13 '19 at 14:37
  • If $x=1$, then the third equation says that $y\equiv 1\bmod z$. Together with $y<z$, this forces $y=1$. – TonyK Jul 13 '19 at 14:39

3 Answers3

5

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.
nonuser
  • 90,026
  • This is already in an answer in the 3rd linked related question. – Bill Dubuque Jul 13 '19 at 18:00
  • Do you like that solution in link you posted? @BillDubuque – nonuser Jul 13 '19 at 18:01
  • What is a point of your comment? – nonuser Jul 13 '19 at 18:03
  • That the answer is a dupe, and we should strive to avoid such since that is one of the major problems the site faces nowadays. – Bill Dubuque Jul 13 '19 at 18:04
  • Do you know how long I'm here? @BillDubuque – nonuser Jul 13 '19 at 18:04
  • I think you understand very well my point. Please don't waste your precious time any more on useless conversation. @BillDubuque – nonuser Jul 13 '19 at 18:08
  • One shouldn't presume that other users understand your comments "very well" when they explicitly stated otherwise. Honestly, I have no idea what you are hinting at above. Please be more precise if you expect others to understand you. – Bill Dubuque Jul 13 '19 at 18:11
  • Yes of course you don't. @BillDubuque – nonuser Jul 13 '19 at 18:13
  • Btw, I just noticed that you change your username quite frequently. This will likely make it much more difficult for others to understand you because they will lack the context that would otherwise be available for a longtime user who doesn't change their username. I don't know if this would have helped above, but it may be worth keeping in mind the next time you consider changing your name. It works against you in many ways. – Bill Dubuque Jul 13 '19 at 18:49
3

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?

Servaes
  • 63,261
  • 7
  • 75
  • 163
1

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$.

W-t-P
  • 4,629