Solution of Linear Congruence/Examples/5 x = 4 mod 3

From ProofWiki
Jump to navigation Jump to search

Example of Solution of Linear Congruence

Let $5 x = 4 \pmod 3$.

Then:

$x = 2 + 3 u$

where $u \in \Z$.


Proof

\(\ds 5 x\) \(=\) \(\ds 4\) \(\ds \pmod 3\)
\(\ds \leadsto \ \ \) \(\ds 5 x - 4\) \(=\) \(\ds 3 k\) for some $k \in \Z$
\(\text {(1)}: \quad\) \(\ds \leadsto \ \ \) \(\ds 5 x - 3 k\) \(=\) \(\ds 4\)


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 5\) \(=\) \(\ds -1 \times \paren {-3} + 2\)
\(\text {(4)}: \quad\) \(\ds -3\) \(=\) \(\ds 2 \times \paren {-2} + 1\)
\(\ds -2\) \(=\) \(\ds -2 \times 1\)

Thus we have that:

$\gcd \set {5, -3} = 1$

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

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


Next we find a single solution to $5 x - 3 k = 4$.

Again with the Euclidean Algorithm:

\(\ds 1\) \(=\) \(\ds -3 - 2 \times \paren {-2}\) from $(4)$
\(\ds \) \(=\) \(\ds -3 + 2 \times 2\)
\(\ds \) \(=\) \(\ds -3 + 2 \times \paren {5 - \paren {-1 \times \paren {-3} } }\) from $(3)$
\(\ds \) \(=\) \(\ds -3 + 2 \times \paren {5 - 3}\)
\(\ds \) \(=\) \(\ds 2 \times 5 + 3 \times \paren {-3}\)
\(\ds \leadsto \ \ \) \(\ds 4\) \(=\) \(\ds 8 \times 5 + 12 \times \paren {-3}\)


and so:

\(\ds x_0\) \(=\) \(\ds 8\)
\(\ds k_0\) \(=\) \(\ds 12\)

is a solution.


Thus:

\(\ds x\) \(=\) \(\ds 8 + 3 t\) from $(2)$
\(\ds \) \(=\) \(\ds 2 + 3 \paren {t + 2}\)

Setting $u = t + 2$ gives the result.

$\blacksquare$


Sources