5.2 Primes and the Fundamental Theory of Arithmetic
We now move on to look at a fundamental property of \(\mathbb{Z}\). First we need some more definitions.
We say an integer \(p>1\) is prime if for all \(a,b \in \mathbb{Z}\) if \(p\mid ab\) then \(p\mid a\) or \(p\mid b\).
Equivalently, if \(ab \in p\mathbb{Z}\) then \(a \in p\mathbb{Z}\) or \(b \in p\mathbb{Z}\).An integer \(p>1\) is a prime if and only if the only positive divisors of \(p\) are \(1\) and \(p\).
We prove both directions separately.
\(\Rightarrow).\) For a proof by contradiction, suppose \(p\) is prime but there exists a positive divisor \(a\) which is not \(1\) or \(p\). Then we have \(1<a<p\) and there exists \(b \in \mathbb{Z}\) such that \(ab = p\). Since \(p>1\) and \(a>1\), we have \(1<b<p\). Now \(p=ab\) means \(p|ab\). However, \(p\nmid a\) and \(p\nmid b\) since \(1<a,b<p\). Hence \(p\) is not prime, which is a contradiction. So if \(p\) is prime, then the only positive integers of \(p\) are \(1\) and \(p\).
\(\Leftarrow).\) Suppose \(p>1\) is an integer whose only positive divisors are \(1\) and \(p\). Let \(a,b \in \mathbb{Z}\) be such that \(p \mid ab\). If \(p\mid a\) then we satisfy the definition of \(p\) being prime. So suppose \(p\nmid a\), then \(\gcd(p,a) = 1\) (since \(p\) has no other positive divisors). By Corollary 5.8, we have that \(p\mid b\), hence satisfying the definition of being prime.□
Most student are used to Theorem 5.13 to be the definition of a prime number. In fact, Euclid introduced prime numbers to be ones that satisfied that definition (he used the Greek word protos meaning first, as prime numbers are the first numbers from which every other numbers arise. The word prime comes from Latin “primus” which also means first). Around the 19th century, it was discovered that there are some rings in which elements satisfying Definition 5.12 and elements satisfying Theorem 5.13 are different. Following this, mathematician decided that elements satisfying Theorem 5.13 should be called irreducible (they can not be reduced into smaller elements). You can learn more about irreducible elements in general rings in a unit like Algebra 2.
Let \(n\in\mathbb{Z}_+\) be such that \(n>1\). Then there exist primes \(p_1,\dots,p_r\) such that \(n=p_1p_2\dots p_r\).
Furthermore, this factorisation is unique up to re-arranging, that is if \(n=p_1\dots p_r=q_1\dots q_t\) where \(q_1,\dots,q_t\) are also primes, then \(r=t\) and, if we order \(p_i\) and \(q_i\) such that \(p_i\leq p_{i+1}\) and \(q_i \leq q_{i+1}\) for all \(i\), then \(p_i=q_i\) for all \(i\).
We use a proof by induction to show the existence of the prime divisors of \(n\). Let \(P(n)\) be the statement that “there exists some primes \(p_1,\dots,p_r\) such that \(n=p_1\dots p_r\)”. We note that \(2\) is prime, hence \(P(2)\) holds. Assume \(P(k)\) holds for all \(k\leq n\) and consider \(P(n+1)\).
If \(n+1\) is prime, then \(P(n+1)\) holds. If \(n+1\) is composite, then it has a non-trivial divisor, say \(a\). So \(n+1=ab\). Note as before that \(1<a,b<n+1\). So by the induction hypothesis, both \(a\) and \(b\) can be written as a product of prime. Hence \(n\) can be written as a product of prime and \(P(n)\) holds. So by the principle of (strong) induction, we have all integers \(n\geq 2\) can be written as a product of primes.
We use a proof by contradiction to show the uniqueness (up to re-ordering) of the prime divisors of \(n\). Let \(S\) be the subset of \(\mathbb{Z}_+\) containing the integers whose factorisation is not unique. For a contradiction, we assume \(S\) is non-empty, hence by the Well Ordering Principle, it has a least element, call it \(n\). Suppose \(n=p_1\dots p_r=q_1\dots q_t\) where \(p_i\) and \(q_i\) are primes.
Note that since \(p_1|n\) we have \(p_1\mid q_1\dots q_t = q_1(q_2\dots q_t)\). If \(p_1\nmid q_1\), by definition \(p_1\mid (q_2\dots q_t)\). In this case, if \(p_1 \nmid q_2\) then by definition \(p_1 \mid (q_3\dots q_t)\). Continuing this argument, we see that there exists \(i\) such that \(p_1\mid q_i\). Without loss of generality, re-order the \(q_i\)’s so that \(p_1|q_1\). Since \(q_1\) is prime, it has two positive divisors, \(1\) and \(q_1\). Since \(p_1>1\) (as it is prime), and a divisor of \(q_1\) we deduce \(p_1 = q_1\). Hence \(p_1\dots p_r=q_1\dots q_t\) implies \(p_2\dots p_r=q_2\dots q_t=a\). Since \(p_2\dots p_r=q_2\dots q_t\) is two distinct prime factorisation of \(a\), we have \(a\in S\). However, \(a<n\) contradicting the minimality of \(n\). Hence \(S\) must be empty, so every \(n>1\) has a unique factorisation.□
There are infinitely many prime numbers in \(\mathbb{Z}_+\).
To the contrary, suppose that there are only finitely many primes, say \(p_1,p_2,\ldots,p_m\) for some \(m\in\mathbb{Z}_+\). Set \(n=p_1 p_2\cdots p_m+1\). Clearly \(m \ge 2\), as \(2\) is a prime. Hence \(n>1\). By the Fundamental Theorem of Arithmetic, \(n\) can be factored as a product of primes. So we let \(q\) be some prime dividing \(n\). Then \(n=qk\) for some \(k\in \mathbb{Z}_+\). Since there are only finitely many primes, we must have that \(q=p_j\) for some \(j\in \mathbb{Z}_+\), \(1\le j\le m\). Hence, \[n=p_jk=p_1p_2\cdots p_m+1,\] so \[1=n-p_1p_2\cdots p_m=p_j\left(k-\frac{p_1p_2\cdots p_m}{p_j}\right).\] Hence the prime \(p_j\) divides \(1\), which is a contradiction. The result follows.
□
The above proof is often called Euclid’s proof as it can be found in his books the elements. The proof follows directly his proof that every number can be factorised as a product of primes. Euclid did not prove the uniqueness of such factorisation, instead a proof of the uniqueness of such factorisation can be found in Diophantus of Alexandria (Greek mathematician, 200BC - 284BC) book Arithmetica (the title presumably linked to the Greek word arithmos meaning “number”).
The Fundamental Theorem of Arithmetic can be used to find solutions to equations such as the one below.
Problem: Find all square numbers \(n^2 \in \mathbb{Z}_+\) such that there exists a prime \(p\) with \(n^2 = 5p+9\).
Solution: First, we suppose we have a prime \(p\) such that \(5p+9=n^2\) for some \(n\in\mathbb{Z}_+\). We want to find constraints on \(p\). We have that \(5p=(n+3)(n-3).\) By the Fundamental Theorem of Arithmetic, the only positive factors of \(5p\) are \(1, 5, p\) and \(5p\). That is \(n+3 \in \{1, 5, p, 5p\}\), so let us analyse these four cases.
Suppose \(n+3=1\). Then \(n-3=-5\), that is \(5p=(n+3)(n-3)=-5\). But this implies that \(p=-1\), which is not prime. It follows that \(n+3\neq 1\).
Suppose \(n+3=5\). Then \(n-3=-1\), so \(5p=(n+3)(n-3)=-5\) and hence \(p=-1\), which is a contradiction. Hence, \(n+3\neq 5\).
Suppose \(n+3=p\). Then \(n-3=p-6\), so \(5p=p(p-6)\). Hence \(5=p-6\), so \(p=11\), which is prime.
Suppose \(n+3=5p\). Then \(5p=(n+3)(n-3)=5p(n-3)\). Hence \(n-3=1\), and so \(n=4\). Then \(5p=(n+3)(n-3)=7\). But this is not possible since \(5\nmid 7\). Hence, \(n+3\neq 5p\).
Summarising all of the above cases, we have that if \(p\) is a prime such that \(5p+9=n^2\), for some \(n\in\mathbb{Z}_+\), then \(p=11.\)
On the other hand, let \(p=11\). Then \(5p+9=55+9=64=8^2\). Hence, the only squares \(n \in \mathbb{Z}_+\) such that there exists a prime \(p\) with \(5p+9=n^2\) is \(n=8\) (and \(p=11\)).Two things to note:
One can use Theorem 5.14 to show that for \(x\in\mathbb{Q}_+\), there are \(a,b\in\mathbb{Z}_+\) so that \(\gcd(a,b)=1\) and \(x=\frac{a}{b}.\) Furthermore, one can show that \(a,b\) are unique. We leave this as an exercise.
Every \(n\in \mathbb{Z}\) with \(n>1\) can be expressed uniquely as \[n=\prod_{i=1}^r p_i^{n_i}\] where \(p_i\) are distinct primes and \(n_i\in \mathbb{Z}_{\geq 0}\). We can extend this representation to include \(1\) by saying \(1\) is equal to the empty product.
With the above representation of integers, we can revisit the greatest common divisor.
Let \(a,b \in \mathbb{Z}_+\) and write \(a=\prod_{i=1}^r p_i^{a_i}\) and \(b=\prod_{i=1}^r p_i^{b_i}\) where \(a_i,b_i\in \mathbb{Z}\) and \(p_i\) are the prime divisors of \(a\) or \(b\) (and hence \(a_i,b_i\) can be \(0\)). Then \(a\mid b\) if and only if \(a_i\leq b_i\) for all \(i\).
We prove both directions separately.
\(\Rightarrow).\) For a contradiction, suppose \(a\mid b\) and there exists \(i\) such that \(a_i>b_i\). We can write \(a = p_i^{a_i} \cdot A\) where \(\gcd(p_i,A)=1\), and we can write \(b = p_i^{b_i} \cdot B\) where \(\gcd(p_i,B) = 1\). Since \(a|b\), there exists \(c\in \mathbb{Z}_+\) such that \(ac = b\), that is \(p_i^{a_i} \cdot A \cdot c = p_i^{b_i} \cdot B\). Rearranging, we have \(p_i^{a_i-b_i} \cdot A \cdot c = B\). Now since \(a_i-b_i>0\), we have \(p_i|B\), which is a contradiction since \(\gcd(B,p_i)=1\). Hence, for all \(i\), \(a_i\leq b_i\).
\(\Leftarrow).\) If \(a_i\leq b_i\) for all \(i\) then \[ b = \left(\prod_{i=1}^r p_i^{a_i}\right)\left(\prod_{i=1}^r p_i^{b_i-a_i}\right) = ac.\] Hence \(a\mid b\).□
Let \(a,b \in \mathbb{Z}\) such that neither are \(0\) and write \(|a|=\prod_{i=1}^r p_i^{a_i}\) and \(|b|=\prod_{i=1}^r p_i^{b_i}\) where \(a_i,b_i\in \mathbb{Z}\) and \(p_i\) are the prime divisors of \(|a|\) or \(|b|\) (and hence \(a_i,b_i\) can be \(0\)). Then \[\gcd(a,b) = \gcd(|a|,|b|) = \prod_{i=1}^r p_i^{\min(a_i,b_i)}.\]
The greatest common divisor is a divisor of both and therefore the prime factorization of the gcd can contain only primes that appear in both \(|a|\) and \(|b|\). Each of those primes can only appear with at most the minimum power appearing in both. The greatest common divisor will then be obtained by choosing as many primes as possible with the minimum power appearing.
□
The word co-prime is to demonstrate that there are no prime factors in common between \(a\) and \(b\) (they are prime with respect to each other).
Let \(a,b \in \mathbb{Z}\) such that neither are \(0\) and write \(|a|=\prod_{i=1}^r p_i^{a_i}\) and \(|b|=\prod_{i=1}^r p_i^{b_i}\) where \(a_i,b_i\in \mathbb{Z}\) and \(p_i\) are the prime divisors of \(|a|\) or \(|b|\) (and hence \(a_i,b_i\) can be \(0\)). Then \[\text{lcm}(a,b) = \text{lcm}(|a|,|b|) = \prod_{i=1}^r p_i^{\max(a_i,b_i)}.\]
The lowest common multiple is a multiple of both and therefore the prime factorization of the lcm must contain all the primes that appear in both \(|a|\) and \(|b|\). Those primes must appear with at least the maximum power appearing in each. The lest common multiple will then be obtained by choosing as few primes as possible with the maximum power appearing.
□
Let \(a,b\in\mathbb{Z}\) such that neither are \(0\). Then \(\text{lcm}(a,b)\gcd(a,b)=|ab|.\)
We first note that for any two numbers \(a_i,b_i\) we have \(\min(a_i,b_i)+\max(a_i,b_i) = a_i+b_i\). Write \(|a|=\prod_{i=1}^r p_i^{a_i}\) and \(|b|=\prod_{i=1}^r p_i^{b_i}\). Then: \[\begin{align*} \text{lcm}(a,b)\gcd(a,b) &= \left(\prod_{i=1}^r p_i^{\max(a_i,b_i)}\right)\left(\prod_{i=1}^r p_i^{\min(a_i,b_i)}\right)\\ &= \prod_{i=1}^r p_i^{\min(a_i,b_i)+\max(a_i,b_i)} \\ &= \prod_{i=1}^r p_i^{a_i+b_i} \\ &= \left(\prod_{i=1}^r p_i^{a_i}\right)\left(\prod_{i=1}^r p_i^{b_i}\right) \\ &= |a||b| = |ab|. \end{align*}\]
□
Let \(a,b\in\mathbb{Z}\) such that neither are \(0\). If \(gcd(a,b)=1\), then \(\text{lcm}(a,b)=|ab|.\)
If there’s time, we’ll talk more about polynomial ring or famous open problems in Number Theory or the fundamental theorem of algebra.