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\)
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\)
If a prime number \(p\) divides product \(a.b\) then \(p\) must divide at least of one of \(a\) or \(b\).
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\).
Each natural number is a prime or unique 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\)
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\).
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.