Why is the solution to $8x \equiv 9 \pmod {15} $ unique?

Question

We can solve $8x \equiv 9 \pmod {15} $ by multiplying both sides by $8^{-1} \equiv 2 \pmod {15}$, getting $x \equiv 3 \pmod {15}$ so $x=3$. I know that the multiplicative inverse of a number is unique; but I am struggling conceptually to justify why this is a unique solution to $8x \equiv 9 \pmod {15} $. How can we show that there exists no other solution for x here?

Answer 1

[Recall $ $ "solutions are unique $\!\bmod n$" means that if $x_1\,$ is a solution then every other solution $x_2$ is congruent to it $\,x_2\equiv x_1\pmod{\!n}\,$ or, equivalently, solutions of $\,8x=9\,$ are unique in $\,\Bbb Z_{15}$]

The proof uses only existence (not uniqueness) of inverses, i.e. suppose $\,a'\,$ is some inverse of $\,a.\,$ Scaling $\,ax\equiv b\,$ by $\,a'\,$ yields $\,x\color{#c00}{\equiv a'b}.\,$ Uniqueness follows immediately: if $\,x_1,x_2\,$ are roots then $\,x_1\color{#c00}{\equiv a'b\equiv} x_2\,$ (which implictly exploits the fact that congruence, like equality, is an equivalence relation so it is transitive, i.e. $\,x_1\color{#c00}{\equiv y}\equiv x_2\,\Rightarrow\, x_1\equiv x_2)$.

---

Existence also follows immediately since scaling an equation or congruence by a unit (invertible) is an invertible operation so it yields an equivalent equation or congruence. Thus the above scaling is reversible: scaling $\,x\equiv a'b\,$ by $\,a\,$ yields $\,ax\equiv b,\,$ so $\,a'b\,$ is indeed a root. Summarizing

$${\rm if}\ \ \ a'a \equiv 1 \equiv aa'\ \ \ {\rm then}\ \ \ ax\equiv b\iff x\color{#c00}{\equiv a'b}\qquad$$

Remark $ $ That the proof uses only the existence (not uniqueness) of some inverse $\,a'\,$ of $\,a\,$ is a point often misunderstood, perhaps because some (very) popular textbooks mislead students by wrongly claiming that $\,x\,$ is unique because inverses of $\,a\,$ are unique, e.g. see here.

Though it is completely obvious with hindsight, it is often overlooked that uniqueness is an immediate consequence of an explicit solution $\,x\equiv\, \ldots\,$ (as in the direction $(\Rightarrow)$ above). See here for further discussion of another textbook example (additive case). Another example occurred here a couple weeks ago.

The above shows that scaling a congruence by a unit (invertible) yields an equivalent congruence. This is the congruence analog of a fact that is well know for equations, e.g. scaling a polynomial equation to an equivalent equation that is monic (lead coefficient $= 1),\,$ e.g. choosing monic minimal polynomials, or unit-normalized polynomial gcds in polynomial rings $\,k[x]$.

Answer 2

The question was originally written with solution $x=3$. It has now been edited to read $x \equiv 3$

The following refers to the question as it was originally asked with x=3, which technically refers specifically and exactly to only 3.

It's not. For example, $x= 18$ is also a solution. In fact $x=3+ 15n$ for $n\in \mathbb Z$ are also solutions.

Unless you meant the entire equivalence class {3 + 15n} in which case our answers are the same.