a bit of number theory: Notes on Number Theory

Mostly a side note for myself, but might be useful for anyone.

Bezout's Identity (or its equivalence): Given \(a, b \in \mathbb{Z}^+\). Let \(d \in  S = \{ ax+by | ax+by > 0, \text{and} x,y \in \mathbb{Z}\} \) is the smallest element in that set. Then \(\text{gcd}(a,b) = d\).
Proof:
Firstly, note that \(\text{gcd}(a,b) \leq d\). Proof: Suppose that  \(\text{gcd}(a,b) = D > d\). Since \(ax+by = d\), then \(D|ax+by\) implies that \(D|d\), which implies \(D \leq d\), contradiction. (shown)

Next, we can write \(a = qd + r\) where \(0 \leq r < d\) (Can be proven formally), then
\( r = a - qd \)
\( r = a - q(ax+by)\)
\( r = a(1 - qx) + b(-qy)\)
\( r = ax' + by' \)
This implies that if \(r \not= 0\), then \(r \in S\) and hence \(r \geq d\), which contradicts the fact that \( r < d\). Therefore \(r\) must be 0, which means that \(a\) is divisible by \(d\).

With analogous reasoning, we can conclude that \(b\) must also be divisible by \(d\). Hence \(\text{gcd}(a,b) \geq d\). Therefore we have \(d \geq \text{gcd}(a,b) \geq d\), and the proof follows.

Euclid's Lemma:  If \(p | ab\), then \(p | a\) or \(p | b\).
Proof:
If \(p|a\), then the the proposition trivially holds. Hence assume that \(p \nmid a\), then by Bezout's Identity, we have
\(ax + py = 1\) (since \(\text{gcd}(a,p) = 1\) by definition)
\((ab)x + (pb)y = b\)
Notice that \(\text{LHS}\) is divisible by \(p\). This means that \(\text{RHS}\) must also be divisible by \(p\). Hence the proof is complete.

Corollary 1: contrapositive of Euclid's Lemma: If \(p \nmid a\) and \(p \nmid b\), then \(p \nmid ab\).
Corollary 2: Fundamental Theorem of Arithmetic: All positive integers can be uniquely represented by multiplication of prime numbers. (Haha not so corollary actually, but yeah)

Lemma 1: Suppose \(P,A\) are some relatively prime integers. Then if \(AN \equiv AM \mod{P}\) then \(N \equiv M \mod{P}\).

Proof: We have \(AN - AM \equiv 0 \mod{P}\), hence \(P | A(N-M)\). Then \(P | N-M\), which means that \(N-M \equiv 0 \mod{P}\), or equivalently \(N \equiv M\mod{P}\), and the proof follows.

Lemma 2: The ordered set \(S =\{ 0, A, 2A, 3A, \ldots ,(P-1)A \mod{P} \}\) is a permutation of \(T = \{0,1,2,3,\ldots, P-1 \}\).

Proof: (by contradiction) suppose that \(S\) is not a permutation of \(T\), then there must exist \(a_i, a_j \in S\) with \(i \not= j\) such that \(a_i = a_j\). This means that there exist \(N \not= M\) such that \(AN \equiv AM \mod{P}\), which contradicts Lemma 1. Hence \(S\) must be a permutation in the first place.

Existence and Uniqueness of Inversion:  We denote \(a^{-1}\) be the inverse of \(a\) such that \(a \cdot a^{-1} \equiv 1 \mod{N}\). Then for \(a,N\) relatively prime, there always exist a unique inverse of \(a\).
Proof:
Following Bezout's Identity, there exist some \((x,y) \in \mathbb{Z}^2\) such that \(ax+Ny=1\). Taking \(\mod{N}\) on each side, we have \(ax \equiv 1 \mod{N}\). Therefore \(x = a^{-1}\) is an inverse of \(a\). Now, the uniqueness of \(a^{-1}\) follows from Lemma 1.

Wilson's Theorem: \(N\) is prime if and only if \((N-1)! = -1 \mod{N}\)

Proof:
Forward Direction:
Firstly, we need to proof the following claim:
Claim 1: For a prime \(P\) and \(x \in \{1,2,\ldots,P-1\}\) \(x^2 \equiv 1 \mod{P}\) if and only if \(x = 1\) or \(x = P-1\).
Proof:
If \(x \not= 1,P-1\), then we have \(x^2 -1 = (x-1)(x+1) \equiv 0 \mod{P}\). This implies that \(P | (x-1)\) or \(P|(x+1)\) (By Euclid's Lemma), which leads to \(x = 1, P-1\), contradiction.

Now by Existence and Uniqueness of Inversion, for each \(i \in S = \{2,3,\ldots, N-2\}\) there exist a unique \(j \in S\) such that \(ij \equiv 1 \mod{N}\). Hence \(2 \cdot 3 \cdot 4 \cdot \ldots \cdot N-2 \equiv 1 \mod{N}\). Lastly, \(1 \cdot (N-1) \equiv -1 \mod{N}\), therefore combining both products completes the forward proof.

Backward Proof:
Suppose for contradiction that \(N\) is composite which satisfies \((N-1)! \equiv -1 \mod{N}\). Since \(N\) is composite, there is \(1\leq q < N\) such that \(q | N\). since \((N-1)! = aN-1\) for some \(a \in \mathbb{Z}\), we have \( (N-1)! = aN-1 \equiv -1 \mod{q}\). However, \( (N-1)! \) is also \( 0 \mod{q}\), hence a contradiction, and therefore \(N\) must be a prime. (shown)