Online Course Discussion Forum
summer camp blue group number theory day 1 P5
Find all triples of positive integers (a,b,c) such that a≡b(mod c), b≡c(mod a), and c≡a(mod b).
The answer key says that all triplets are (k,k,ck) where k and c are positive integers and I can see that this will work, but how do we know there are no others? Also how can we prove this because in the problem I let a-b=c(k1), b-c=a(k2), c-a=b(k3) and I don't see how to get that two of the a, b, and c must be equal.
thanks
It is not hard to see that if $(a,b,c)$ is a solution, also $(ka,kb,kc)$ is a solution for any positive integer $k$.
Assume $1 \leq a \leq b \leq c$ and $\gcd(a,b,c)=1$. Since $a \equiv b \pmod{c}$, we have that $c \mid b -a$, so $b - a = 0$, and $a = b$. Since $b \equiv c \pmod{a}$, we have $a \mid b - c$, so $a \mid c$. Thus $a = b = 1$. Therefore $(1,1,c)$ is a solution for any positive integer $c$.
Social networks