Solution of Linear Congruence/Examples/6 x = 5 mod 4
Jump to navigation
Jump to search
Example of Solution of Linear Congruence
Let $6 x = 5 \pmod 4$.
Then $x$ has no solution in $\Z$.
Proof
\(\ds 6 x\) | \(=\) | \(\ds 5\) | \(\ds \pmod 4\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds 6 x - 5\) | \(=\) | \(\ds 4 k\) | for some $k \in \Z$ | ||||||||||
\(\text {(1)}: \quad\) | \(\ds \leadsto \ \ \) | \(\ds 6 x - 4 k\) | \(=\) | \(\ds 5\) |
Using the Euclidean Algorithm:
\(\ds 6\) | \(=\) | \(\ds -1 \times \paren {-4} + 2\) | ||||||||||||
\(\ds -4\) | \(=\) | \(\ds 2 \times \paren {-2}\) |
Thus we have that:
- $\gcd \set {6, -4} = 2$
which is not a divisor of $5$.
So, from Solution of Linear Diophantine Equation, no solution exists.
$\blacksquare$
Sources
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {4-1}$ Basic Properties of Congruences: Exercise $2 \ \text{(a)}$