Solution of Linear Congruence/Examples/9 x = 8 mod 7

Example of Solution of Linear Congruence

Let $9 x = 8 \pmod 7$.

Then:

$x = 4 + 7 t$

where $t \in \Z$.

Proof

We have that:

$8 \equiv 1 \pmod 7$

and so:

\(\ds 9 x\)

\(=\)

\(\ds 8\)

\(\ds \pmod 7\)

\(\ds \leadstoandfrom \ \ \)

\(\ds 9 x\)

\(=\)

\(\ds 1\)

\(\ds \pmod 7\)

That should simplify the arithmetic.

Then:

\(\ds 9 x\)

\(=\)

\(\ds 1\)

\(\ds \pmod 7\)

\(\ds \leadsto \ \ \)

\(\ds 9 x - 1\)

\(=\)

\(\ds 7 k\)

for some $k \in \Z$

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

\(\ds \leadsto \ \ \)

\(\ds 9 x - 7 k\)

\(=\)

\(\ds 1\)

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

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

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

Using the Euclidean Algorithm:

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

\(\ds 9\)

\(=\)

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

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

\(\ds -7\)

\(=\)

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

\(\ds -2\)

\(=\)

\(\ds -2 \times 1\)

Thus we have that:

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

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

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

Next we find a single solution to $9 x - 7 k = 1$.

Again with the Euclidean Algorithm:

\(\ds 1\)

\(=\)

\(\ds -7 - 4 \times \paren {-2}\)

from $(4)$

\(\ds \)

\(=\)

\(\ds -7 + 4 \times 2\)

\(\ds \)

\(=\)

\(\ds -7 + 4 \times \paren {9 - \paren {-1 \times \paren {-7} } }\)

from $(3)$

\(\ds \)

\(=\)

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

\(\ds \)

\(=\)

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

and so:

\(\ds x_0\)

\(=\)

\(\ds 4\)

\(\ds k_0\)

\(=\)

\(\ds 5\)

is a solution.

Thus from $(2)$:

$x = 4 + 7 t$

$\blacksquare$

Sources

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