Trivia Definitions
- Let $a$ and $b$ be integers with $a \neq 0$. We say $a$ divides $b$, denoted by $a \mid b$, if there exists an integer $c$ such that $b=ac$. And we say that $a$ is a divisor (or factor) of $b$, and $b$ is a multiple of $a$. If $a$ does not divide $b$, we write $a ∤ b$. If $a \mid b$ and $0<a<b$, then $a$ is called a proper divisor of $b$.
- A divisor of $n$ is called a trivial divisor of $n$ if it is either 1 or $n$ itself. A divisor of $n$ is called a non-trivial divisor if it is a divisor of $n$, but is neither 1, nor $n$.
- If $x \equiv a \;(\mathrm{mod}\; n)$ and $ 0 \leq a \leq n - 1$, then $a$ is called the least (non-negative) residue of $x$ modulo $n$. For any negative numbers, the residue is always positive and measured as the number minus the cloest negative multiple of $n$. For example, $-12 \; \mathrm{mod} \; 7 = 2$.
Euclid Theorem
There are infinitely many primes.
Proof: Suppose that $P_1 ,P_2, \dots ,P_k$ are all the primes. Consider the number $N = P_1 P_2 \cdots P_k + 1$. Since $N$ cannot be divided by any know primes, $N$ itself must be a new prime. But this conclusion contradicts the assertion of the case.
Prime Equal or Less than Factorial + 1
If $n$ is an integer $\geq 1$, then there is a prime $p$ such that $n<p \leq n!+1$.
Proof: Consider the integer $N = n! +1$. If $N$ is a prime, we may take $p = N$ and the theorem holds. If $N$ is not a prime, it must has a prime factor $p$ that $p \mid N$. Suppose $p \leq n$, then $p \mid n!$, hence $p \mid (N - n!)$, which is impossible since $N - n! = 1$. Therefore, $p > n$.
Bertrand–Chebyshev Theorem
For every $n>1$, there is always at least one prime $p$ such that \(n<p<2n\).
Proof: Omitted.
No Prime in Between
If $n$ is an integer $\geq 2$, then there are no primes between $n! +2$ and $n! +n$.
Proof: Since $n!$ is a product of all integers between 1 and $n$, then $2 \mid (n! +2)$, $3 \mid (n! + 3)$, $\cdots, (n-1) \mid (n!+n), n \mid (n! + n)$.
Largest Prime Limit
If $n$ is an composite number, then $n$ has a prime divisor $p$ such that $p \leq \sqrt{n}$.
Proof: Let $p$ be the smallest prime divisor of $n$. If $n=rs$, then $p \leq r$ and $p \leq s$. Hence, $p^2 \leq rs = n$. That is, $p \leq \sqrt{n}$.
This theorem can be used to find all the prime factors of number $n$ with a linear search up to $\sqrt{n}$. This procedure is called the Sieve of Eratosthenes, attributed to the ancient Greek astronomer and mathematician Eratosthenes of Cyrene.
Module Theorems
For all $a,b,c,d \in \mathbb{Z}$ and $ n \in Z^+$, if $a \equiv b \;( \mathrm{mod} \; n)$ and $c \equiv d \;(\mathrm{mod} \; n)$, then:
- $a \pm b \equiv c \pm d \;(\mathrm{mod} \; n)$
- $a \cdot b \equiv c \cdot d \;(\mathrm{mod}\; n)$
- $a^m \equiv b^m \;(\mathrm{mod}\; n)$
Proof: We prove the last one as an illustration of the way to prove the first and second.
We already know that $a \equiv b \;(\mathrm{mod}\; n)$. Let $a = kn + r$ and $b=ln+r$. We have,
\[a^m = [(kn)^m + \cdots + m\cdot(kn)r^{m-1} + r^m]\]and
\[b^m = [(ln)^m + \cdots + m\cdot(ln)r^{m-1} + r^m]\]We can see that any terms before $r^m$ is dividable by $n$, and the last term $r^m \equiv r^m \;(\mathrm{mod}\; n)$.
Residue Class
If $x \equiv a \;(\mathrm{mod}\; n)$, then $a$ is called a residue of $x$ modulo $n$. The residue class of $a$ modulo $n$, denoted by $[a]_n$ (or just $[a]$ if no confusion will be caused), is the set of all those integers that are congruent to $a$ modulo $n$. That is,
\[\begin{align*} [a]_n &= \{ x: x \in \mathbb{Z} \text{ and } x \equiv a \;(\bmod\; n) \} \\ &= \{ a + kn: k \in \mathbb{Z} \} \end{align*}\]In residue classes modulo 2, $[0]_2$ is the set of all even integers, and $[1]_2$ is the set of all odd integers.
Euler’s Totient Function
In number theory, Euler’s totient function counts the positive integers up to a given integer $n$ that are relatively prime to $n$.
It is written using the Greek letter phi as $ \varphi (n)$ or $ \phi (n)$, and may also be called Euler’s phi function.
In other words, it is the number of integers $k$ in the range $1 \leq k \leq n$ for which the greatest common divisor gcd$(n, k)$ is equal to 1. The integers $k$ of this form are sometimes referred to as totatives of $n$.
For example, the totatives of $n = 9$ are the six numbers 1, 2, 4, 5, 7 and 8. They are all relatively prime to 9, but the other three numbers in this range, 3, 6, and 9 are not, since gcd$(9, 3) =$ gcd$(9, 6) = 3$ and gcd$(9, 9) = 9$. Therefore, $\phi(9) = 6$.
As another example, $\phi(1) = 1$ since for $n = 1$ the only integer in the range from 1 to $n$ is 1 itself, and gcd$(1, 1) = 1$.
If two numbers $a$ and $b$ are relatively prime, then $\phi(ab) = \phi(a)\phi(b)$.
Proof: Let $\phi(a) = m$, $\phi(b)=n$, then we have:
\[1 \leq a_1, a_2, \dots, a_m \leq a \text{ , where gcd } (a_i, a)=1\] \[1 \leq b_1, b_2, \dots, b_n \leq b \text{ , where gcd } (b_i, b)=1\]Since $a$ and $b$ are relatively prime, we also know that gcd $(a_i, b)=1$ and gcd $(b_i, a)=1$. So all products of $a_i b_i$ are relatively prime to $ab$, i.e., gcd$(a_i b_i, ab)=1$. And we conclude that there are $mn$ terms of $a_i b_i$.
Multiplicative Inverse Theorem
Two integers $a$ and $b$ are said to be multiplicative inverse if
\[ab \equiv 1 \;(\mathrm{mod} \; n)\]when $n$ is a positive integer greater than 1.
Given any couple of $(a,n)$, $b$ does not always exist. This fact was stated by the following theorem.
The multiplicative inverse $b = 1/a$ modulo $n$ exists if and only if
\[\mathrm{gcd}(a,n)=1\]
Proof: We know from the given condition gcd$(a,n)=1$ that, least common multiple, lcm$(a,n)=an$. Any number less than $an$ is not dividable by both $a$ and $n$. As a result, any element in set A of $ \{a, 2a, 3a, \dots, (n-1)a \} $ cannot be divided by $n$, and we can get the full residue classes modulo $n$, i.e., $ \{ 1, 2, 3, \dots, (n-1) \} $ from set A.
To prove this, first we notice that no element in set A is dividable by $n$, so we have exact $n-1$ residues from set A elements modulo $n$.
Second, we prove no two residues are the same by way of contradiction. Assume the residues of two elements are both $r$, so we can write these two elements as $kn+r$ and $ln+r$.
If we subtract these two numbers, we get $(k-l)n$, which is dividable by $n$. On the other hand, we also know that the subtraction $(k-l)n$ must also be dividable by $a$, as any elements in set A is dividable by $a$, so is their subtraction. This conclustion makes $(k-l)n$, a number less than $an$ also a common multiple of $a$ and $n$. However, it’s impossible as $an$ is the lcm.
We have $n-1$ residues from set A, and each residue is different, so all residues must be the set of $\{ 1, 2, 3, \dots, (n-1) \}$. A one-on-one relation determines that there must be a number $b$, when multipling $a$, that $ab$ from the set A: $ab \equiv 1 \;(\mathrm{mod} \; n)$.
Comment
If we are asked, for any given dividor $n$, how many numbers are its inverse modulo? Now we know this is actually asking how many numbers less than $n$ are relatively prime to $n$? Obviously, the answer is the value of totient function of $n$, $\phi(n)$.
Corollary 1: for all integers $x$ and $y$, not both zero, if $d=\text{gcd}(x,y)$, then there exist integers $s, t$ such that $xs+yt=d$.
Corollary 1 proof: from $d=\text{gcd}(x,y)$, we get
\[1=\text{gcd}\left(\frac{x}{d}, \frac{y}{d}\right)\]Let $a=x/d$ and $n=y/d$, now we have gcd$(a,n)=1$. We can rewrite the equation:
\[\begin{align*} as+nt &=1 \\ as -1 &= -tn \\ \end{align*}\]If we regard $s$ as $b$, the above equation is equal to saying that $ab \equiv 1 \;(\mathrm{mod} \; n)$, just as the Multiplicative Inverse Theorem says.
Corollary 2: The division $x/a$ modulo $n$ (assume that $x/a$ is in its lowest terms) is possible, which is saying that $ab \equiv x \;(\mathrm{mod}\;n)$, if and only if $1/a \;(\bmod\; n)$ exists, i.e., $\text{gcd}(a,n)=1$.
Corollary 2 proof: as $x/a$ is in lowest terms, this means gcd$(x,a)=1$, so also gcd$(x,n)=1$. According to the multiplicative theorem, we have,
\[ab \equiv 1 \;(\mathrm{mod}\; n) \Rightarrow ab*x \equiv 1*x \;(\mathrm{mod}\; n)\]Cancellation for Modular Congruence
For all integers $a, b,c$ and $n$ with $n >1$, if gcd$(c,n)=1$ and $ac \equiv bc \;(\mathrm{mod} \; n)$, then
\[a \equiv b \;(\mathrm{mod} \; n)\]
Proof: From the definition of congruence, we have $n \mid (a-b)c$. But since gcd$(c,n)=1$, then $n \mid (a-b)$. proved.
Fermat’s Little Theorem
Let $a$ be a positive integer, and $p$ a prime. If gcd$(a,p) = 1$, then
\[a^{p-1} \equiv 1 \;(\mathrm{mod} \; p)\]
Proof: First notice that the residues modulo $p$ of all elements in set $A=\{a, 2a, \dots, (p - 1)a\}$ are $\{1,2, \dots,(p - 1) \}$ (residue set) in some order.
We know that the product of all element from set A and the product of all elements from residue set have the same remainder if divided by $p$, as stated below:
\[\begin{align*} a \cdot 2a \cdots (p-1)a &\equiv 1 \cdot 2 \cdots (p-1) \;(\mathrm{mod}\; p) \\ (p-1)! a^{p-1} &\equiv (p-1)! \;(\mathrm{mod}\; p) \\ \end{align*}\]Becuase $(p-1)!$ and $p$ are relatively prime, according to cancellation theorem, we have $a^{p-1} \equiv 1 \;(\mathrm{mod}\; p)$.
Euler’s Theorem
Let $a$ and $n$ be positive integers with gcd$(a,n) = 1$, then
\[a^{\phi(n)} \equiv 1 \;(\mathrm{mod}\; n)\]
Proof: Let set A $=\{ r_1, r_2, \dots, r_{\phi(n)} \}$ be a reduced residue system modulo $n$. The whole residue set is $\{ 1, 2, \dots, (n-1) \}$, so the former is called a reduced system.
There must be $i,j$ from the sub-script in set A that
\[ar_i \equiv r_j \;(\mathrm{mod}\; n)\]because if the above equation doesn’t hold, it means $ar_i = kn+x$, where $x \notin A$. We know that’s impossible as $x$ must be in set $A$, since both $a, r_i$ are relatively prime to $n$, so their product. If $x$ is not the set $A$, which means gcd$(n,x) = d \neq 1$, so
\[ar_i = kn+x \equiv d \; (\mathrm{mod} \;n)\]contradicting to the above condition.
As a result, $\{ ar_1, ar_2, \dots ,ar_{\phi(n)} \}$ is also the same reduced residue system modulo $n$ as set $A$.
We now have the following conclusion:
\[\begin{align*} ar_1 ar_2 \cdots ar_{\phi(n)} &\equiv r_1 r_2 \cdots r_{\phi(n)} \;(\mathrm{mod}\; n) \\ a^{\phi(n)} r_1 r_2 \cdots r_{\phi(n)} &\equiv r_1 r_2 \cdots r_{\phi(n)} \;(\mathrm{mod}\; n) \\ a^{\phi(n)} &\equiv 1 \;(\mathrm{mod}\; n) \end{align*}\]Notice we use cancellation theorem again to reach the last step.
