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.