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?

  • $\begingroup$ The solution of $ax+b\equiv 0\pmod m$ is unique if $\gcd(a,m)=1$. $\endgroup$ – richrow Sep 18 '20 at 20:28
  • $\begingroup$ So, are $89$ and $55$ coprime? $\endgroup$ – Geoffrey Trang Sep 18 '20 at 20:31
  • $\begingroup$ @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 $\endgroup$ – sjm23 Sep 18 '20 at 20:35
  • $\begingroup$ @GeoffreyTrang yes they are. $\endgroup$ – sjm23 Sep 18 '20 at 20:36
  • 1
    $\begingroup$ The uniqueness (and existence) of the solution are explicitly treated in this dupe. If you have further questions please post comments here or there. $\endgroup$ – 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}$.

  • $\begingroup$ 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$. $\endgroup$ – sjm23 Sep 18 '20 at 20:39
  • $\begingroup$ $k=-3\implies x=-147$. $\endgroup$ – user403337 Sep 18 '20 at 20:42
  • $\begingroup$ Yes, and $x=-147=7(-21)=7\lambda$ $\endgroup$ – sjm23 Sep 18 '20 at 20:54
  • $\begingroup$ 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\}$. $\endgroup$ – user403337 Sep 18 '20 at 20:57
  • $\begingroup$ I know. But what I'm asking is why that infinite list is the only solution. That's what I need to prove. $\endgroup$ – sjm23 Sep 18 '20 at 21:00

Not the answer you're looking for? Browse other questions tagged or ask your own question.