Help me out with understanding this congruence solution.

Question

If $11k \equiv -6 \pmod 9$, it is easily found that $k=6$

Here are my questions:

1) Since $(11,9)=1$ how do we know for sure that the above congruence has exactly one incongruent solution modulo $9$?

2) also if we know $k=6$, how come $k \equiv 6 \pmod 9$?

Answer 1

From Bézout's identity: $\,5\cdot 11-6\cdot 9=1$, we deduce $5$ is the inverse of $11$ modulo $9$. Multiplying both sides by $5$, we obtain: $$5\cdot 11k\equiv k\equiv 5\cdot (-6)=-30\equiv6\mod 9.$$

Answer 2

since $(11,9) = 1$ then we know there exists $x,y \in \mathbb{Z}$ such that $11x + 9y= 1$ and we can actually go through the euclidean algorithm

$$11 = 1\times 9 + 2$$

$$9 = 4 \times 2 + 1$$ and so reversing the algorithm we can find those pair $(x,y)$

it is easy $$1 = 9 - 4 \times 2 = 9 - 4 \times (11 \times 9) = 5 \times 9 - 4 \times 11$$ and so $x = -4,y = 5$

Now since we have $$1 = 5 \times 9 - 4 \times 11$$ we can multiply $-6$ each side to get $$-6 = -30 \times 9 + 24 \times 11$$ and so we get $$-6 - 24 \times 11 = -30 \times 9$$ and so $k=24$ however, we are working modulo $9$ and so $24 \equiv 6 \pmod{9}$ and so $k \equiv 6 \pmod 9$

Answer 3

For Q1:

Suppose you have two solutions $x$ and $y$, then \begin{align*} 11x & \equiv -6 \pmod{9}\\ 11y & \equiv -6 \pmod{9}. \end{align*} This means $$11(x-y) \equiv 0 \pmod{9}.$$ But $\gcd(11,9)=1$, therefore for this equivalence to be true $9$ should divide $x-y$. Consequently $x \equiv y \pmod{9}$. Thus any two solutions have to be congruent to each other.

For Q2:

This follows from my reasoning stated above: if $k=6$ is a solution we already know that $6$ is also a solution, then (by the reasoning stated above) $k \equiv 6 \pmod{9}$.