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

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)}$