GCD and Modular Arithmetic

A linear Diophantine equation $ax + by = c$ and a linear congruence $ax \equiv c \pmod b$ are the same object, written differently.

In $ax + by = c$, you're asking: does there exist an integer $x$ such that $c - ax$ is a multiple of $b$? That's exactly $ax \equiv c \pmod b$.

So everything from the Diophantine theory translates directly. But the modular language opens new questions — particularly about inverses — that are worth developing on their own.

---

When is $a$ invertible modulo $m$?

Question. When does $ax \equiv 1 \pmod m$ have a solution?

This is asking: when does $a$ have a multiplicative inverse mod $m$?

Theorem. $a$ has an inverse modulo $m$ if and only if $\gcd(a, m) = 1$.

Proof. $ax \equiv 1 \pmod m$ means $ax - 1 = my$ for some integer $y$, i.e., $ax + m(-y) = 1$. By Bezout, this is solvable iff $\gcd(a, m) \mid 1$, i.e., $\gcd(a, m) = 1$. $\blacksquare$

When $\gcd(a, m) = 1$, the Bezout coefficients give the inverse directly.

Example. Find $3^{-1} \pmod 7$.

From Bezout: $3(5) + 7(-2) = 1$. So $3 \times 5 \equiv 1 \pmod 7$. Thus $3^{-1} \equiv 5 \pmod 7$.

---

Solving $ax \equiv b \pmod m$

Theorem. The congruence $ax \equiv b \pmod m$ has a solution if and only if $d = \gcd(a, m)$ divides $b$.

When solutions exist, there are exactly $d$ solutions modulo $m$.

Method:

1. Check $d = \gcd(a,m)$ divides $b$. If not, no solution.
2. Divide through by $d$: $\frac{a}{d} x \equiv \frac{b}{d} \pmod{\frac{m}{d}}$.
3. Now $\gcd(a/d, m/d) = 1$, so $a/d$ is invertible mod $m/d$. Find the inverse.
4. One solution mod $m/d$. Lift to $d$ solutions mod $m$ by adding multiples of $m/d$.

Example. Solve $6x \equiv 4 \pmod{10}$.

$d = \gcd(6,10) = 2$ and $2 \mid 4$. ✓

Divide: $3x \equiv 2 \pmod 5$.

Inverse of 3 mod 5: $3 \times 2 = 6 \equiv 1 \pmod 5$, so $3^{-1} \equiv 2$.

$x \equiv 2 \times 2 = 4 \pmod 5$.

Lift to mod 10: $x \equiv 4$ or $x \equiv 9 \pmod{10}$. Two solutions, matching $d = 2$.

---

Euler's Totient — how many invertibles?

The number of integers in $\{1, 2, \ldots, m\}$ coprime to $m$ is denoted $\phi(m)$, Euler's totient function.

These are exactly the integers with inverses mod $m$.

Formula. If $m = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$, then:

$\phi(m) = m \prod_{p \mid m} \left(1 - \frac{1}{p}\right)$

Examples:

• $\phi(p) = p-1$ for prime $p$ (all of $1, \ldots, p-1$ are coprime to $p$).
• $\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$.
• $\phi(1000) = 1000 \times (1-\frac{1}{2})(1-\frac{1}{5}) = 400$.

Euler's Theorem. If $\gcd(a, m) = 1$, then $a^{\phi(m)} \equiv 1 \pmod m$.

Fermat's Little Theorem is the prime case: $a^{p-1} \equiv 1 \pmod p$ for prime $p \nmid a$.

---

Chinese Remainder Theorem

When you have a system of congruences with different moduli, the Chinese Remainder Theorem (CRT) tells you when a simultaneous solution exists.

Theorem. The system: $x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2}$

has a unique solution modulo $m_1 m_2$ if and only if $\gcd(m_1, m_2) = 1$.

Why the GCD condition? The system requires $x$ to be in two arithmetic progressions simultaneously. These progressions intersect iff their "step" relationship is compatible — which happens iff $\gcd(m_1, m_2) \mid a_1 - a_2$.

When $\gcd(m_1, m_2) = 1$, this is always satisfied.

Construction. Let $M = m_1 m_2$, $M_1 = m_2$, $M_2 = m_1$.

Find $y_1$ such that $M_1 y_1 \equiv 1 \pmod{m_1}$ (i.e., $m_2 y_1 \equiv 1 \pmod{m_1}$).

Find $y_2$ such that $M_2 y_2 \equiv 1 \pmod{m_2}$.

Then $x = a_1 M_1 y_1 + a_2 M_2 y_2 \pmod M$ is the unique solution.

Example. Solve: $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$.

$\gcd(3,5) = 1$. ✓ $M = 15$, $M_1 = 5$, $M_2 = 3$.

$5y_1 \equiv 1 \pmod 3$: $5 \equiv 2 \pmod 3$, so $2y_1 \equiv 1 \pmod 3$, $y_1 = 2$.

$3y_2 \equiv 1 \pmod 5$: $y_2 = 2$.

$x = 2 \times 5 \times 2 + 3 \times 3 \times 2 = 20 + 18 = 38 \equiv 8 \pmod{15}$.

Check: $8 = 2 \times 3 + 2$ ✓, $8 = 1 \times 5 + 3$ ✓.

General CRT. For pairwise coprime $m_1, \ldots, m_k$, the system has a unique solution modulo $m_1 m_2 \cdots m_k$. The pairwise coprime condition is essential — and it's a GCD condition.

---

Worked problems

Problem 1. Find $x$ such that $x \equiv 1 \pmod 2$, $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$.

$\gcd$ of all pairs is 1. ✓

First combine mod 2 and mod 3: need $x$ odd and $x \equiv 2 \pmod 3$.

$x = 2k+1$ and $2k+1 \equiv 2 \pmod 3 \implies 2k \equiv 1 \pmod 3 \implies k \equiv 2 \pmod 3$.

So $k = 3j+2$, $x = 6j+5$. Combined: $x \equiv 5 \pmod 6$.

Now combine with mod 5: $x \equiv 5 \pmod 6$ and $x \equiv 3 \pmod 5$.

$x = 6j+5$ and $6j+5 \equiv 3 \pmod 5 \implies 6j \equiv -2 \equiv 3 \pmod 5 \implies j \equiv 3 \pmod 5$.

So $j = 5n+3$, $x = 6(5n+3)+5 = 30n+23$.

Answer: $x \equiv 23 \pmod{30}$.

Problem 2. Find all $n$ such that $7 \mid n^2 + 1$.

$n^2 \equiv -1 \equiv 6 \pmod 7$.

Check $n = 1,\ldots,6$: $1,4,2,2,4,1$ (squares mod 7). None equal 6.

So $7 \nmid n^2+1$ for any $n$. No solutions.

Problem 3. How many integers in $\{1, \ldots, 1000\}$ are coprime to 1000?

$1000 = 2^3 \times 5^3$.

$\phi(1000) = 1000\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right) = 1000 \times \frac{1}{2} \times \frac{4}{5} = 400$.

Problem 4. Prove: if $p$ is an odd prime, $ax^2 + bx + c \equiv 0 \pmod p$ has at most 2 solutions mod $p$.

Complete the square (valid since $p$ is odd, so 2 is invertible): reduce to $y^2 \equiv d \pmod p$. This has 0 or 2 solutions (since $\mathbb{Z}/p\mathbb{Z}$ is a field — every nonzero element is either a quadratic residue with 2 roots or a non-residue with 0 roots). $\blacksquare$

---

The connection to look for

When a problem involves "find all $n$ such that [some expression] is an integer," you're usually solving a Diophantine equation. When it involves "find all $n$ such that [some expression] is divisible by $m$," you're solving a congruence. The GCD is the gatekeeper to both.

The full problem set — mixing these techniques — is in GCD and LCM Problems.