Solve $ax \equiv b \mod m$ without Linear Congruence Theorem or Euclid's Algorithm?

Question

Origin page 5. The overhead doesn't look like Linear Congruence Theorem or anything from Euclid's Algorithm. page 4 tries to delineate Casting Out the Modulus? Is this it?

So if $d|m,$ then I rewrite $\begin{align} ax & \equiv b \mod m \\dx + x & \equiv \\ \implies x & \equiv \end{align}$

Is this errorless? Did I blight anything?

Answer 1

The $3x \equiv 9 \mod 6 $ has a common factor of $3$. Dividing both sides by 3 - including the modulus - we get:

$$ \begin{array}{ccc} 3x & \equiv & 9 \mod 6 \\ x & \equiv & 3 \mod \mathbf{2} \end{array} $$

For the remaining two congruence, we multiply both sides by an appropriate number:

$$ \begin{array}{rcc} 2x & \equiv & 1 \mod 5 \\ 3(2x) & \equiv & 3 \mod 5 \\ x & \equiv & 3 \mod 5 \end{array} $$

In modular arithmetic we have inverses $3\times 2 = 6 \equiv 1 \mod 5$ so we can say that $2^{-1} = 3$.

---

If you are still not sure about $x \equiv 3 \mod 2$. Let's write the congruence as an actual equation:

$$ \begin{array}{ccc} 3x -9 & \equiv & 6k \\ x-3 & \equiv & 2k \end{array} $$

The modulus $6$ got reduced to a $2$ in the process.

Answer 2

I use the following strategy for solving the linear congruence

$$ax \equiv b \mod{m}\quad (\star)$$

Case 1: $\gcd(a, m) = 1$

Implies that the modular multiplicative inverse $(\color{green}{a^{-1}})$ exists, and we solve for $x$ as follows.

$\begin{eqnarray}&&ax &\equiv b&\mod{m}\\\iff&(\color{green}{a^{-1}})&ax &\equiv (\color{green}{a^{-1}})b&\mod{m}\\\iff&&x &\equiv \color{green}{a^{-1}}b&\mod{m}\tag{1}\end{eqnarray}$

Example: $$2x \equiv 1 \mod{5} \iff x \equiv 3 \mod{5}$$ where $\color{green}{2^{-1} = 3}$ was found using the Extended Euclidean algorithm.

Case 2: $\gcd(a, m) > 1$ and $\gcd(a, m) \nmid b$

$\text{No solution exists}\tag{2}$

$\begin{eqnarray}\text{since}&ax &\equiv b \mod{m}\\\iff &ax &= b + mt &(t \in\mathbb{Z})\\\iff &b&= ax - mt \end{eqnarray}$

so $b$ being a linear combination of $a$ and $m$, must be divisible by $\gcd(a, m)$.

Example: $$2x \equiv 3 \mod{4}$$ has no solution, since $\gcd(2, 4) = 2 \nmid 3$.

Case 3: $\gcd(a, m) > 1$ and $\gcd(a, m) \mid b$

Substitute $a = a_0d, b = b_0d, m = m_0d$ in $(\star)$ where $d = \gcd(a, m)$

$\begin{eqnarray}&ax &\equiv b &\mod{m}\\\iff&a_0dx &\equiv b_0d &\mod{m_0d}\\\iff &a_0dx &= b_0d + m_0dt &(t \in\mathbb{Z})\\\iff &a_0x &= b_0 + m_0t &(\text{divide by }d \neq 0) \\\iff&a_0x &\equiv b_0&\mod{m_0}\tag{3}\end{eqnarray}$

which finds itself amenable to solution by invoking case 1, since $\gcd(a_0, m_0) = 1$.

Examples:

• $4x \equiv 2 \mod{10} \underset{(\text{case }3)}{\overset{\gcd(4, 10) = 2}{\iff}} 2x \equiv 1 \mod{5}\underset{(\text{case }1)}{\overset{\gcd(2, 5) = 1}{\iff}} x \equiv 3 \mod{5}$
• $3x \equiv 9 \mod{6} \quad\underset{(\text{case }3)}{\overset{\gcd(3, 6) = 3}{\iff}} x \equiv 3 \mod{2}\quad\underset{(\text{case }1)}{\overset{\text{trivially}}{\iff}} x \equiv 3 \mod{2}$