# Linear Congruences

We want to solve the equation $ax \equiv b \pmod{m}$, where $a$,$b$ are integers and $m$ is a positive integer. This is called a **linear congruence**.

## Solutions to Linear Congruences
:::danger
**Theorem**
Let $d = \gcd(a,m)$, then
1. If $d\nmid b$, the linear congruence $ax \equiv b \pmod{m}$ has **no solution**.
2. If $d \mid b$, the congruence has exactly $d$ incongruent solutions modulo $m$.
:::

:::warning
**Example** Solve $9x \equiv 12 \pmod{15}$

* We first find $d= \textrm{gcd}(9,15)=3$. Since $3 \mid 12$, we know there will be exactly 3 incongruent solutions.
* To find a particular solution, we can use the extended Euclidean algorithm to find a solution to $9x+15y=\textrm{gcd}(9,15)=3$: $$15 = 9 \cdot 1 + 6, \quad 9 = 6 \cdot 1 + 3, \quad 6 = 3 \cdot 2$$ Working backwards, we get $$3=9−6⋅1=9−(15−9⋅1)=2⋅9−1⋅15$$
* We have $2⋅9−1 \cdot 15=3$. We want to solve for $12$, so we multiply by $4$: $$(4 \cdot 2) \cdot 9 - (4 \cdot 1) \cdot 15 = 12 \implies 8 \cdot 9 - 4 \cdot 15 = 12$$
* This gives us a solution $x=8$. The solutions are of the form $x=x_0 + \frac{m}{d} t$. The general solution is $$x \equiv 8 + 5t \pmod{15}$$
* The 3 incongruent solutions modulo 15 are: $$x \equiv 8, \; 13, \; 3 \pmod{15}$$
:::

## Modular Inverses
:::info
**Definition**
A solution to the congruence $ax \equiv 1 \pmod{m}$ is called the modular inverse of $a$ modulo $m$.
:::

* A modular inverse exists if and only if $\textrm{gcd}(a,m)=1$.
* If $\textrm(a,m)=1$, then there is a unique solution for $x$ modulo $m$.
* If $a\bar{a} \equiv 1 \pmod{m}$ then $\bar{a}$ is the inverse of $a$. We can use this to solve other congruences: if $ax \equiv b \pmod{m}$, we can multiply by the inverse to get $$x \equiv a\bar{a}x \equiv \bar{a}b \pmod{m}$$

:::warning
**Example**
1. Solve $7x \equiv 1 \pmod{31}$
* Since $\textrm{gcd}(7,31)=1$, a unique inverse exists. By inspection, $7 \cdot 9 = 63 \equiv 1 \pmod{31}$. So, the inverse is $x=9$.
2. Solve $7x \equiv 22 \pmod{31}$
* We can multiply both sides by the inverse, 9: $$x \equiv 9\cdot 7x \equiv 9 \cdot 22 = 198 \equiv 12 \pmod{31}$$
3. Solve $7x \equiv 4 \pmod{12}$
* Since $\textrm{gcd}(7,12)=1$, a unique solution exists. We can use the extended Euclidean algorithm to find the inverse of 7 modulo 12: $$12 = 7 \cdot 1 + 5, \quad 7 = 5 \cdot 1 + 2, \quad 5 = 2 \cdot 2 + 1$$
* This shows that $3 \cdot 12−5 \cdot 7=1$, which means $−5 \cdot 7 \equiv 1 \pmod{12}$. The inverse of 7 is −5 modulo 12. Now we solve for $x$: $$x \equiv -5\cdot 7x \equiv -5 \cdot 4 \equiv -20 \equiv 4 \pmod{12}$$
:::

:::success
**Exercies**
1. Find all solutions of each of the following linear congruences.
- a) $2x \equiv 5 \pmod{7}$
- b) $3x \equiv 6 \pmod{9}$
- c) $19x \equiv 30 \pmod{40}$
- d) $9x \equiv 5 \pmod{25}$
- e) $103x \equiv 444 \pmod{999}$
- f) $980x \equiv 1500 \pmod{1600}$
2. Find all solutions to the congruence $$6789783x \equiv 2474010 \pmod{28927591}$$
3. Find an inverse modulo $17$ of each of the following integers.
- a) $4$
- b) $5$
- c) $7$
- d) $16$
:::

## The Chinese Remainder Theorem (CRT)
:::danger
**Theorem (CRT)**
Let $m_1,m_2,\ldots,m_r$ be a set of pairwise relatively prime positive integers (meaning $\textrm{gcd}(m_i, m_j)=1$ for $i \neq j$).

The system of linear congruences:
\begin{aligned}
x &\equiv a_1 \pmod{m_1} \\
x &\equiv a_2 \pmod{m_2} \\
& \; \vdots \\
x &\equiv a_r \pmod{m_r}
\end{aligned}
has a unique solution modulo $M = m_1 m_2 \cdots m_r$.
:::

### Method 1: Direct Formula
:::warning
**Example** Solve the system
$$
x \equiv 1 \pmod{3}, \quad
x \equiv 2 \pmod{5}, \quad
x \equiv 3 \pmod{7}
$$

* $m_1=3$, $m_2=5$, $m_3=7$. They are pairwise relatively prime.
* $M = 3 \cdot 5 \cdot 7 = 105$.
* We find the modular inverse for each $M_i = \frac{M}{m_i}$:
* $M_1 = \dfrac{105}{3} = 35$. Solve $$35y_1 \equiv 1 \pmod{3} \Rightarrow 2y_1 \equiv 1 \pmod{3} \\ \Rightarrow y_1 \equiv 2 \pmod{3}$$
* $M_2 = \dfrac{105}{5} = 21$. Solve $$21y_2 \equiv 1 \pmod{5} \Rightarrow y_2 \equiv 1 \pmod{5}$$
* $M_3 = \dfrac{105}{7} = 15$. Solve $$15y_3 \equiv 1 \pmod{7} \Rightarrow 15y_3 \equiv 1 \pmod{7}$$
* The solution is $x \equiv \sum_{i=1}^r a_i M_i y_i \pmod{M}$: $$x \equiv 1 \cdot 35 \cdot 2 + 2 \cdot 21 \cdot 1 + 3 \cdot 15 \cdot 1 = 157
\equiv 52 \pmod{105}$$
:::

### Method 2: Iterative Substitution
:::warning
**Example** Solve the system
$$
\begin{cases}
x \equiv 1 \pmod{5} \\
x \equiv 2 \pmod{6} \\
x \equiv 3 \pmod{7}
\end{cases}
$$

* From the first congruence, we know $x=5t+1$ for some integer $t$.
* Substitute this into the second congruence: $$5t+1 \equiv 2 \pmod{6} \Rightarrow 5t \equiv 1 \pmod{6} \Rightarrow t \equiv 5 \pmod{6}$$ which means $t=6u+5$ for some integer $u$.
* Substitute this expression for t back into the equation for $x$: $$x = 5(6u+5)+1 = 30u+26$$
* Substitute this into the third congruence: $$30u+26 \equiv 3 \pmod{7} \Rightarrow 2u+5 \equiv 3 \pmod{7} \Rightarrow 2u \equiv -2 \pmod{7}$$ Since $\textrm{gcd}(2,7)=1$, we can divide by 2 to get $u \equiv 6 \pmod{7}$. This means $u=7v+6$ for some integer $v$.
* Substitute the expression for u back into the equation for $x$: $$x = 30(7v+6)+26 = 210v+206$$ The unique solution is $x \equiv 206 \pmod{210}$.
:::

## Related Theorems
:::danger
**Theorem** Let $a$,$b$ be positive integers.
* If $a \equiv r \pmod{b}$ with $0\leq r < b$, then $$2^a -1 \equiv 2^r -1 \pmod{2^b -1}$$
* $\textrm{gcd}(2^a - 1 , 2^b -1) = 2^{\textrm{gcd}(a,b)}-1$.
:::

:::success
**Exercise**

4. Which integers leave a remainder of $1$ when divided by both $2$ and $3$?
5. Find an integer that leaves a remainder of $2$ when divided by either $3$ or $5$, but that is divisible by $4$.
6. Find all the solutions to the system of linear congruences:
$$
\begin{cases}
x \equiv 1 \pmod{2} \\
x \equiv 2 \pmod{3} \\
x \equiv 3 \pmod{5} \\
x \equiv 4 \pmod{7} \\
x \equiv 5 \pmod{11}
\end{cases}
$$
7. A general had 1200 troops at the start of a battle. After the battle, there were 3 left over when they lined up 5 at a time, 3 left over when they lined up 6 at a time, 1 left over when they lined up 7 at a time, and none left over when they lined up 11 at a time. How many troops remained after the battle?
8. Show that the system of congruences:
$$\begin{cases}x \equiv a_1 \pmod{m_1} \\x \equiv a_2 \pmod{m_2}\end{cases}$$ has a solution if and only if $$\gcd(m_1, m_2) \mid (a_1 - a_2)$$ Show that when there is a solution, it is unique modulo $\mathrm{lcm}(m_1, m_2)$.
9. Using Exercise 5, solve each of the following simultaneous systems of congruences:
* a) $$\begin{cases}x \equiv 10 \pmod{60} \\x \equiv 80 \pmod{350}\end{cases}$$
* b) $$\begin{cases}x \equiv 2 \pmod{910} \\x \equiv 93 \pmod{1001}\end{cases}$$
:::