# Congruence and Modular Arithmetic

Invented/Discovered by Carl Friedrich Gauss.

Let $m$ be a fixed positive integer. For integers $a$ and $b$, we say that $a$ is congruent to $b$ *modulo* $m$, and write

$a≡b(modm)$
when $m∣(a−b)$. For integers $a$ and $b$ such that $m∤(a−b)$, we write $a≡b(modm)$. We refer to $≡$ as *congruence*, and $m$ as its *modulus*.

### Elementary Properties of Congruence

One convenient aspect of congruence is that it behaves a lot like equality. For example, equality is an equivalence relation on the integers. This means that it has the following three properties:

*Reflexivity*: For all integers $a$, $a=a$.*Symmetry*: For all integers $a$ and $b$, $a=b⟺b=a$.*Transitivity*: For all integers $a$,$b$ and $c$, $(a=b)∧(b=c)⟹(a=c)$.

Equivalence relation Let $S$ be any set and let $Δ$ be any binary relation on $S$. Then $Δ$ is said to be an equivalence relation if “same thing as above”

#### Some Theorems

**Congruence is an Equivalence Relation (CER)**
For all integers $a$, $b$ and $c$, we have

- $a≡a(modm)$.
- If $a≡b(modm)$, then $b≡a(modm)$.
- If $a≡b(modm)$ and $b≡c(modm)$,then $a≡c(modm)$.

**Proposition 2**
For all integers $a_{1}$, $a_{2}$, $b_{1}$ and $b_{2}$, if $a_{1}≡b_{1}(modm)$ and $a_{2}≡b_{2}(modm)$, then

- $a_{1}+a_{2}≡b_{1}+b_{2}(modm)$,
- $a_{1}−a_{2}≡b_{1}−b_{2}(modm)$,
- $a_{1}a_{2}≡b_{1}b_{2}(modm)$

**Congruence Add and Multiply (CAM)**
For all positive integers $n$, for all integers $a_{1},…,a_{n}$, and $b_{1},…,b_{n}$, if $a_{i}≡b_{i}(modm)$ for all $1≤i≤n$, then

- $a_{1}+a_{2}+⋯+a_{n}≡b_{1}+b_{2}+⋯+b_{n}(modm),$
- $a_{1}a_{2}⋯a_{n}≡b_{1}b_{2}⋯b_{n}(modm)$.

**Congruence Power (CP)**
For all positive integers $n$ and integers $a$ and $b$, if $a≡b(modm)$, then $a_{n}≡b_{n}(modm)$.

**Congruence Divide (CD)**
For all integers $a$, $b$ and $c$, if $ac≡bc(modm)$and $g(c,m)=1$, then $a≡b(modm)$.

### Congruence and Remainders

**Congruent Iff Same Remainder (CISR)**
For all integers $a$ and $b$, $a≡b(modm)$ if and only if $a$ and $b$ have the same remainder when divided by $m$.

**Congruent To Remainder (CTR)**
For all integers $a$ and $b$ with $0≤b<m$, $a≡b(modm)$ if and only if $a$ has remainder $b$ when divided by $m$.

### Linear Congruence

A relation of the form
$ax≡c(modm)$
is called a *linear congruence* in the variable $x$. A *solution* to such a linear congruence is an integer $x_{0}$ such that
$ax_{0}≡c(modm)$

**Linear Congruence Theorem (LCT)**
For all integers $a$ and $c$, with a non-zero, the linear congruence
$ax≡c(modm)$
has a solution if and only if $d∣c$, where $d=g(a,m)$. Moreover, if $x=x_{0}$ is one particular solution to this congruence, then the set of all solutions is given by

${x∈Z:x≡x_{0}(moddm )}$ or, equivalently, ${x∈Z:x≡x_{0},x_{0}+dm ,x_{0}+2dm ,…,x_{0}+(d−1)dm (modm)}$

### Non-Linear Congruence#gap-in-knowledge

For higher powers, we can solve a congruence relation modulo $m$ by checking all $m$ values, which works quite well when $m$ is small. (so essentially brute forcing)

### Congruence Classes and Modular Arithmetic

The *congruence class* modulo $m$ of the integer $a$ is the set of integers
$[a]={x∈Z:x≡a(modm)}$

We define $Z_{m}$ to be the set of $Z_{m}$ congruence classes

$Z_{m}=[0],[1],[2],…,[m−1]$
and we define two operations on $Z_{m}$, *addition* and *multiplication*, as follows:
$[a]+[b]=[a+b]$
$[a][b]=[ab]$

When we apply these operations on the set $Z_{m}$, we are doing what is known as *modular arithmetic*.

### Inverses in $Z_{m}$ (INV $Z_{m}$)

I really struggled with this for MATH135. See MATH135. See Modular Multiplicative Inverse Inverse defintiion

Let $a$ be an integer with $1≤a≤m−1$. The element $[a]$ in $Z_{m}$ has a multiplicative inverse if and only if $g(a,m)=1$. Moreover, when $g(a,m)=1$, the multiplicative inverse is unique.

### Inverses in $Z_{p}$ (INV $Z_{p}$)

For all prime numbers $p$ and non-zero elements [a] in $Z_{p}$, the multiplicative inverse $[a]_{−1}$ exists and is unique.

### Fermat’s Little Theorem (F$l$T)

For all prime numbers $p$ and integers $a$ not divisible by $p$, we have $a_{p−1}≡1(modp)$

#### Corollary for Fermat’s Little Theorem

$a_{p}≡a(modp)$

### Chinese Remainder Theorem (CRT)

For all integers $a_{1}$ and $a_{2}$, and positive integers $m_{1}$ and $m_{2}$, if $g(m_{1},m_{2})=1$, then the simultaneous linear congruences $n≡a_{1}(modm_{1})$ $n≡a_{2}(modm_{2})$

have a unique solution modulo $m_{1}m_{2}$. Thus, if $n=n_{0}$ is one particular solution, then the solutions are given by the set of all integers $n$ such that

$n≡n_{0}(modm_{1}m_{2})$

### Generalized Chinese Remainder Theorem (GCRT)

For all positive integers $k$ and $m_{1},m_{2},…,m_{k}$, and integers $a_{1},a_{2},…,a_{k}$, if $g(m_{i},m_{j})=1$ for all $i=j$, then the simultaneous congruences

$n≡a_{1}(modm_{1})$ $n≡a_{2}(modm_{2})$ $⋮$ $n≡a_{k}(modm_{k})$ have a unique solution modulo $m_{1},m_{2},…,m_{k}$. Thus, if $n=n_{0}$ is one particular solution, then the solutions are given by the set of all integers $n$ such that $n≡n_{0}(modm_{1}m_{2}…m_{k})$

### Splitting Modulus Theorem (SMT)

For all integers $a$ and positive integers $m_{1}$ and $m_{2}$, if $g(m_{1},m_{2})=1$, then the simultaneous congruences $n≡a(modm_{1})$ $n≡a(modm_{2})$

have exactly the same solutions as the single congruence $n≡a(modm_{1}m_{2})$.