Pre-Definitions

Let a and b be integers, with $b\neq0$. If there exists an integer c such that b=ac, then b is divisible by a. We use notation $a|b$, otherwise, $a\nmid b$.

Numbers that cannot be factored further is called Primes. A number p is a prime if its only divisors are 1 and p.

The Theorem of Unique Factorization

Every number can be factored into a product of primes in a unique way.

$\Z$ denotes the ring of integers, where 1 or -1 divide everything as the units of $\Z$, zero can be divided by any nonzero integer.

• $a|a, a\neq0$
• If $a|b$ and $b|a$, then $a=\pm b$
• If $a|b$ and $b|c$, then $a|c$
• If $a|b$ and $a|c$, then $a|b+c$​

Consider $n\in\Z$ and p is prime. If n is not 0, there will be a nonnegative integer a allows $p^a|n$ and $p^{a+1} \nmid n $. We call a as the order of n at p, denoted as $\text{ord}_pn$. $\text{ord}_pn$ is the number of times p divides n.

Lemma 1

Every nonzero integer can be written as a product of primes.

Proof:

Assume N is the smallest positive non-prime number, that cannot be written as a product of primes. We have $N=pq$, where $1<p,q<N$​, p,q are not primes. So there is a contradiction.

So we have: $$n=(-1)^{\epsilon(n)}\prod_{p}p^{a(p)}$$ where $\epsilon(n)=1$ when n is negative, 0 when n is positive. $a(p)$ are $\text{ord}_{p}n$​.

Lemma 2

For $a,b\in\Z$, with $b > 0$, there exist unique $q,r\in\Z$ such that $a = qb + r$, where $0 \leq r < b$​.

Proof:

Consider a set $S=\\{ a-xb|\ x \in \mathbb{Z},a-bx\geq 0 \\}$ and $r = a -qb \in S$ as a minimal nonnegative element, $r > 0$.

If $r \geq b$, we will have $0\leq a - (q+1)b < r$​ which is contradiction.

Lemma 3

Define a ideal in ring $\Z$ called $A=(a_1,a_2,...,a_n)$, where $a_n$ is the element of A that form $a_1x_1+a_2x_2+...+a_nx_n$ with $x_n\in \Z$​.

If $a,b\in\Z$, then there is a $d\in\Z$, such that $(a,b)=(d)$​

Proof:

Since a,b are not zero at the same time, so there are positive elements in $(a,b)$​, we can let d be the smallest positive element.

Let's have $c\in(a,b)$, from Lemma 2, we have $c=qd+r$, with $0\leq r<d$. Now we know $c,d\in(a,b)$, follows that $r=c-qd \in (a,b)$. Since d is the least positive element, so it's a contradiction.

The d is called a greatest common divisor(GCD) of a,b if $a|d,b|d$​ and every other common divisor divides d. The positive version of d is the GCD.

Lemma 4

Let $a,b\in\Z$. If $(a,b)=(d)$, then d is a GCD of a,b.

Proof:

By definition, $a\in(d)$ and $b\in(d)$. For any common divisor c, c should divides $ax+by$, which is $c|d$​.

Proposition 1

We can define a,b are relatively prime if $(a,b)=1$ (the positive GCD is 1). If $a|bc$ and $(a,b)=1$, then $a|c$.

Proof:

While $(a,b)=1$, we should have $pa+qb=1$. Therefore, $c(pa)+qbc=c$, where $a|rac$ and $a|sbc$, so $a|c$.

Corollary 1

If p is prime and $p|bc$, then $p|b$ or $p|c$​.

Proof:

Since p is prime, $(p,b)=1$ or $(p,b)=p$. In first case, by proposition 1, $p|c$. In second case, $p|b$.

Corollary 2

If p is prime and $a,b\in \Z$, $\text{ord}_p ab=\text{ord}_p a+\text{ord}_p b$.

Proof:

Let $\alpha$ that $a=p^\alpha c$ and $\beta$ that $b=p^\beta d$ where $p\nmid c$ and $p\nmid d$. Now we have, $ab=p^{\alpha+\beta}cd$ and by Corollary 1. So $\text{ord}_p ab=\alpha+\beta=\text{ord}_p a+\text{ord}_p b$

Proof of Unique Factorization:

By corollary 2: $$\text{ord}_q n=\epsilon(n)\text{ord}_q(-1) + \sum_p a(p)\text{ord}_q(p)$$ Obviously, $\text{ord}_q(-1)=0$ and $\text{ord}q(p)=0$ when $p\neq q$. Only when $p=q$, $\text{ord}_q(p)=1$.

So: $$\text{ord}_qn=a(q)$$ Proved.