
# 3.1: Basics and the FTA


$$\newcommand{\NN}{\mathbb N}$$
$$\newcommand{\RR}{\mathbb R}$$
$$\newcommand{\QQ}{\mathbb Q}$$
$$\newcommand{\ZZ}{\mathbb Z}$$
$$\newcommand{\Cc}{\mathcal C}$$
$$\newcommand{\Dd}{\mathcal D}$$
$$\newcommand{\Ee}{\mathcal E}$$
$$\newcommand{\Ff}{\mathcal F}$$
$$\newcommand{\Kk}{\mathcal K}$$
$$\newcommand{\Mm}{\mathcal M}$$
$$\newcommand{\Pp}{\mathcal P}$$
$$\newcommand{\ind}{\operatorname{ind}}$$
$$\newcommand{\ord}{\operatorname{ord}}$$

First of all, we make the following definition.

Definition: Prime

We say $$p\in\NN$$ is prime if $$p>1$$ and the only natural numbers which divide $$p$$ are $$1$$ and $$p$$.

Example $$\PageIndex{1}$$

Some primes are $$2$$, $$3$$, $$5$$, $$7$$, $$11$$, $$13$$, and $$17$$. Notice $$2$$ is the only even prime (clearly – any other would be a multiple of $$2$$ and hence could not be prime), and has some unusual properties – the joke is that “$$2$$ is the oddest prime.”

The largest prime known to humans at the time of this writing is $2^{57,885,161}-1$ which was proven to be prime in January of 2013 by a distributed computer program called GIMPS [the Great Internet Mersenne Prime Search] running on hundreds of machines across the Internet. In contrast, we also use the following term

Definition: Composite

A number $$c\in\NN$$ which is greater than $$1$$ and not prime is called composite.

How far does a naive, brute-force check have to go in order to see if a number is composite?

Theorem $$\PageIndex{1}$$

If $$n$$ is a composite, then it has a positive divisor $$d$$ satisfying $$d\le\sqrt{n}$$.

Proof

Suppose $$n$$ is composite. Then it has some divisor $$a\in\NN$$. Notice that $$n=a\cdot\dfrac{n}{a}$$, so $$\dfrac{n}{a}\in\NN$$ is also a divisor. But $$a$$ and $$\dfrac{n}{a}$$ cannot both be less than $$\sqrt{n}$$, because if they were we would have $n=a\cdot\dfrac{n}{a}<\sqrt{n}\cdot\sqrt{n}=n$ which would be a contradiction. Hence either $$a$$ or $$\dfrac{n}{a}$$ is the divisor $$d$$ promised by the theorem statement.

Euclid’s Lemma (Lemma 2.1.1) takes a particularly nice form if the divisor involved is prime:

Proposition $$\PageIndex{1}$$

Suppose $$p$$ is a prime and $$a,b\in\ZZ$$. If $$p\mid ab$$ then $$p\mid$$ or $$p\mid b$$.

Proof

Notice that $$\gcd(p,a)\mid p$$, therefore $$\gcd(p,a)$$ is either $$1$$ or $$p$$ since $$p$$ is prime. But also $$\gcd(a,p)\mid a$$, so either $$p\mid a$$ or $$\gcd(a,p)=1$$. If $$p\mid a$$, we are done. If not, since therefore $$\gcd(a,p)=1$$, Euclid’s Lemma 2.1.1 tells us that $$p\mid b$$.

A more general form of this is

Corollary $$\PageIndex{1}$$

Suppose $$p$$ is a prime, $$k\in\NN$$, and $$a_1,\dots,a_k\in\ZZ$$. Then if $$p\mid a_1\dots a_k$$, it follows that $$p$$ divides at least one of the $$a_j$$.

Proof

Left to the reader (use induction on $$k$$).

This leads to the aptly named

Theorem $$\PageIndex{2}$$: The Fundamental Theorem of Arithmetic

Let $$n\in\NN$$, $$n\ge2$$. Then $$\exists k\in\NN$$ and primes $$p_1,\dots,p_k$$ such that $$n=p_1\dots p_k$$. Furthermore, if $$l\in\NN$$ and $$q_1,\dots,q_l$$ are also primes such that $$n=q_1\dots q_l$$, then $$l=k$$ and the factorization in terms of the $$q$$’s is merely a reordering of that in term s of the $$p$$’s.

Proof

We use the Second Principle of Mathematical induction for the existence part. The general statement we are proving is $$\forall n\in\ZZ,\ n>1\Rightarrow S(n)$$, where $$S(n)$$ is the statement “$$\exists k\in\NN$$ and primes $$p_1,\dots,p_k$$ such that $$n=p_1\dots p_k$$.”

As the base case, say $$n=2$$. Then $$k=1$$ and $$p_1=2$$ works.

Now assume $$S(k)$$ is true for all $$k<n$$. If $$n$$ is prime, then $$k=1$$ and $$p_1=n$$ works. So suppose $$n$$ is instead composite, with divisor $$d\neq1,n$$. Then both $$d,\dfrac{n}{d}<n$$, so by the inductive hypothesis $$\exists k,k^\prime\in\NN$$ and primes $$p_1,\dots,p_k,p^\prime_1,\dots,p^\prime_{k^\prime}$$ such that $$d=p_1\dots p_k$$ and $$\dfrac{n}{d}=p^\prime_1\dots p^\prime_{k^\prime}$$. So then $$n$$ is the product $n=p_1\dots p_k\cdot p^\prime_1\dots p^\prime_{k^\prime}$ of the $$k+k^\prime$$ primes. Hence $$S(n)$$ is true as well, and so prime factorizations always exist.

Now suppose $$n\in\ZZ$$ satisfies $$n>1$$ and $$\exists k,l\in\NN$$ and both primes $$p_1,\dots p_k$$ and $$q_1,\dots,q_l$$ such that $p_1\dots p_k = n = q_1\dots q_l\ .$ Certainly $$p_1$$ divides the left hand side of these dual expressions for $$n$$. Then by Corollary 3.1.1, $$p_1$$ divides one of the $$q_j$$, which means it must be that $$p_1=q_j$$ since they are prime. Removing the $$p_1$$ from the left and the $$q_j$$ from the right, we get $p_2\dots p_k = n = q_1\dots q_{j-1}\cdot q_{j+1}\dots q_l\ .$ Continuing in this way, either we get the uniqueness statement in the theorem, or we run out of $$p$$’s or $$q$$’s. However, we cannot run of of primes on one side before the other, because that would make a product of primes on one side equal to $$1$$, which is impossible.

Exercise $$\PageIndex{1}$$

1. Provide all the details of the proof of Corollary 3.1.1.
2. State and prove a theorem about the prime factorizations of numbers $$a,b\in\NN$$ and of their gcd.
3. A number $$n\in\ZZ,\ n>1$$ is called square-free if it is not divisible by the square of any natural number other than $$1$$. Prove that an $$n\in\ZZ,\ n\ge1$$ is square-free if and only if it is the product of distinct primes.