0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 1 = 9 * 5 - 11* 4 also works. Then will 4 be an inverse of 11 modulo 9 too? $\endgroup$ – wrenyoong Jun 8 '15 at 3:10
  • $\begingroup$ 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? $\endgroup$ – wrenyoong Jun 8 '15 at 4:34
  • $\begingroup$ Nevermind. It does work on 4 by setting -11! thanks! $\endgroup$ – wrenyoong Jun 8 '15 at 4:45
  • $\begingroup$ $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. $\endgroup$ – Bernard Jun 8 '15 at 8:08
1
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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