Exercise 2.1.41 (Solve $a \equiv b \mod c, b \equiv c \mod a, c \equiv a \mod b$, $a,b,c \in \mathbb{N}^*$)

Proof. Let $(a,b,c)$ be a solution of

Then $(\mathit{ka},\mathit{kb},\mathit{kc})$ is a solution for any positive integer $k$. Hence is suffices to determine all primitive sets with the property $a\wedge b\wedge c=1$.

If $(a,b,c)$ is a solution, so is any permutation of $(a,b,c)$. So there is no loss in generality in assuming that $a\le b\le c$.

Let $(a,b,c)$ be a solution of (1) such that $a\wedge b\wedge c=1$ and $a\le b\le c$. We name such a solution a reduced solution.

Then (1) is equivalent to the existence of integers $k,l,m$ such that

Since $0<a\le b\le c$, we have $k\ge 0,l\ge 0,m\ge 0$.

From (2), we obtain $b=a+\mathit{kc}$. Substituting this value in (3), we deduce $c-(a+\mathit{kc})=\mathit{la}$, therefore

Assume for contradiction that $k\ge 1$. Then $0=(k-1)c+(l+1)a>0$. This is a contradiction, so $k=0$. Then $a=b$, and (4) gives $c=(m+1)a$.

But $1=a\wedge b\wedge c=a\wedge a\wedge (m+1)a=a$, thus $a=b=1$ (and $c$ is any integer $n\ge 1$).

Conversely $(1,1,n)$, where $n\in {\mathbb{N}}^{\text{∗}}$, is a reduced solution, because $1-1\equiv 0(\mathit{mod}n)$ and $n-1\equiv 0(\mathit{mod}1)$ (and $1\wedge 1\wedge n=1,1\le 1\le n$).

To conclude, the reduced solutions are the triplets $(1,1,n)$ for $n\in {\mathbb{N}}^{\text{∗}}$.

(So the solutions are $(\lambda ,\lambda ,\mathit{\lambda n}),(\lambda ,\mathit{\lambda n},\lambda )$ or $(\mathit{\lambda n},\lambda ,\lambda )$, where $\lambda ,n\in {\mathbb{N}}^{\text{∗}}$). □