0
$\begingroup$

Find all sets of positive integers a, b, c satisfying the three congruences $a ≡ b (mod \text{ c})$ , $ b ≡ c (mod \text{ a})$ , $c ≡ a (mod \text{ b})$.

Well i can see that the tuple $(a,a,1)$ satisfies the system and also $a=b=c$. What i dont understand is how i can proceed using modular arithmetic to find the solutions since the modulos are different. Thanks

$\endgroup$

1 Answer 1

1
$\begingroup$

Your solution of $(a,a,1)$ doesn't work; $b \not \equiv c \pmod a$ if $b=a$, $c=1$.

Here's the correct way to go about it.

$a \equiv b \pmod c$ gives $a-b \equiv 0 \pmod c$, i.e. $c|a-b$. Similarly, $a|b-c$, $b|c-a$.

Without loss of generality, assume $c$ is the largest. Then $c|a-b$, so $a-b \geq c$, or $a-b = 0$. $a-b \geq c$ cannot happen as $a \leq c$, so $a=b$.

So we have $a=b$, and so we also have $a|a-c$, which gives $a|c$. So $(a,a,ka)$ and cyclic rotations of these are the only possible solutions, and it's easy to check they all work.

$\endgroup$
1
  • $\begingroup$ Ahh yes ofc are right. And well i got so involved with congruences i never thought about divisibility in this question. Thanks a lot. $\endgroup$ Jun 11, 2020 at 16:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .