Section 2.4 Number Theory
149
Although Euclid’s theorem says that there is always another prime number
ahead as we march through the positive integers, the distribution of primes among
the integers is erratic. Contrary to what one might think, the primes do not get
farther and farther apart. Even among the small primes, 23 and 29 are farther
apart than 29 and 31.
eXAMPLe 33
In Example 11, we did a proof by contradiction that !2 is not a rational number.
The same argument works for !3 and !5 (2, 3, and 5 are all prime numbers).
We can generalize this result from a single prime to any integer x that is the
product of an odd number of primes. Assume that by the fundamental theorem of
arithmetic, x = p 1 p 2 c p 2k+1 (In this example, we are not using any exponents, so
some of these primes could be identical; that is, 75 = 3 * 5 * 5). Again doing a proof
by contradiction, assume that !p 1 p 2 c p 2k+1 = a/b where a and b are integers,
b ∙ 0, and a and b are relatively prime. Then
p 1 p 2 c p 2k+1 =
a
2
b
2
a
2
= p 1 p 2 c p 2k+1 b
2
By the fundamental theorem, a can be written as a product of one or more primes,
but a
2
will add another factor of each of a’s primes, resulting in a product of an even
number of primes. Similarly, b
2
is the product of an even number of primes. Therefore
p 1 p 2 c p 2k+1 b
2
is the product of an odd number and an even number (which gives
an odd number) of prime factors. Contradiction: a
2
has an even number of prime
factors while p 1 p 2 c p 2k+1 b
2
has an odd number of prime factors, yet by the fundamental theorem, factorization is unique.
The search for prime numbers and information about primes has generated
much interest. As of June 2013, the largest known prime number is 2
57,885,161
− 1,
which is a number with 17,425,170 decimal digits. If we consider that for a reasonable type size it takes about 1 inch to print 10 digits, then it would take more than
27 miles just to print out a number of this size!
One of the oldest conjectures about prime numbers—still unsolved—is Goldbach’s conjecture, formulated in 1742: Every even integer greater than 2 is the
sum of two prime numbers.
Euler Phi Function
DeFinition EulEr PhI FuNCTIoN
For n an integer, n ≥ 2, the euler phi function of n, φ(n), is the number of positive integers less than or equal to n and relatively prime to n. (φ(n) is pronounced
“fee” of n.)
149
Although Euclid’s theorem says that there is always another prime number
ahead as we march through the positive integers, the distribution of primes among
the integers is erratic. Contrary to what one might think, the primes do not get
farther and farther apart. Even among the small primes, 23 and 29 are farther
apart than 29 and 31.
eXAMPLe 33
In Example 11, we did a proof by contradiction that !2 is not a rational number.
The same argument works for !3 and !5 (2, 3, and 5 are all prime numbers).
We can generalize this result from a single prime to any integer x that is the
product of an odd number of primes. Assume that by the fundamental theorem of
arithmetic, x = p 1 p 2 c p 2k+1 (In this example, we are not using any exponents, so
some of these primes could be identical; that is, 75 = 3 * 5 * 5). Again doing a proof
by contradiction, assume that !p 1 p 2 c p 2k+1 = a/b where a and b are integers,
b ∙ 0, and a and b are relatively prime. Then
p 1 p 2 c p 2k+1 =
a
2
b
2
a
2
= p 1 p 2 c p 2k+1 b
2
By the fundamental theorem, a can be written as a product of one or more primes,
but a
2
will add another factor of each of a’s primes, resulting in a product of an even
number of primes. Similarly, b
2
is the product of an even number of primes. Therefore
p 1 p 2 c p 2k+1 b
2
is the product of an odd number and an even number (which gives
an odd number) of prime factors. Contradiction: a
2
has an even number of prime
factors while p 1 p 2 c p 2k+1 b
2
has an odd number of prime factors, yet by the fundamental theorem, factorization is unique.
The search for prime numbers and information about primes has generated
much interest. As of June 2013, the largest known prime number is 2
57,885,161
− 1,
which is a number with 17,425,170 decimal digits. If we consider that for a reasonable type size it takes about 1 inch to print 10 digits, then it would take more than
27 miles just to print out a number of this size!
One of the oldest conjectures about prime numbers—still unsolved—is Goldbach’s conjecture, formulated in 1742: Every even integer greater than 2 is the
sum of two prime numbers.
Euler Phi Function
DeFinition EulEr PhI FuNCTIoN
For n an integer, n ≥ 2, the euler phi function of n, φ(n), is the number of positive integers less than or equal to n and relatively prime to n. (φ(n) is pronounced
“fee” of n.)