150
Proofs, Induction, and Number Theory
Notice that n will never be relatively prime to n, so this definition could have
been stated as, “the number of positive integers less than n and relatively prime to
n,” but it turns out to be convenient to include equality.
For small n, it is easy to compute φ(n) by a brute-force approach of just trying values < n to find how many are relatively prime to n. But there is actually a
formula to compute φ(n), which we’ll derive now.
eXAMPLe 34
The first few values of φ(n), together with the numbers that give those values, are
φ(2) = 1 (the number 1)
φ(3) = 2 (the numbers 1, 2)
φ(4) = 2 (the numbers 1, 3)
φ(5) = 4 (the numbers 1, 2, 3, 4)
φ(6) = 2 (the numbers 1, 5)
φ(7) = 6 (the numbers 1, 2, 3, 4, 5, 6)
PrACTiCe 16 If p is a prime number, prove that φ (p) = p − 1.
eXAMPLe 35
Using the fundamental theorem of arithmetic, write the positive integer n in its
factored form as a product of primes, where if the same prime p occurs m times, it
is written as p
m
. Suppose, for example, that
n = p
m 1
1 p
m 2
2 p
m 3
3
To compute φ(n), we’ll count all the positive integers ≤ n, of which there are n,
and throw out those that are not relatively prime to n, Now let A i , 1 ≤ i ≤ 3, be
defined as the collection of all positive integral multiples of p i that are ≤ n; these
numbers share a common factor of p i with n and so are not relatively prime to n.
The integral multiples of p i that are ≤ n are p i , 2p i , 3p i , … , n. How many numbers
are in this list? Exactly the number of times you can divide n by p i , or n/p i . So,
denoting the size of A i by 0 A i 0 , we know that 0 A i 0 = n/p i . If we combine A 1 , A 2 , and
A 3 , that will be all integers ≤ n that are not relatively prime to n. How many such
integers are there? We can’t just add 0 A 1 0 + 0 A 2 0 + 0 A 3 0 = n/p 1 + n/p 2 + n/p 3 because
there could be some numbers that appear in more than one of the three collections, and would therefore be counted twice. Numbers that appear in both A i and
A j , i ∙ j, are integral multiples of both p i and p j , so there will be n/(p i p j ) of them.
We’ll subtract those for all i, j combinations. But by doing this, we have subtracted
any numbers in all three collections three times, which means they now are not
counted at all, so we have to add back the n/(p 1 p 2 p 3 ) numbers that are in all three
collections.
2
Therefore
2 This lengthy discussion is an instance of the principle of inclusion and exclusion, discussed in Chapter 4.
■
Proofs, Induction, and Number Theory
Notice that n will never be relatively prime to n, so this definition could have
been stated as, “the number of positive integers less than n and relatively prime to
n,” but it turns out to be convenient to include equality.
For small n, it is easy to compute φ(n) by a brute-force approach of just trying values < n to find how many are relatively prime to n. But there is actually a
formula to compute φ(n), which we’ll derive now.
eXAMPLe 34
The first few values of φ(n), together with the numbers that give those values, are
φ(2) = 1 (the number 1)
φ(3) = 2 (the numbers 1, 2)
φ(4) = 2 (the numbers 1, 3)
φ(5) = 4 (the numbers 1, 2, 3, 4)
φ(6) = 2 (the numbers 1, 5)
φ(7) = 6 (the numbers 1, 2, 3, 4, 5, 6)
PrACTiCe 16 If p is a prime number, prove that φ (p) = p − 1.
eXAMPLe 35
Using the fundamental theorem of arithmetic, write the positive integer n in its
factored form as a product of primes, where if the same prime p occurs m times, it
is written as p
m
. Suppose, for example, that
n = p
m 1
1 p
m 2
2 p
m 3
3
To compute φ(n), we’ll count all the positive integers ≤ n, of which there are n,
and throw out those that are not relatively prime to n, Now let A i , 1 ≤ i ≤ 3, be
defined as the collection of all positive integral multiples of p i that are ≤ n; these
numbers share a common factor of p i with n and so are not relatively prime to n.
The integral multiples of p i that are ≤ n are p i , 2p i , 3p i , … , n. How many numbers
are in this list? Exactly the number of times you can divide n by p i , or n/p i . So,
denoting the size of A i by 0 A i 0 , we know that 0 A i 0 = n/p i . If we combine A 1 , A 2 , and
A 3 , that will be all integers ≤ n that are not relatively prime to n. How many such
integers are there? We can’t just add 0 A 1 0 + 0 A 2 0 + 0 A 3 0 = n/p 1 + n/p 2 + n/p 3 because
there could be some numbers that appear in more than one of the three collections, and would therefore be counted twice. Numbers that appear in both A i and
A j , i ∙ j, are integral multiples of both p i and p j , so there will be n/(p i p j ) of them.
We’ll subtract those for all i, j combinations. But by doing this, we have subtracted
any numbers in all three collections three times, which means they now are not
counted at all, so we have to add back the n/(p 1 p 2 p 3 ) numbers that are in all three
collections.
2
Therefore
2 This lengthy discussion is an instance of the principle of inclusion and exclusion, discussed in Chapter 4.
■