Solution of Linear Congruence/Examples/7 x = 6 mod 5

Example of Solution of Linear Congruence

Let $7 x = 6 \pmod 5$.

Then:

$x = 3 + 5 u$

where $u \in \Z$.

Proof

\(\ds 7 x\)

\(=\)

\(\ds 6\)

\(\ds \pmod 5\)

\(\ds \leadsto \ \ \)

\(\ds 7 x - 6\)

\(=\)

\(\ds 5 k\)

for some $k \in \Z$

\(\text {(1)}: \quad\)

\(\ds \leadsto \ \ \)

\(\ds 7 x - 5 k\)

\(=\)

\(\ds 6\)

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

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

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

Using the Euclidean Algorithm:

\(\text {(3)}: \quad\)

\(\ds 7\)

\(=\)

\(\ds -1 \times \paren {-5} + 2\)

\(\text {(4)}: \quad\)

\(\ds -5\)

\(=\)

\(\ds 3 \times \paren {-2} + 1\)

\(\ds -2\)

\(=\)

\(\ds -2 \times 1\)

Thus we have that:

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

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

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

Next we find a single solution to $7 x - 5 k = 6$.

Again with the Euclidean Algorithm:

\(\ds 1\)

\(=\)

\(\ds -5 - 3 \times \paren {-2}\)

from $(4)$

\(\ds \)

\(=\)

\(\ds -5 + 3 \times 2\)

\(\ds \)

\(=\)

\(\ds -5 + 3 \times \paren {7 - \paren {-1 \times \paren {-5} } }\)

from $(3)$

\(\ds \)

\(=\)

\(\ds -5 + 3 \times \paren {7 - 5}\)

\(\ds \)

\(=\)

\(\ds 3 \times 7 + 4 \times \paren {-5}\)

\(\ds \leadsto \ \ \)

\(\ds 6\)

\(=\)

\(\ds 18 \times 7 + 24 \times \paren {-5}\)

and so:

\(\ds x_0\)

\(=\)

\(\ds 18\)

\(\ds k_0\)

\(=\)

\(\ds 24\)

is a solution.

Thus:

\(\ds x\)

\(=\)

\(\ds 18 + 5 t\)

from $(2)$

\(\ds \)

\(=\)

\(\ds 3 + 5 \paren {t + 3}\)

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

$\blacksquare$

Sources

• 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {4-1}$ Basic Properties of Congruences: Exercise $1 \ \text{(b)}$