# The fundamental theorem of arithmetic

## The Fundamental Theorem of Arithmetic

### Euclidian division

Euclidian division is the theory for any pair of natural numbers, we can divide one by the other and have a remainder less than the divisor. Formally: $$\forall a \in \mathbb{N} ,\forall b \in \mathbb{N}^+ ,\exists q \in \mathbb{N},\exists r\in \mathbb{N} [(a=bq+r)\land (0\le r < b)]$$

Where $$\mathbb{N}^+$$ refers to natural numbers excluding $$0$$.

That is, every natural number $$a$$ is a multiple $$q$$ of any other natural number $$b$$, plus another natural number $$r$$ less than the other natural number $$b$$.

These are unique. For each jump in $$q$$, $$r$$ falls by $$b$$. As the range of $$r$$ is $$b$$ there is only one solution.

$$17=2.8+1$$

$$9=3.3+0$$

### Bezout’s identity

For any two non-zero natural numbers $$a$$ and $$b$$ we can select natural numbers $$x$$ and $$y$$ such that

$$ax+by=c$$

The value of $$c$$ is always a multiple of the greatest common denominator of $$a$$ and $$b$$.

In addition, there exist $$x$$ and $$y$$ such that $$c$$ is the greatest common denominator itself. This is the smallest positve value of c..

Let’s take two numbers of the form $$ax+by$$:

$$d=as+bt$$

$$n=ax+by$$

Where $$n>d$$. And $$d$$ is the smallest non-zero natural number form.

We know from Euclidian division above that for any numbers $$i$$ and $$j$$ there is the form $$i=jq+r$$.

So there are values for $$q$$ and $$r$$ for $$n=dq+r$$.

If $$r$$ is always zero that means that all values of $$ax+by$$ are multiples of the smallest value.

$$n=dq+r$$ so $$r=n-dq$$.

$$r=ax+by-(as+bt)q$$

$$r=a(x-sq)+b(y-tq)$$

This is also of the form $$ax+by$$. Recall that $$r$$ is the remainder for the division of $$d$$ and $$n$$, and that $$d=ax+by$$ is the smallest positive value.

$$r$$ cannot be above or equal to $$d$$ due to the rules of euclidian division and so it must be $$0$$.

As a result we know that all solutions to $$ax+by$$ are multiples of the smallest value.

As every possible $$ax+by$$ is a multiple of $$d$$, $$d$$ must be a common divisor to both numbers. This is because $$a.0+b.1$$ and $$a.1+b.0$$ are also solutions, and $$d$$ is their divisor.

So we know that the smallest positive solution is a common mutliple of both numbers.

We now need to show that that $$d$$ is the largest common denominator. Consider a common denominator $$c$$.

$$a=pc$$

$$b=qc$$

And as before:

$$d=ax+by$$

So:

$$d=pcx+qcy$$

$$d=c(px+qy)$$

So $$d\ge c$$

### Euclid’s lemma

#### Statement

If a prime number $$p$$ divides product $$a.b$$ then $$p$$ must divide at least of one of $$a$$ or $$b$$.

#### Proof

From Bezout’s identity we know that:

$$d=px+by$$

Where $$p$$ and $$b$$ are natural numbers and $$d$$ is their greatest common denominator.

Let’s choose a prime number for $$p$$. There are no common divisors, other than one. As a result there are exist values for $$x$$ and $$y$$ such that:

$$1=px+by$$

Now, we are trying to prove that if $$p$$ divides $$a.b$$ then $$p$$ must divide at least one of $$a$$ and $$b$$, so let’s multiply this by $$a$$.

$$a=pax+aby$$

We know that $$p$$ divides $$pax$$, and $$p$$ divides $$ab$$ by definition. As a result $$p$$ can divide $$a$$.

### Fundamental Theorem of Arithmetic

#### Statement

Each natural number is a prime or unique product of primes.

#### Proof: existance of each number as a product of primes

If $$n$$ is prime, no more is needed.

If $$n$$ is not prime, then $$n=ab$$, $$a,b\in \mathbb{N}$$.

If $$a$$ and $$b$$ are prime, this is complete. Otherwise we can iterate to find:

$$n=\prod_{i=1} p_i$$

#### Proof: this product of primes is unique

Consider two different series of primes for the same number:

$$s=\prod_{i=1}^n p_i = \prod_{i=1}^m q_i$$

We need to show that $$n=m$$ and $${p}={q}$$.

We know that $$p_i$$ divides $$s$$. We also know that through Euclid’s lemma that if a prime number divides a non-prime number, then it must also divide one of its components. As a result $$p_i$$ must divide one of $${q}$$.

But as all of $${q}$$ are prime then $$p_i$$=$$q_j$$.

We can repeat this process to to show that $${p}={q}$$ and therefore $$n=m$$.

### Existence of an infinite number of prime numbers

#### Existence of an infinite number of prime numbers

If there are a finite number of primes, we can call the set of primes $$P$$.

We identify a new natural number $$a$$ by taking the product of existing primes and adding $$1$$.

$$a=1+\prod_{p\in P} p$$

From the fundamental theorem of arithmetic we know all numbers are primes or the products of primes.

If $$a$$ is not a prime then it can be divided by one of the existing primes to form number $$n$$:

$$\dfrac{\prod^n p_i +1}{p_j}=n$$

$$\dfrac{p_j \prod^n_{i\ne j} p_i +1}{p_j}=n$$

$$\prod^n_{i\ne j} p_i +\dfrac{1}{p_j}=n$$

As this is not a whole number, $$n$$ must prime.

We can do this process for any finite number of primes, so there are an infinite number.