Solution of Linear Congruence/Examples/5 x = 4 mod 3
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
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {4-1}$ Basic Properties of Congruences: Exercise $1 \ \text{(a)}$