CONGRUENCE AND MODULAR ARITHMETIC
A congruence relation, defined as $a\text{R}b \iff a \equiv b \pmod m$ (where $\text{R}$ represents a relation), is an equivalence relation i.e.a relation wherein:
If $a \equiv b \pmod m$ and $c \equiv d \pmod m$, then the following hold true:
For each of the above, the proof is easily obtained by using the fact that $a \equiv b \pmod m \implies m \mid (a - b) \implies a = km + b$ for some $k \in \mathbb{Z}$.
If $a \equiv b \pmod m$, then $a^k \equiv b^k \pmod m$ for any positive integer $k$.
NOTE ON CONVERSE: Converse is not necessarily true. As counterexample, take $a = 2, b = 4, k = 2$ and $m = 3$.
We can use mathematical induction to prove this.
If $a \equiv b \pmod m$ and $k$ is a constant, then the following hold true:
NOTE ON CONVERSES: Converse of (1) is true i.e. $a ± k \equiv b ± k \pmod m \implies a \equiv b \pmod m$. However, converse of (b) is not necessarily true i.e. $ak \equiv bk \pmod m \not \implies a \equiv b \pmod m$. As a counterexample, consider $a = 3, b = 2, k = 2$ and $m = 2$ as a counterexample.
If $ak \equiv bk \pmod m$, then $a \equiv b \pmod m/d$, where $d = \gcd(k, m)$.
Note that $k = q_1 d$ and $m = q_2 d$, where $q_1,q_2 \in \mathbb{Z}$. Also show that $q_1$ and $q_2$ are coprime. Then, use the fact that:
$ak \equiv bk \pmod m$
$\implies m \mid (ak - bk)$
$\implies ak - bk = cm, where c \in \mathbb{Z}$
(Remember that $q_2 = \frac{m}{d}$)
If $k$ and $m$ are coprime, then $ak \equiv bk \pmod m \implies a \equiv b \pmod m$
For any integers $a$ and $b$, $a \equiv b \pmod m$ iff $a$ and $b$ leave the same remainder when divided by $m$.
Use division algorithm for $a$ and $m$, and $b$ and $m$ (with $m$ always the divisor). Then, use the fact that:
$a \equiv b \pmod m$
$\implies m \mid (a - b)$
$\implies a - b = km$, where $k \in \mathbb{Z}$
Substitute $a$ and $b$ with the expressions obtained using division algorithm. Then, you will obtain the difference of the remainders as an integer multiple of $m$. But note that both remainders are positive integers less than $\mid m \mid$. Hence, they must be less than or equal to the absolute value of any integer multiple of $m$. But these two conditions can only hold if the integer multiple of $m$ here is 0. Hence, the difference of remainders is 0.
Use division algorithm for b and m (with m the divisor). So, we would get $b = qm + r$, where $q,r \in \mathbb{Z}$ and $0 \leq r < m$. Then, use the fact that:
$a \equiv b \pmod m$
$\implies m \mid (a - b)$
$\implies a - b = km$, where $k \in \mathbb{Z}$
$\implies a = km + b$
Substitute $b$ with the expression obtained using division algorithm. Then, you will obtain $a = (k+q)m + r$, where $(k+q),r \in \mathbb{Z}$ and $0 \leq r < m$. But by the division algorithm, this means that $r$ is the remainder of the division between $a$ and $m$.
An equivalence relation $\text{R}$ on a set $S$ partitions the set $S$ into equivalence classes.
Congruency and modular arithmetic
The linear congruence $ax \equiv b\pmod n$ has a solution iff $\gcd(a,n) \mid b$.
Convert the linear congruence into a linear Diophantine equation.
(Extension of theorem 1)
Let $d = \gcd(a,n)$. If $d \mid b$, then the linear congruence $ax \equiv b\pmod n$ has exactly $d$ mutually incongruent (or pairwise incongruent) solutions.
Use the associated Diophantine equation to obtain the following general solution for $x$, i.e. $x = x_0 + \frac{n}{d}t$, where $x_0$ is a particular solution and $t$ is any integer. Take $t = 0, 1, 2… d-1$, and hence get a list of d solutions. For convenience, let’s name this list $S$. You must hence:
NOTE: This theorem is useful in solving systems of linear congruences, but not strictly a part of linear congruences, and is more part of division and divisibility.
STATEMENT VARIATION 1:
If we know the remainders of the Euclidean i.e. integer division of an integer x by several integers n_1, n_2… n_k, i.e. if we have…
$r_1 = x \bmod n_1$
$r_2 = x \bmod n_2$
.
.
.
$r_k = x \bmod n_k$
… then we can uniquely determine the remainder of the division of x by the product of the above integers i.e. by $n_1 n_2… n_k$, provided that these integers i.e. $n_1, n_2… n_k$, are pairwise coprime.
STATEMENT VARIATION 2:
If $n_1, n_2… n_k$ are pairwise coprime, and r_1, r_2… r_k are integers such that $0 \leq r_i < n_i \forall i$, then there exists exactly one integer $x$ such that $0\leq x < N$ (where $N = n_1 n_2… n_k$) and the remainder of the division of $x$ by $n_i$ is $r_i \forall i$, i.e. $x \bmod n_i = a_i \forall i$
STATEMENT VARIATION 3:
Let $n_1, n_2… n_k$ be integers greater than 1, and let $N = n_1 n_2… n_k$. If $n_1, n_2… n_k$ are pairwise coprime, and $a_1, a_2… a_k$ are any integers (no conditions here), then the following system of linear congruences…
$x \equiv a_1 \pmod n_1$
$x \equiv a_2 \pmod n_2$
.
.
.
$x \equiv a_k \pmod n_k$
… has a solution (for $x$). Furthermore, if $x_1$ and $x_2$ are two solutions of the above system, then $x_1 \equiv x_2 \pmod N$.
Let $p$ be a prime such that $p$ does not divide $a$. Then:
$a^(p-1) \equiv 1 \pmod p$
a):
Consider 1st $p-1$ multiples of $a$ i.e. $S = a, 2a, 3a… (p-1)a$
b):
Prove that the elements of $S$ are mutually incongruent.
c):
Show that if elements of S are divided by p, the only remainders possible are $1, 2… (p-1)$
d):
Note that steps (b) and (c) $\implies$ remainders for every division between $S$ and $p$ are unique $\implies$
$r_1 = a \bmod p$
$r_2 = 2a \bmod p$
.
.
.
$r_(p-1) = (p-1) \bmod p$
such that $r_1, r_2… r_(p-1)$ are all distinct.
e) Hence, from (d), we obtain:
$p \mid a - r_1$
$p \mid 2a - r_2$
.
.
.
$p \mid (p-1)a - r_(p-1)$
Hence, we obtain:
$a \equiv r_1 \pmod p$
$2a \equiv r_2 \pmod p$
.
.
.
$(p-1)a \equiv r_(p-1) \pmod p$
Hence, we obtain:
$(p-1)! a^(p-1) = r_1 r_2…r_(p-1) \pmod p$
But, from (d), we have that:
$\set{r_1, r_2… r_(p-1)} = \set{1, 2… p-1}$
$\implies (p-1)! a^(p-1) \equiv 1 \cdot 2…(p-1) \pmod p$
$\implies (p-1)! a^(p-1) \equiv (p-1)! \pmod p$
From the result $uk = vk \pmod w \implies u = v \pmod w/d$, where $d = \gcd(k, w)$. Hence, we get $a^(p-1) \equiv 1 \pmod p$ (since $\gcd((p-1)!, p) = 1$)
If $p$ is a prime, then:
$(p-1)! \equiv -1 \pmod p$ i.e.
$(p-1)! + 1 \equiv 0 \pmod p$ i.e.
$(p-1)! \equiv (p-1) \pmod p$
Let $p$ be a prime. Define $S = \set{1, 2 … p-1}$. Since $p$ is prime, all elements of $S$ are coprime to $p$. Now, define $a \in S \implies \gcd(a,p) = 1$, since $a$ is coprime to $p$. Now, consider the linear congruence:
$ax \equiv 1 \pmod p$ …(1)
Note that $\gcd(a,p) = 1 \mid 1 \implies$ (1) has a solution for $x$. Let $x_0$ be a solution of $(1)$. This implies that:
$ax_0 \equiv 1 \pmod p$ is true
$\implies x = x_0 + \frac{tp}{\gcd(a,p)} = x_0 + tp$ for some $t \in \mathbb{Z}$ …(2)
NOTE: The above gives the general solution for (1). Note also that the above result is given in the section for linear congruences.
Now, note that (2) implies we can always get an $x$ for (1) such that $0 < x < p$. To justify this statement, observe the cases given in the following side note (note that $\text{div}$ means integer division, i.e. obtaining only the integer quotient of a division).
Start of side note…
Case 1:
If $\mid x_0 \mid > p$ and $x_0 < 0$, put $t = (x_0 \text{div} p) + 1$.
Case 2:
If $\mid x_0 \mid > p$ and $x_0 > 0$, put $t = -(x_0 \text{div} p)$.
Case 3:
If $\mid x_0 \mid < p$ and $x_0 < 0$, put $t = 1$.
Case 4:
If $\mid x_0 \mid < p and x_0 > 0$, put $t = 0$
In all the above cases, we would get 0<x<p by choosing the right t.
Back to the main proof…
Let $x_1$ be a solution of (1) such that $0 < x_1 < p$ i.e. such that $x_1 \in S$. Hence, we have that:
$ax_1 \equiv 1 \pmod p$ is true, where $x_1 \in S$ …(3)
(3) $\implies a^2 \equiv 1 \pmod p$
$\implies p \mid a^2 - 1$
$\implies p \mid (a-1)(a+1)$
Since $a \in S$, we have that:
Note that $(a = 1$ or $a = p-1) \implies a=x_1$. To justify this:
Consider $a=1$:
(3) $\implies x_1 \equiv 1 \pmod p, x_1 \in S$
i.e $x_1$ leaves 1 as remainder when divided by $p$
$\implies x_1 = 1 \implies x_1 = a = 1$
Consider $a = p-1$
(3) $\implies (p-1)x_1 \equiv 1 \pmod p, x_1 \in S$
$\implies px_1 - x_1 \equiv 1 \pmod p, x_1 \in S$
$\implies p \mid px_1 - x_1 - 1$
Now, note that:
$p \mid px_1 \implies p \mid - x_1 -1$
$\implies p \mid x_1 + 1$
Since $x_1 \in S$, we must have:
$x_1 = p-1$
$\implies x_1 = p \implies x_1 = a = p-1$
We have seen above that $a=x_1 iff a=1 or a=p-1$. Hence, if $a \neq x_1, a \neq 1$ and $a \neq -1$. Hence, $a \in T = \set{2, 3 … p-2}$. Now, (3) $\implies$ we can always find a solution for $x$ in (1) such that $x \in S$. But we found that that $a = x \iff (x = 1$ or $x = p-1)$. Hence, equivalently, we have $a \neq x \iff (x \neq 1$ and $x \neq p-1)$. Hence, if a \in T, then $x \in T$. Hence, we can obtain…
$2x_2 \equiv 1 \pmod p$
$3x_3 \equiv 1 \pmod p$
.
.
.
$(p-2)x_(p-2) \equiv 1 \pmod p$
… where $x_i \in T \forall \text{ } i = 1, 2 … (p-2)$ … (*)
Now, we must prove $x_2, x_3 … x_(p-2)$ are distinct form each other. To prove this, we can use proof by contradiction, where we assume the following congruences from (*) hold…
$a_i x_k \equiv 1 \pmod p$
$a_j x_k \equiv 1 \pmod p$
… such that $a_i \neq a_j$
Hence, note that $\set{x_2, x_3 … x_(p-2)} = T$. Also note that $\set{a_2, x_3 … a_(p-2)} = T$, by definition. Now, also note that $p$ is a prime greater than 3. Hence, $T$, which has $p-3$ elements, has an even number of elements. Hence, we can divide $T$ into two equally sized partitions. Hence, consider the following selection process:
Define a list $L$
Consider $2x_2 \equiv 1 \pmod p$; put 2 and $x_2$ in $L$
Consider $3x_3 \equiv 1 \pmod p$; pnly if $3,x_3 \not \in L$, put both in $L$
Consider $4x_4 \equiv 1 \pmod p$; only if $4,x_4 \not \in L$, put both in L
.
.
.
Consider $(p-2)x_(p-2) \equiv 1 \pmod p)$; Only if $(p-2),x_(p-2) \not \in L$, put both in $L$
Hence, we obtain:
$a_1 x_{q_1} \equiv 1 \pmod p$
$a_2 x_{q_2} \equiv 1 \pmod p$
.
.
.
$a_k x_{q_k} \equiv 1 \pmod p$
Since we have that…
… we know that:
Hence, we get that using the multiplicative property of congruence:
$a_1 x_{q_1} a_2 x_{q_2}… a_k x_{q_k} \equiv 1 \pmod p$
$\implies 2 \cdot 3…(p-2) \equiv 1 \pmod p$
$\implies 2 \cdot 3…(p-2)(p-1) \equiv (p-1) \pmod p$
$\implies (p-1)! \equiv (p-1) \pmod p$
$\implies (p-1)! \equiv -1 \pmod p$