Friday, August 29, 2014

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)