Solution of Linear Congruence/Examples/9 x = 8 mod 7
Jump to navigation
Jump to search
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)}$