# Number of solutions to $89 x \equiv 7 \pmod{55}$ [duplicate]

How do I show that my solution to the congruence is the only solution?

I'm asked to solve, $$\mu,\lambda$$ that satisfy $$89 \lambda+55 \mu=1$$ Using Euclid's algorithm I found $$\lambda=-21,\mu=34$$.

Then I'm asked to find the solution to $$89 x \equiv 7\pmod{55}$$ Using $$\lambda 89 \equiv1 \pmod{55}$$

I found that $$7\lambda89 \equiv7 \pmod{55} \implies x=7\lambda +55k$$ for $$k\in \mathbb{Z}$$.

But how do I show, that this is the only solution to the congruence?

• The solution of $ax+b\equiv 0\pmod m$ is unique if $\gcd(a,m)=1$. – richrow Sep 18 '20 at 20:28
• So, are $89$ and $55$ coprime? – Geoffrey Trang Sep 18 '20 at 20:31
• @richrow So you're saying because $gcd(89,55)=1$ there is only one solution? Why is that the case? I don't have any theorems saying that. So I think I need to argue for that – sjm23 Sep 18 '20 at 20:35
• @GeoffreyTrang yes they are. – sjm23 Sep 18 '20 at 20:36
• The uniqueness (and existence) of the solution are explicitly treated in this dupe. If you have further questions please post comments here or there. – Bill Dubuque Sep 18 '20 at 21:15

You found the multiplicative inverse of $$89 \bmod {55}$$. It's $$-21$$. Thus we get $$89x\cong7\bmod{55}\iff x\cong -21\cdot7\bmod{55}\iff x\cong 18\bmod{55}$$.
• But that just gives me the same solution: $x=18+55k$ for $k\in \mathbb{Z}$? If we set $k=-3$, we get $x=7\lambda$. – sjm23 Sep 18 '20 at 20:39
• $k=-3\implies x=-147$. – user403337 Sep 18 '20 at 20:42
• Yes, and $x=-147=7(-21)=7\lambda$ – sjm23 Sep 18 '20 at 20:54
• Yes, but by multiplying on both sides of the congruence by $-21$ you prove all solutions are of the form $18+55k$. So we have the infinite list $\{\dots,-147, -92,-37,18,73,\dots\}$. – user403337 Sep 18 '20 at 20:57