Cyclic Remainders

Number Theory Level 3

Distinct positive integers $x$ , $y$ , and $z$ such that:

$\begin{cases} yz \equiv 1 \text{ (mod } x) \\ zx \equiv 1 \text{ (mod } y) \\ xy \equiv 1 \text{ (mod }z) \end{cases}$

Find the sum of all possible values of $xyz$ .

The answer is 30.

1 solution

Scrub Lord
Jan 5, 2019

WLOG we can assume that $x > y > z$ . Since $x$ and $y$ and $z$ are pairwise coprime, we see that $xyz | xy + xz + yz -1$ .

$xyz < xy + xz + yz < 3xy \rightarrow z < 3$

If $z = 2 \rightarrow xy < 2(x+y)$ , then $y = 3$ or $y = 4$ .

In the first case $x < 6$ and we notice that $(z, y, x) = (2, 3, 5)$ is the first solution to a problem. In the second case $x$ can only be 4, which is not a solution.

$z = 1$ requires that $y=1$ , which contradicts the rules of the problem. $(z, y, x) = (2, 3, 5)$ is therefore the only solution.

Your solution is similar to my solution but there is a typo at "we see that xyx|xy+xz+yz-1" should be "we see that xyz|xy+xz+yz-1"

Culver Kwan - 2 years, 5 months ago

Of course, thank you.

Scrub Lord - 2 years, 5 months ago

total 6 solution possible (x,y,z)=(2,3,5),(2,5,3),(3,2,5),(3,5,2),(5,2,3),(5,3,2)

sonu gupra - 2 years, 4 months ago

I assumed that x>y>z. The rest of the problem is solved under that assumption, so in this context there is only one solution.

Scrub Lord - 2 years, 4 months ago

xyz|xy + yz + zx -1 put x=3 y =2 z=1; 6|10 not correct

sonu gupra - 2 years, 4 months ago

Cyclic Remainders

The answer is 30.

1 solution

0 pending reports