Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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 n2, there exist primes p1p2ps such that n=p1p2ps. Furthermore, this factorization is unique, in the sense that if n=q1q2qt for some primes q1q2qt, then s=t and pi=qi for each i, 1is.

Proof

We first prove the existence of the factorization. Let S be the set of integers n2 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 2x,y<d. The minimality of d implies that x,yS. 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 n2 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=p1p2ps=q1q2qt. Without loss of generality, we may assume st. Suppose there exists a smallest i, where 1is, such that piqi. Then p1=q1,p2=q2,pi1=qi1,butpiqi. It follows that pipi+1ps=qiqi+1qt, in which both sides have at least two factors (why?). Without loss of generality, we may assume pi<qi. Since piqiqi+1qt, and pi is prime, Euclid’s lemma implies that piqj for some j, where i<jt. Since qj is prime, we must have pi=qjqi, which contradicts the assumption that pi<qi. Therefore, there does not exist any i for which piqi. 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 k2. 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+p1p2pn. It is obvious that xpi 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=xp1p2pn=pkqp1p2pn=pk(qp1p2pk1pk+1pn), 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 n2 can be uniquely expressed in the form n=pe11pe22pett 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=2341 and 426=2379, it is clear that gcd(246,426)=23=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=2235241,and34128=243379, we could write them as 12300=223152411790,and34128=243350410791. It follows that gcd(12300,34128)=223150410790=12. The generalization is immediate.

Theorem 5.6.4

If a=pe11pe22pett and b=pf11pf22pftt for some distinct primes pi, where ei,fi0 for each i, then gcd(a,b)=pmin(e1,f1)1pmin(e2,f2)2pmin(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(2357112,22325272).

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=pe11pe22pett and b=pf11pf22pftt for some distinct primes pi, where ei,fi0 for each i, then lcm(a,b)=pmax(e1,f1)1pmax(e2,f2)2pmax(et,ft)t.

hands-on exercise 5.6.3

Compute lcm(2357112,22325272).

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=223152411790, and 34128=243350410791, it follows that lcm(12300,34128)=243352411791=34981200. We have seen that gcd(12300,34128)=12, and we do have 1234981200=1230034128.

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=7833+51222=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(4m6n,6m+4n)?

Example 5.6.5

What does 2Z3Z equal to?

Solution

Assume x2Z3Z, then x2Z and x3Z. This means x is a multiple of both 2 and 3. Consequently, x is a multiple of lcm(2,3)=6, which means x6Z. Therefore, 2Z3Z6Z.

Next, assume x6Z, then x is a multiple of 6. Consequently, x is a multiple of 2, as well as a multiple of 3. This means x2Z, and x3Z. As a result, x2Z3Z. Therefore, 6Z2Z3Z. Together with 2Z3Z6Z, we conclude that 2Z3Z=6Z.

hands-on exercise 5.6.7

What does 4Z6Z 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.

  1. 4725
  2. 9702
  3. 180625
  4. 1662405

Exercise 5.6.2

Find the least common multiple of each of the following pairs of integers.

  1. 27, 81
  2. 24, 84
  3. 120, 615
  4. 412, 936
  5. 1380, 3020
  6. 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(1550,2521), and lcm(1550,2521).

Exercise 5.6.5

What does 10Z15Z equal to? Prove your claim.

Exercise 5.6.6

Let m and n be positive integers. What does mZnZ 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

  1. 4k+1
  2. 4k+3
  3. 6k+1
  4. 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 n24.

Hint

Consider the factorization of n24.

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 p5 is a prime, then p2+2 is composite.
  • If pq5 are primes, then 24(p2q2).

This page titled 5.6: Fundamental Theorem of Arithmetic is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Harris Kwong (OpenSUNY) .

Support Center

How can we help?