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.
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.
If n∈N 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 k∈N ), then k is divisible by a prime number.
Since n∣n, but (by assumption) n is not divisible by any prime number, we know that n is not prime. By definition, this means there exists k∈N, such that k∣n and 1<k<n. From the minimality of n, we know that k is divisible by some prime number p. Then p∣k and k∣n, so p∣n. This contradicts the fact that n is not divisible by a prime number.
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 k∈N), 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 m∈N+. 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=p1p2⋯pr and m=q1q2⋯qs. Then n=km=(p1p2⋯pr)(q1q2⋯qs)
is a product of prime numbers. This is a contradiction.
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.
Let a,b∈N+. We say a and b are relatively prime iff they have no divisors in common, other than 1. (I.e., if k∈N+, 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.)
Let a,b∈N+. If a and b are relatively prime, then there exist m,n∈Z, such that ma+nb=1.
- Proof
-
Let S={ma+nb∣m,n∈Zk=}∩N+.
It is easy to see that a∈S (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 d∈S, so we have d=m0a+n0b for some m0,n0∈Z.
By the Division Algorithm (5.1.20), we may write a=qd+r with 0≤r<d.
So r=a−qd=a−q(m0a+n0b)=(1−qm0)a+qn0b=ma+nb,
where m=1−qm∈Z and n=qn∈Z. On the other hand, since r<d, and d is the smallest element of S, we know r∉S. From the definition of S, we conclude that r=0. So d∣a.
By repeating the same argument with a and b interchanged (and m0 and n0 also interchanged) we see that d∣b.
Therefore, d is a divisor of both a and b. Since a and b are relatively prime, we conclude that d=1. Since d∈S, this means 1∈S, which establishes the desired conclusion.
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:
Assume a,b∈N+.
- Show a and b are relatively prime iff there exists x∈Z, such that xa≡1(modb).
- Show a and b are relatively prime iff for all y∈Z, there exists x∈Z, such that xa≡y(modb).
- (Chinese Remainder Theorem) Suppose a and b are relatively prime. For all y1,y2∈Z, show there exists x∈Z, such that x≡y1(moda) and x≡y2(modb).
Proposition 8.5.2 also has important consequences. For example:
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=p1p2⋯pn.
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 p∣N. 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.