# Help me out with understanding this congruence solution.

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$?

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.$$

• 1 = 9 * 5 - 11* 4 also works. Then will 4 be an inverse of 11 modulo 9 too? – wrenyoong Jun 8 '15 at 3:10
• I do not think consideration of 4 as an inverse of 11 will work since -24 mod 9 is 3. Is there any pattern I can use with this Bezout's identity? The principal idea that I have to keep in mind when I am using this identity? – wrenyoong Jun 8 '15 at 4:34
• Nevermind. It does work on 4 by setting -11! thanks! – wrenyoong Jun 8 '15 at 4:45
• $4$ is not an inverse of $11$, and I never said it was! Indeed $4\cdot 11\equiv -1\mod 9$ (whence of course $4\cdot -11\equiv 1$). Now the method will work starting from any Bézout's identity for $11$ and $9$ – and there is an infinity of them. – Bernard Jun 8 '15 at 8:08

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$

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}$.