Wednesday, 19 November 2025

Exercise (3.3).10

Give an example of a linear congruence $ax ≡ b \pmod n$ where integer $d > 1$ divides $a$, $n$, and $b$ but the equation has no solutions.


Since $d > 1$ divides $a$, $n$, and $b$, we have for some integers $p, q, r$

$$ \begin{align} a & = pd \\ \\ b & = qd \\ \\ n & = rd \end{align} $$

So we can rewrite the linear congruence as

$$ pdx \equiv qd \pmod {rd}$$

which reduces to

$$ \begin{align} px & \equiv q \pmod {\frac{rd}{\gcd(rd,d)}} \\ \\ px & \equiv q \pmod {\frac{rd}{d\gcd(r,1)}}  \\ \\ & \equiv q \pmod {\frac{rd}{d}} \\ \\ px & \equiv q \pmod {r} \end{align} $$

For there to be no solutions

$$ \gcd(r,p) \not \mid q $$


The candidates $r=2, p=2, q=3$ satisfy $\gcd(r,p) \not \mid q$.

We can then try $d=2$, giving $a=4, b=6, n=4$.

So an example of a linear congruence is

$$ 4x \equiv 6 \pmod 4 $$


Let's check: $g = \gcd(4,4)=4$ and $g \not \mid 6$, so there are no solutions, yet $d=2$ divides 4 and 6.