📂Number Theory

Congruences in Number Theory

Definition ¹

Given integers $a \equiv b \pmod{m}$, $\iff$, $a$, $b$, $m$, there exists an integer $k$ that satisfies $a = b + mk$.

Theorem

Assuming $a_{1} \equiv b_{1} \pmod{m}$ and $a_{2} \equiv b_{2} \pmod{m}$ are true:

• [1] Addition: $a_{1} + a_{2} \equiv b_{1} + b_{2} \pmod{m}$
• [2] Subtraction: $a_{1} - a_{2} \equiv b_{1} - b_{2} \pmod{m}$
• [3] Multiplication: $a_{1} a_{2} \equiv b_{1} b_{2} \pmod{m}$
• [4] Division: if $\gcd ( c , m ) = 1$, then $$ ac \equiv bc \pmod{m} \implies a \equiv b \pmod{m} $$
• [5] Product of Modulos: if $\gcd ( m_{1} , m_{2} ) = 1$, then $$ \begin{cases} a \equiv b \pmod{ m_{1} } \\ a = b \pmod{ m_{2} } \end{cases} \implies a \equiv b \pmod{ m_{1} m_{2} } $$
• [6] Power of Modulo: if $a \equiv b \pmod{m^n}$, then $a \equiv b \pmod{m}$
• [7] Reduction including modulo: $ax \equiv ay \pmod{am} \iff x \equiv y \pmod{m}$

Explanation

The equation $a \equiv b \pmod{m}$ is called a congruence, and within the Modulo $m$, $a$ is said to be congruent to $b$. The modulo is often simply pronounced as modulo $m$, as $\pmod{}$ is used as is in the formula.

In theorem [4], without the condition $\gcd(c,m) = 1$, it is not possible to divide both sides by $c$. For example, $ 8 \equiv 20 \pmod{12}$ holds, but $ 2 \equiv 5 \pmod{12}$, which is divided by $4$ on both sides, does not hold.

In dealing with simple number theory problems, $m$ is often set to be a prime number, but as things become complicated, $m$ is set to be a composite number. Therefore, it’s necessary to understand the overall properties of congruence equations.

Proof

[5]

Because of $a \equiv b \pmod{m_{1}}$, there exists an integer $n_{1}$ satisfying: $$ a = b + n_{1} m_{1} $$ Because of $a \equiv b \pmod{m_{2}}$, there exists an integer $n_{2}$ satisfying: $$ a = b + n_{2} m_{2} $$ Since $m_{1}$ and $m_{2}$ are coprime, for both equations to be satisfied simultaneously, $n_{1}$ must be a multiple of $m_{2}$, and $n_{2}$ must be a multiple of $m_{1}$. Thus, there exists an integer $n_{3}$ satisfying: $$ a = b + n_{3} m_{1} m_{2} $$ Then, by the definition of congruence: $$ a \equiv b \pmod{ m_{1} m_{2} } $$

■

[6]

If $a \equiv b \pmod{m^n}$, then there exists an integer $k$ satisfying: $$ a = b + m^n k $$ Detaching $m^{n-1}$ gives: $$ a = b + m^{n} k \cdot n = b + m \cdot (m^{n-1} k) $$ Thus, there exists an integer $m^{n-1} k$ satisfying: $$ a \equiv b \pmod{m} $$

■

[7]

For some integer $k$, $$ \begin{align*} ax \equiv ay \pmod{am} & \iff ax = ay + amk \\ & \iff x = y + mk \\ & \iff x \equiv y \pmod{m} \end{align*} $$

■