5.6: Fundamental Theorem of Arithmetic
( \newcommand{\kernel}{\mathrm{null}\,}\)
Primes are positive integers that do not have any proper divisor except 1. Primes can be regarded as the building blocks of all integers with respect to multiplication.
Theorem 5.6.1: Fundamental Theorem of Arithmetic
Given any integer n≥2, there exist primes p1≤p2≤⋯≤ps such that n=p1p2…ps. Furthermore, this factorization is unique, in the sense that if n=q1q2…qt for some primes q1≤q2≤⋯≤qt, then s=t and pi=qi for each i, 1≤i≤s.
- Proof
-
We first prove the existence of the factorization. Let S be the set of integers n≥2 that are not expressible as the product of primes. Since a product may contain as little as just one prime, S does not contain any prime. Suppose S≠∅, then the principle of well-ordering implies that S has a smallest element d. Since S does not contain any prime, d is composite, so d=xy for some integers x and y, where 2≤x,y<d. The minimality of d implies that x,y∉S. So both x and y can be expressed as products of primes, then d=xy is also a product of primes, which is a contradiction, because d belongs to S. Therefore, S=∅, which means every integer n≥2 can be expressed as a product of primes.
Next, we prove that the factorization is unique. Assume there are two ways to factor n, say n=p1p2…ps=q1q2…qt. Without loss of generality, we may assume s≤t. Suppose there exists a smallest i, where 1≤i≤s, such that pi≠qi. Then p1=q1,p2=q2,⋯pi−1=qi−1,butpi≠qi. It follows that pipi+1⋯ps=qiqi+1⋯qt, in which both sides have at least two factors (why?). Without loss of generality, we may assume pi<qi. Since pi∣qiqi+1⋯qt, and pi is prime, Euclid’s lemma implies that pi∣qj for some j, where i<j≤t. Since qj is prime, we must have pi=qj≥qi, which contradicts the assumption that pi<qi. Therefore, there does not exist any i for which pi≠qi. This means pi=qi for each i, and as a consequence, we must have have s=t.
Interestingly, we can use the strong form of induction to prove the existence part of the Fundamental Theorem of Arithmetic.
- Proof
-
(Existence) Induct on n. The claim obviously holds for n=2. Assume it holds for n=2,3,…,k for some integer k≥2. We want to show that it also holds for k+1. If k+1 is a prime, we are done. Otherwise, k+1=αβ for some integers α and β, both less than k+1. Since 2≤α,β≤k, both α and β can be expressed as a product of primes. Putting these primes together, and relabeling and rearranging them if necessary, we see that k+1 is also expressible as a product of primes in the form we desire. This completes the induction.
The next result is one of the oldest theorems in mathematics, numerous proofs can be found in the literature.
Theorem 5.6.2
There are infinitely many primes.
- Proof
-
Suppose there are only a finite number of primes p1,p2,…,pn. Consider the integer x=1+p1p2⋯pn. It is obvious that x≠pi for any i. Since p1,p2,…,pn are assumed to be the only primes, the integer x must be composite, hence can be factored into a product of primes. Let pk be one of these prime factors, so that x=pkq for some integer q. Then 1=x−p1p2⋯pn=pkq−p1p2⋯pn=pk(q−p1p2⋯pk−1pk+1⋯pn), which is impossible. This contradiction proves that there are infinitely many primes.
Some of the primes listed in the Fundamental Theorem of Arithmetic can be identical. If we group the identical primes together, we obtain the canonical factorization or prime-power factorization of an integer.
Theorem 5.6.3
All integers n≥2 can be uniquely expressed in the form n=pe11pe22⋯pett for some distinct primes pi and positive integers ei.
Once we find the prime-power factorization of two integers, their greatest common divisor can be obtained easily.
Example 5.6.1
From the factorizations 246=2⋅3⋅41 and 426=2⋅3⋅79, it is clear that gcd(246,426)=2⋅3=6.
hands-on exercise 5.6.1
Find the factorizations of 153 and 732, and use them to compute gcd(153,732).
Although the set of primes that divide two different positive integers a and b may be different, we could nevertheless write both a and b as the product of powers of all the primes involved. For example, by combining the prime factors of 12300=22⋅3⋅52⋅41,and34128=24⋅33⋅79, we could write them as 12300=22⋅31⋅52⋅411⋅790,and34128=24⋅33⋅50⋅410⋅791. It follows that gcd(12300,34128)=22⋅31⋅50⋅410⋅790=12. The generalization is immediate.
Theorem 5.6.4
If a=pe11pe22⋯pett and b=pf11pf22⋯pftt for some distinct primes pi, where ei,fi≥0 for each i, then gcd(a,b)=pmin(e1,f1)1pmin(e2,f2)2⋯pmin(et,ft)t.
In this theorem, we allow the exponents to be zero. In the usual prime-power factorization, the exponents have to be positive.
hands-on exercise 5.6.2
Compute gcd(23⋅5⋅7⋅112,22⋅32⋅52⋅72).
Definition: least common multiple
The least common multiple of the integers a and b, denoted lcm(a,b), is the smallest positive common multiple of both a and b.
Theorem 5.6.5
If a=pe11pe22⋯pett and b=pf11pf22⋯pftt for some distinct primes pi, where ei,fi≥0 for each i, then lcm(a,b)=pmax(e1,f1)1pmax(e2,f2)2⋯pmax(et,ft)t.
hands-on exercise 5.6.3
Compute lcm(23⋅5⋅7⋅112,22⋅32⋅52⋅72).
Corollary 5.6.6
For any positive integers a and b, we have ab=gcd(a,b)⋅lcm(a,b).
- Proof
-
For each i, one of the two numbers ei and fi is the minimum, and the other is the maximum. Hence, ei+fi=min(ei,fi)+max(ei,fi), from which we obtain peiipfii=pei+fii=pmin(ei,fi)+max(fi,fi)i=pmin(ei,fi)ipmax(ei,fi)i. Therefore, ab equals the product of gcd(a,b) and lcm(a,b).
Example 5.6.1
Since 12300=22⋅31⋅52⋅411⋅790, and 34128=24⋅33⋅50⋅410⋅791, it follows that lcm(12300,34128)=24⋅33⋅52⋅411⋅791=34981200. We have seen that gcd(12300,34128)=12, and we do have 12⋅34981200=12300⋅34128.
hands-on exercise 5.6.4
Knowing that gcd(246,426)=6, how would you compute the value of lcm(246,426)?
Example 5.6.3
When we add two fractions, we first take the common denominator, as in 78+512=78⋅33+512⋅22=21+1024=3124. Clear enough, the least common denominator is precisely the least common multiple of the two denominators.
Example 5.6.4
The control panel of a machine has two signal lights, one red and one blue. The red light blinks once every 10 seconds, and the blue light blinks once every 14 seconds. When the machine is turned on, both lights blink simultaneously. After how many seconds will they blink at the same time again?
- Solution
-
This problem illustrates a typical application of least common multiple. The red light blinks at 10, 20, 30, … seconds, while the blue light blinks at 14, 28, 42, … seconds. In general, the red light blinks at t seconds if t is a multiple of 10, and the blue light blinks when t is a multiple of 14. Therefore, both lights blink together when t is a multiple of both 10 and 14. The next time it happens will be lcm(10,14)=70 seconds later.
hands-on exercise 5.6.5
Two comets travel on fixed orbits around the earth. One of them returns to Earth every 35 years, the other every 42 years. If they both appear in 2012, when is the next time they will return to Earth in the same year?
hands-on exercise 5.6.6
Given relatively prime positive integers m and n, what are the possible values of lcm(4m−6n,6m+4n)?
Example 5.6.5
What does 2Z∩3Z equal to?
- Solution
-
Assume x∈2Z∩3Z, then x∈2Z and x∈3Z. This means x is a multiple of both 2 and 3. Consequently, x is a multiple of lcm(2,3)=6, which means x∈6Z. Therefore, 2Z∩3Z⊆6Z.
Next, assume x∈6Z, then x is a multiple of 6. Consequently, x is a multiple of 2, as well as a multiple of 3. This means x∈2Z, and x∈3Z. As a result, x∈2Z∩3Z. Therefore, 6Z⊆2Z∩3Z. Together with 2Z∩3Z⊆6Z, we conclude that 2Z∩3Z=6Z.
hands-on exercise 5.6.7
What does 4Z∩6Z equal to?
Summary and Review
- There are infinitely many primes.
- Any positive integer n>1 can be uniquely factored into a product of prime powers.
- Primes can be considered as the building blocks (through multiplication) of all positive integers exceeding one.
- Given two positive integers a and b, their least common multiple is denoted as lcm(a,b).
- For any positive integers a and b, we have ab=gcd(a,b)⋅lcm(a,b).
Exercise 5.6.1
Find the prime-power factorization of these integers.
- 4725
- 9702
- 180625
- 1662405
Exercise 5.6.2
Find the least common multiple of each of the following pairs of integers.
- 27, 81
- 24, 84
- 120, 615
- 412, 936
- 1380, 3020
- 1122, 3672
Exercise 5.6.3
Richard follows a very rigid routine. He orders a pizza for lunch every 10 days, and has dinner with his parents every 25 days. If he orders a pizza for lunch and has dinner with his parents today, when will he do both on the same day again?
Exercise 5.6.4
Compute gcd(15⋅50,25⋅21), and lcm(15⋅50,25⋅21).
Exercise 5.6.5
What does 10Z∩15Z equal to? Prove your claim.
Exercise 5.6.6
Let m and n be positive integers. What does mZ∩nZ equal to? Prove your claim.
Exercise 5.6.7
Let p be an odd prime. Show that
- p is of the form 4k+1 or of the form 4k+3 for some nonnegative integer k.
- p is of the form 6k+1 or of the form 6k+5 for some nonnegative integer k.
Exercise 5.6.8
Give three examples of an odd prime p of each of the following forms
- 4k+1
- 4k+3
- 6k+1
- 6k+5
Exercise 5.6.9
Prove that any prime of the form 3n+1 is also of the form 6k+1.
Exercise 5.6.10
Prove that if a positive integer n is of the form 3k+2, then it has a prime factor of the same form.
- Hint
-
Consider its contrapositive.
Exercise 5.6.11
Prove that 5 is the only prime of the form n2−4.
- Hint
-
Consider the factorization of n2−4.
Exercise 5.6.12
Use the result “Any odd prime p is of the form 6k+1 or of the form 6k+5 for some nonnegative integer k” to prove the following results.
- If p≥5 is a prime, then p2+2 is composite.
- If p≥q≥5 are primes, then 24∣(p2−q2).