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

8.5: Applications in Number Theory

( \newcommand{\kernel}{\mathrm{null}\,}\)

Induction (or the fact that N is well-ordered) can be used to prove many important properties of natural numbers. Here are just three examples.

Definition 8.5.1.

An element p of N+ is prime iff p>1 and p is not divisible by any element of N+ other than 1 and p.

Proposition 8.5.2.

If nN and n>1, then n is divisible by a prime number.

Proof

Suppose there is some natural number n>1, such that n is not divisible by a prime number. (This will lead to a contradiction.) Since N is well-ordered, we may assume that n is the smallest such number, so:  If 1<k<n (and kN ), then k is divisible by a prime number. 

Since nn, but (by assumption) n is not divisible by any prime number, we know that n is not prime. By definition, this means there exists kN, such that kn and 1<k<n. From the minimality of n, we know that k is divisible by some prime number p. Then pk and kn, so pn. This contradicts the fact that n is not divisible by a prime number.

Theorem 8.5.3 (Fundamental Theorem of Arithmetic).

Every natural number (other than 0 and 1) is a product of prime numbers (or is itself a prime).

Proof

BY CONTRADITION: Suppose there is some natural number n>1, such that n is not a product of prime numbers (and is not a prime). Since N is well-ordered, we may assume that n is the smallest such number, so:  If 1<k<n (and kN), then k is a product of prime numbers. 

Since n is not prime, it is divisible by some natural number k, with 1<k<n. This means we may write n=km, for some mN+. Since m=n/k and 1<k<n, we see that 1<m<n. Therefore, the minimality of n implies that k and m are products of prime numbers: say k=p1p2pr and m=q1q2qs. Then n=km=(p1p2pr)(q1q2qs)

is a product of prime numbers. This is a contradiction.

Remark 8.5.4.

In fact, every natural number can be written in only one way as a product of prime numbers (up to rearranging the order of the factors), but we will not prove this fact.

Definition 8.5.5.

Let a,bN+. We say a and b are relatively prime iff they have no divisors in common, other than 1. (I.e., if kN+, and k is a divisor of both a and b, then k=1. In other words, the “greatest common divisor” of a and b is 1.)

Theorem 8.5.6.

Let a,bN+. If a and b are relatively prime, then there exist m,nZ, such that ma+nb=1.

Proof

Let S={ma+nbm,nZk=}N+.

It is easy to see that aS (by letting m=1 and n=0), so S. Therefore, since N is well-ordered, we may let d be the smallest element of S. Then dS, so we have d=m0a+n0b for some m0,n0Z.

By the Division Algorithm (5.1.20), we may write a=qd+r with 0r<d.

So r=aqd=aq(m0a+n0b)=(1qm0)a+qn0b=ma+nb,

where m=1qmZ and n=qnZ. On the other hand, since r<d, and d is the smallest element of S, we know rS. From the definition of S, we conclude that r=0. So da.

By repeating the same argument with a and b interchanged (and m0 and n0 also interchanged) we see that db.

Therefore, d is a divisor of both a and b. Since a and b are relatively prime, we conclude that d=1. Since dS, this means 1S, which establishes the desired conclusion.

Exercise 8.5.7.

Prove the converse of Theorem 8.5.6.

Theorem 8.5.6 is of fundamental importance in Number Theory, the mathematical study of properties of N and Z. Here are a few of its many consequences:

Exercise 8.5.8.

Assume a,bN+.

  1. Show a and b are relatively prime iff there exists xZ, such that xa1(modb).
  2. Show a and b are relatively prime iff for all yZ, there exists xZ, such that xay(modb).
  3. (Chinese Remainder Theorem) Suppose a and b are relatively prime. For all y1,y2Z, show there exists xZ, such that xy1(moda) and xy2(modb).

Proposition 8.5.2 also has important consequences. For example:

Corollary 8.5.9.

There are infinitely many prime numbers.

Proof

BY CONTRADICTION: Suppose there are only finitely many prime numbers. Then we can make a list of all of them:  The set of all prime numbers is {p1,p2,,pn}.

Let N=p1p2pn.

From Proposition 8.5.2, we know there is some prime p, such that p(N+1).

Since p1,p2,,pn is a list of all the prime numbers, we know p=pi, for some i. Therefore p=pi is one of the factors in the product that defines N, so pN. Therefore, p divides both N and N+1, so (from 5.1.9(1)) we have p((N+1)N)=1.

This implies p=±1 (see page 97), which contradicts the fact that p, being a prime number, must be >1.


This page titled 8.5: Applications in Number Theory is shared under a CC BY-NC-SA 2.0 license and was authored, remixed, and/or curated by Dave Witte Morris & Joy Morris.

Support Center

How can we help?