Solution of Linear Congruence/Examples/10 x = 8 mod 6

From ProofWiki
Jump to navigation Jump to search

Example of Solution of Linear Congruence

Let $10 x = 8 \pmod 6$.

Then:

$x = 4 + 7 t$

where $t \in \Z$.


Proof

We have that:

$8 \equiv 2 \pmod 6$

and so:

\(\ds 10 x\) \(=\) \(\ds 8\) \(\ds \pmod 6\)
\(\ds \leadstoandfrom \ \ \) \(\ds 10 x\) \(=\) \(\ds 2\) \(\ds \pmod 6\)

That should simplify the arithmetic.

Then:

\(\ds 10 x\) \(=\) \(\ds 2\) \(\ds \pmod 6\)
\(\ds \leadsto \ \ \) \(\ds 10 x - 2\) \(=\) \(\ds 6 k\) for some $k \in \Z$
\(\text {(1)}: \quad\) \(\ds \leadsto \ \ \) \(\ds 10 x - 6 k\) \(=\) \(\ds 2\)


From Solution of Linear Diophantine Equation, the general solution to $(1)$ is:

$(2): \quad \forall t \in \Z: x = x_0 + 3 t, k = k_0 + 5 t$

where $x_0, k_0$ can be found as follows.


Using the Euclidean Algorithm:

\(\text {(3)}: \quad\) \(\ds 10\) \(=\) \(\ds -1 \times \paren {-6} + 4\)
\(\text {(4)}: \quad\) \(\ds -6\) \(=\) \(\ds -2 \times 4 + 2\)
\(\ds 4\) \(=\) \(\ds 2 \times 2\)

Thus we have that:

$\gcd \set {10, -6} = 2$

which is (trivially) a divisor of $2$.

So, from Solution of Linear Diophantine Equation, a solution exists.


Next we find a single solution to $10 x - 6 k = 2$.

Again with the Euclidean Algorithm:

\(\ds 2\) \(=\) \(\ds -6 - \paren {-2} \times 4\) from $(4)$
\(\ds \) \(=\) \(\ds -6 + 2 \times 4\)
\(\ds \) \(=\) \(\ds -6 + 2 \times \paren {10 - \paren {-1 \times \paren {-6} } }\) from $(3)$
\(\ds \) \(=\) \(\ds -6 + 2 \times \paren {10 - 6}\)
\(\ds \) \(=\) \(\ds 2 \times 10 + 3 \times \paren {-6}\)


and so:

\(\ds x_0\) \(=\) \(\ds 2\)
\(\ds k_0\) \(=\) \(\ds 3\)

is a solution.


Thus from $(2)$:

$x = 2 + 3 t$

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Solution_of_Linear_Congruence/Examples/10_x_%3D_8_mod_6&oldid=539349"