Fundamental Theorems of Arithmetic

Bézout's Theorem and Applications

Proposition Bézout Identity

Let $a$ and $b$ be two integers, not both zero, and let $d=\gcd(a,b)$.
Then there exist integers $u,v$ such that$$au+bv=d.$$

Proof

Consider the set $S$ of all strictly positive linear combinations of $a$ and $b$:$$S=\{am+bn \mid m,n\in\mathbb{Z}\ \text{and}\ am+bn>0\}.$$

$S$ is not empty: since $a$ and $b$ are not both zero, at least one of $a,-a,b,-b$ is strictly positive and belongs to $S$.
Since $S$ is a non-empty subset of $\mathbb{N}^*$, it admits a least element $d_0$. Let $u$ and $v$ be integers such that $d_0=au+bv$.
Let us show that $d_0$ divides $a$. Perform the Euclidean division of $a$ by $d_0$: $$ a=d_0q+r \quad \text{with } 0\le r0\), then $r\in S$, but \(r
Finally, $d_0$ is the GCD: if $d'$ is any common divisor of $a$ and $b$, then $d'$ divides every linear combination of $a$ and $b$, in particular $d_0=au+bv$. Thus $d'\le d_0$, so $d_0=\gcd(a,b)$.

Proposition Bézout Theorem

Let $a$ and $b$ be two integers, not both zero.
$\gcd(a,b)=1$ if and only if there exist integers $u,v$ such that $au+bv=1$.

Proof

$(\Rightarrow)$ If $\gcd(a,b)=1$, the existence of $(u,v)$ follows from the proposition above.
$(\Leftarrow)$ Suppose there exist integers $u,v$ such that $au+bv=1$. Let $d=\gcd(a,b)$. Since $d\mid a$ and $d\mid b$, we have $d\mid (au+bv)$, hence $d\mid 1$. Since $d$ is a positive integer, $d=1$.

Method Finding Bézout coefficients (extended Euclid)

Let $a$ and $b$ be two integers with $b\neq 0$.

Apply the Euclidean algorithm to $(|a|,|b|)$ to obtain $\gcd(a,b)$.
Perform back-substitution to write $\gcd(a,b)$ as a linear combination of $a$ and $b$.

Example

Find integers $u$ and $v$ such that $47u+39v=1$.

Answer

First, we apply the Euclidean algorithm to find the GCD:

$47 = 39 \times 1 + 8\quad \textcircled{1}$
$39 = 8 \times 4 + 7 \quad \textcircled{2}$
$8 = 7 \times 1 + 1 \quad \textcircled{3}$

Now, we express each remainder from the equations above:

From $\textcircled{3}: 1 = 8 - 7 \times 1$
From $\textcircled{2}: 7 = 39 - 8 \times 4$
From $\textcircled{1}: 8 = 47 - 39 \times 1$

Finally, we "back-substitute" to express $1$ as a combination of $47$ and $39$:$$\begin{aligned}1 &= 8 - (39 - 8 \times 4) \times 1 &&( \text{substituting } 7 \text{ using } \textcircled{2}) \\ 1 &= 8 \times 5 - 39 &&( \text{simplifying}) \\ 1 &= (47 - 39 \times 1) \times 5 - 39 &&( \text{substituting } 8 \text{ using } \textcircled{1}) \\ 1 &= 47 \times 5 - 39 \times 5 - 39 & &(\text{expanding}) \\ 1 &= 47 \times 5 + 39 \times (-6) & &(\text{final form})\end{aligned}$$Thus, a solution is $u=5$ and $v=-6$.

Gauss's Theorem

Theorem Gauss's Theorem

Let $a,b,c$ be non-zero integers.
If $a$ divides the product $bc$ and if $a$ and $b$ are coprime, then $a$ divides $c$.

Proof

Suppose $a \mid bc$ and $\gcd(a,b)=1$.

Since $a \mid bc$, there exists an integer $k$ such that $bc=ka$.
Since $\gcd(a,b)=1$, by Bézout's Theorem, there exist integers $u$ and $v$ such that $$ au+bv=1. $$
Multiplying by $c$, we obtain $$ c(au+bv)=c \implies acu+bcv=c. $$
Rewrite as $a(cu)+(bc)v=c$ and substitute $bc=ka$: $$ a(cu)+(ka)v=c \implies a(cu+kv)=c. $$
Since $(cu+kv)$ is an integer, it follows that $a\mid c$.

Proposition Corollaries of Gauss's Theorem

If an integer is divisible by integers $a$ and $b$ that are coprime, then it is divisible by their product $ab$.
If a prime number divides a product $ab$, then it divides at least one of the factors $a$ or $b$.
If a prime number $p$ divides a product of prime numbers, then $p$ is equal to one of them.
A prime number $p$ is coprime with integers $a$ and $b$ if and only if $p$ is coprime with their product $ab$.

Theorem Fermat's Little Theorem

Let $p$ be a prime number and let $a$ be a non-negative integer not divisible by $p$. Then:$$a^{p-1} \equiv 1 \pmod{p}.$$For any non-negative integer $a$, we have:$$a^p \equiv a \pmod{p}.$$

Proof

We prove the theorem in two steps.

Case where $a$ is not divisible by $p$:
Consider the $p-1$ products $1a,2a,\dots,(p-1)a$ modulo $p$:$$S=\{a,2a,3a,\dots,(p-1)a\}.$$
- Distinct remainders: Let $i$ and $j$ be two distinct integers in $\{1,\dots,p-1\}$. If $ia \equiv ja \pmod{p}$, then $p\mid a(i-j)$.
  Since $p$ is prime and $p\nmid a$, Gauss's Theorem implies $p\mid (i-j)$. But $|i-j| Hence the remainders of \(a,2a,\dots,(p-1)a$ modulo $p$ are all distinct.
- Non-zero remainders: For each $k\in\{1,\dots,p-1\}$, we have $p\nmid k$ and $p\nmid a$, hence $p\nmid ka$. So none of these remainders is $0$.
- Conclusion on the set: Therefore, the set of remainders of $S$ modulo $p$ is exactly $\{1,2,\dots,p-1\}$ in some order.
Multiplying all congruences together gives$$(1a)(2a)\cdots((p-1)a)\equiv 1\cdot 2\cdots (p-1)\pmod{p},$$that is$$a^{p-1}(p-1)! \equiv (p-1)! \pmod{p}.$$Since $p$ is prime, it does not divide any factor $1,2,\dots,p-1$, so $\gcd\bigl((p-1)!,p\bigr)=1$; hence we can cancel $(p-1)!$ modulo $p$, and obtain$$a^{p-1}\equiv 1 \pmod{p}.$$
General case ($a^p \equiv a \pmod{p}$):
- If $p\nmid a$, multiply $a^{p-1}\equiv 1 \pmod{p}$ by $a$ to get $a^p\equiv a \pmod{p}$.
- If $p\mid a$, then $a\equiv 0 \pmod{p}$ and also $a^p\equiv 0 \pmod{p}$, so $a^p\equiv a \pmod{p}$ holds.