Chapter 7

As for anything else, so for a mathematical theory: beauty can be perceived but not explained.

-Arthur Cayley

The point, as I see things, is for it to be fun.

-Jerry Garcia

Definition Euler’s phi function, ϕ(n), enumerates the number of integers less than n and relatively prime to it. For example: ϕ(2) = 1, ϕ(6) = 2, ϕ(15) = 8. Note that by convention, ϕ(1) = 1.

Problem 82 Prove that ϕ(n) is multiplicative.

To begin the proof, we will need a lemma.

Lemma 6.1 If d is relatively prime to a, then d + ka is also relatively prime to a.

Proof by contradiction: Suppose that d is relatively prime to a, but there exists e such that e|(d + ka) and e|a. Then em = d + ka for some integer m, which implies em − ka = d, and since e|a it follows that e|d. But, d is relatively prime to a; contradiction.

We can now proceed with a proof by example. We want to show that if gcd(a, b)=1, then ϕ(ab) = ϕ(a)ϕ(b). Let a = 4, and b = 9. The following tables display those numbers less than 36 and, in the first table congruent modulo 4 to 1 and 3, in the second table congruent modulo 9 to 1, 2, 4, 5, 7, and 8.

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35  1 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35

Note that by the lemma, the numbers relatively prime to 4 must be congruent to 1 or 3 modulo 4. Similarly, the numbers relatively prime to 9 must be congruent to 1, 2, 4, 5, 7, or 8 modulo 9. Since we are looking for those numbers relatively prime to 36, we are interested in those numbers that appear on both these tables. In other words, those numbers that are a solution to the following pairs of congruences:

1 (mod 4) and 1 (mod 9) 3 (mod 4) and 1 (mod 9)
1 (mod 4) and 2 (mod 9) 3 (mod 4) and 2 (mod 9)
1 (mod 4) and 4 (mod 9) 3 (mod 4) and 4 (mod 9)
1 (mod 4) and 5 (mod 9) 3 (mod 4) and 5 (mod 9)
1 (mod 4) and 7 (mod 9) 3 (mod 4) and 7 (mod 9)
1 (mod 4) and 8 (mod 9) 3 (mod 4) and 8 (mod 9)

Because 4 and 9 are relatively prime, the Chinese Remainder Theorem tells us that there exist solutions to each of these. It also tells us that these solutions are unique up to 4 · 9 = 36. Notice that we are looking at the number of ways to pair everything relatively prime to, and less than, 4 with everything relatively prime to, and less than, 9. This tells us that there are ϕ(4)ϕ(9) sets of equations, and thus ϕ(4)ϕ(9) numbers relatively prime to, and less than, 36. Thus, ϕ(4)ϕ(9) = ϕ(36).

In general, for a number r_{k} to be relatively prime to p_{1}p_{2} ⋯ p_{x} where the p_{i} are relatively prime, we need r_{k} to be congruent to some q_{1}(mod p_{1}) such that q_{1} is relatively prime to p_{1} and q_{1} < p_{1}, congruent to some q_{2}(mod p_{2}) such that q_{2} is relatively prime to p_{2} and q_{2} < p_{2},…, congruent to some q_{x}(mod p_{x}) such that q_{x} is relatively prime to p_{x} and q_{x} < p_{x}. We will have ϕ(p_{1})ϕ(p_{2}) ⋯ ϕ(p_{x}) of these systems of equations, which by the Chinese Remainder Theorem all have unique solutions (mod p_{1} ⋯ p_{x}). Thus we have ϕ(p_{1})ϕ(p_{2}) ⋯ ϕ(p_{x}) numbers relatively prime to, and less than, p_{1}p_{2} ⋯ p_{x}. Therefore, ϕ(p_{1}p_{2} ⋯ p_{x})=ϕ(p_{1})ϕ(p_{2}) ⋯ ϕ(p_{x}).

Problem 84 Find a formula for ϕ(p^{n}) for prime p.

Proof: We can think of ϕ(p^{n}) as the difference between the cardinality of the set containing all numbers between 1 and p^{n}, {x|1 ≤ x ≤ p^{n}}, and the cardinality of the set containing all numbers less than or equal to p^{n} which are not relatively prime to it, {y| p|y, y ≤ p^{n}}. So,

ϕ(p^{n}) = |{1, 2, ..., p^{n}}| − |{1p, 2p, …, (p^{n−1} − 1)p, p^{n−1}p}|
= p^{n} − p^{n−1}

Problem 83 Find all n such that ϕ(n) is odd.

1. First note that by convention, ϕ(1) = 1, so one possible value of n is 1.

2. Consider ϕ(p) such that p is prime. ϕ(p) = p − 1, so for all odd primes, ϕ(p) is even. However, for p = 2, ϕ(p) = 2 − 1 = 1, so another possible value of n is 2.

3. Now consider ϕ(p^{k}) such that p is prime and k is some integer such that k > 1. By problem 84, ϕ(p^{k}) = p^{k} − p^{k−1}. For any value of p, note that the parity of p^{k} and p^{k−1} must be the same, thus their difference must be even. Therefore, no number of this form can be a value of n.

4. Finally, consider the composite numbers with more than one prime factor. We can write these numbers as p^{k}(x) such that p is an odd prime, k is some positive integer, and gcd(p, x)=1. Because the function is multiplicative, ϕ(p^{k}x) = ϕ(p^{k})ϕ(x). But, we have already shown that ϕ(p^{k}) for any k ≥ 1 is even. Therefore, the product ϕ(p^{k})ϕ(x) must also be even.

Thus we have shown that the only possible values of n are 1 and 2.

Problem 85 Find a quick way to evaluate ϕ(n) given the prime factorization of n.

Let n = p_{1}^{a_{1}}p_{2}^{a_{2}} ⋯ p_{k}^{a_{k}}. Because ϕ(n) is multiplicative,

ϕ(n) = ϕ(p_{1}^{a_{1}})ϕ(p_{2}^{a_{2}}) ⋯ ϕ(p_{k}^{a_{k}})

= (p_{1}^{a_{1}} − p_{1}^{a_{1}−1})(p_{2}^{a_{2}} − p_{2}^{a_{2}−1}) ⋯ (p_{k}^{a_{k}} − p_{k}^{a_{k}−1})

= (p_{1}^{a_{1}}p_{2}^{a_{2}} ⋯ p_{k}^{a_{k}})(1 − \frac{1}{p_{1}} )(1 − \frac{1}{p_{2}} ) ⋯ (1 − \frac{1}{p_{k}})

= n(1 − \frac{1}{p_{1}} )(1 − \frac{1}{p_{2}} ) ⋯ (1 − \frac{1}{p_{k}})

Problem 86a When is it true that ϕ(3n) = 3ϕ(n)?

1. Suppose gcd(3,n)=1. Because the function is multiplicative, we know that

ϕ(3n) = ϕ(3)ϕ(n)

Since ϕ(3) = 3 − 1 = 2, it follows that

ϕ(3n) = 2ϕ(n)

We are looking for ϕ(3n) = 3ϕ(n) so we are intersted in knowing when

3ϕ(n) = 2ϕ(n)

But this cannot happen, thus for gcd(3,n)=1, ϕ(3n) = 3ϕ(n) is never true.

2. Now, consider the case where gcd(3,n)=3. Let n = 3^{a}x such that gcd(3,x)=1. So,

ϕ(3n) = ϕ(3^{a+1}x) = ϕ(3^{a+1})ϕ(x)
= (3^{a+1} − 3^{a})ϕ(x)
= 3(3^{a} − 3^{a−1})ϕ(x)
= 3ϕ(3^{a})ϕ(x)
= 3ϕ(n)

Thus, in this case it is always true that ϕ(3n) = 3ϕ(n).

Note that this proof can be generalized: for all prime numbers p, ϕ(pn) = pϕ(n) is true exactly when gcd(p, n)=p.

Problem 86b When is it true that ϕ(2n) = n?

1. If gcd(2,n)=1, then:

ϕ(2n) = ϕ(2)ϕ(n)
ϕ(2n) = ϕ(n)

So, when does ϕ(2n) = ϕ(n) = n? Consider ϕ(n) = n. By convention ϕ(1) = 1, so n = 1 is a solution. Now consider every number, n, greater than 1. Each n has at least itself as a divisor, so the greatest possible value of ϕ(n) is n − 1. Therefore, the only solution to this case is n = 1.

2. Now consider the case where gcd(2,x)=2: Let n = 2^{a}x such that gcd(2,x)=1. Then,

ϕ(2n) = ϕ(2^{a+1}x) = ϕ(2^{a+1})ϕ(x)
= (2^{a+1} − 2^{a})ϕ(x)
= 2^{a}ϕ(x)

Now since n = 2^{a}x, and we want to know when n = 2^{a}ϕ(x), consider 2^{a}x = 2^{a}ϕ(x). We are interested in knowing when x = ϕ(x), but as discussed before, the only possible solution is x = 1. This implies the only solutions for ϕ(2n) = n are when n = 2^{a} such that a is a positive integer.

Therefore, ϕ(2n) = n is true exactly for all n = 2^{t} ≥ 1.

Problem 87 Given a number k show that there are only a finite number of solutions to ϕ(n) = k.

Proof: Note that k can be written as k = q_{1}^{r_{1}}q_{2}^{r_{2}} ⋯ q_{a}^{r_{a}} for some distinct primes q_{1}, q_{2}, …, q_{a} and some integers r_{1}, r_{2}, …, r_{a}. Let n = p_{1}^{t_{1}}p_{2}^{t_{2}} ⋯ p_{b}^{t_{b}} for some distinct primes p_{1}, p_{2}, …, p_{b} and some integers t_{1}, t_{2}, …, t_{b}. Since k = ϕ(n) = (p_{1}^{t_{1}−1}p_{2}^{t_{2}−1} ⋯ p_{b}^{t_{b}−1})(p_{1} − 1)(p_{2} − 1) ⋯ (p_{b} − 1) every p_{i} must divide k. And, because the prime factorization of k is q_{1}^{r_{1}}q_{2}^{r_{2}} ⋯ q_{a}^{r_{a}}, every p_{i} must be equal to some q_{i}, i.e. every p_{i} ∈ {q_{i}|1 ≤ i ≤ a}. This implies a ≥ b, and since a is fixed, there are a finite number, b, of factors, p_{i}. Now all that remains to be shown is that the exponents, t_{i}, are bounded. But, certainly p_{i}^{t_{i}−1} ≤ k, for 1 ≤ i ≤ b so the t_{i} are also bounded and there must be a finite number of solutions to ϕ(n) = k.

Problem 88 Prove that this finite number is zero if k = 14. That is, prove that there exist no solutions to ϕ(n) = 14. Even better, prove that this finite number is zero if k is twice a prime and k + 1 is composite.

We will prove this by showing that there exists no n for which the statement is true.

1. Consider ϕ(n) = 14 and suppose n is prime. Then, by problem 84, n = k + 1, which in this case means n = 15. But, 15 is composite, and thus n is both prime and composite; contradiction.

2. Now, let n = p^{j} such that p is prime, and j ≥ 2. By problem 84, this implies that ϕ(p^{j}) = (p^{j−1})(p − 1) = 14. First note that k is exactly twice a prime, so p^{j−1} and p − 1 yeild exactly one prime factor, distinct or not, each. Thus, j = 2. Now note that p − 1 must be even: since neither p^{j} = 2^{1} (k + 1 = 1 · 1 + 1), nor p^{j} = 2^{2} (k + 1 = 2 · 1 + 1), satisfies the condition that k +1 is composite, p must be an odd prime. Recall that p−1 has exactly one factor, so p − 1 = 2. The only case where p − 1 = 2 is when p = 3. But, neither p^{j} = 3^{1} (k + 1 = 1 · 2 + 1), nor p^{j} = 3^{2} (k + 1 = 3 · 2 + 1), yields a composite k + 1, so we can eliminate this case. Thus, it is not possible to have k = ϕ(p^{j}).

3. Finally, let n = p^{j}x such that gcd(p^{j}, x)=1 and x > 1. If x = 2, then ϕ(n) = 1 · ϕ(p^{j}), but we have already shown that k ≠ ϕ(p^{j}). If x > 2, then by problem 83 we know that both ϕ(p^{j}) and ϕ(x) are even and contain factors of 2. This implies k = 2^{2}(w). We have already shown that k cannot be equal to 2^{2}, so w > 1. But, k is exactly twice a prime and therefore cannot contain a factor of 4 if k ≠ 4; i.e.: we cannot write 14 = 2^{2}(w) because 7 ≠ 2w. Thus we have eliminated the case for n of this form as well.

Therefore, it is not possible for any n to fulfill the criteria ϕ(n) = k, where k is twice a prime and k + 1 is composite.

Day 18, October 19, notes scribed by Rose Koch.

Problem 26 (Bertrand’s Postulate) There exists a prime between n and 2n for all n ≥ 2

To begin, we offer a preliminary result:

Lemma: If n ≥ 2, then ∏_{p≤n} p ≤ 4^{n} where p is a prime.

This appears to be quite an imprecise approximation. Consider, for example, the case where n = 10. Then we would have 2 · 3 · 5 · 7 < 4^{10} and that does not tell us much that is not immediately obvious. However, as n gets large, the primes we multiply get larger, but we still are only multiplying the right hand side of the inequality by 4’s. The following proves the result for all values of n:

Proof:

Our plan will be to partition the integers from 1 to n and look at the product of the primes in a given partition, bound this product with some binomial coefficients, and attain the desired inequality. Note that we only need to worry about n being odd since ∏_{p≤(2k−1)} p = ∏_{p≤(2k)} p for k ≥ 2.

To partition the integers, choose some n and let n_{0} = n. Define n_{i} = \frac{n_{i−1}±1}{2}. Select plus or minus on the basis of ensuring n_{i} is odd. For example, let n_{0} = 95. Then we would get the following sequence:

n_{1} = 47, n_{2} = 23, n_{3} = 11, n_{4} = 5, n_{5} = 3, n_{6} = 1, n_{7} = 1, etc.

Since this will always be a decreasing string of integers it will be finite and will terminate at 1. Note that 3 must come before the first one in this list since n_{i} = 1 = \frac{n_{i−1}±1}{2} implies that n_{i−1} is either 1 or 3. If it is 1, then n_{i} cannot be the first 1. Denote k as the subscript of n such that n_{k} = 3 (i.e., the last n_{i} > 1).

Consider: ( \begin{matrix}n_{i−1} \\ n_{i} \end{matrix} ). Note that any prime, p, strictly between n_{i} and n_{i−1} will

divide n_{i−1}!. However, p does not divide n_{i−1}!(n_{i−1} − n_{i})! because p > n_{i} and n_{i−1} − n_{i} is even (which forces p > n_{i−1} − n_{i} since p is odd). Therefore it divides

( \begin{matrix}n_{i−1} \\ n_{i} \end{matrix} ). It follows immediately that

∏_{n_{i}<p<n_{i−1}} p| ( \begin{matrix}n_{i−1} \\ n_{i} \end{matrix} ) ⇒ ∏_{3<p<n} p| ∏_{i=1}^{k} ( \begin{matrix}n_{i−1} \\ n_{i} \end{matrix} )

We now show

∏_{i=1}^{k} ( \begin{matrix}n_{i−1} \\ n_{i} \end{matrix} ) < 4^{n}

The binomial theorem implies

(1 + 1)^{n_{i−1}} = 1 + ( \begin{matrix}n_{i−1} \\ 1 \end{matrix} ) + … + ( \begin{matrix}n_{i−1} \\ n_{i} \end{matrix} ) + … + ( \begin{matrix}n_{i−1} \\ n_{i−1} \end{matrix} ) = 2^{n_{i−1}}.

So ( \begin{matrix}n_{i−1} \\ n_{i} \end{matrix} ) < 2^{n_{i−1}}. Since ( \begin{matrix}n_{i−1} \\ n_{i} \end{matrix} ) = ( \begin{matrix}n_{i−1} \\ n_{i−1} − n_{i} \end{matrix} ), ( \begin{matrix}n_{i−1} \\ n_{i} \end{matrix} ) appears twice

in the expansion for (1+1)^{n_{i−1}} so we can divide the right hand side of the inequality by 2 to get

( \begin{matrix}n_{i−1} \\ n_{i} \end{matrix} ) < 2^{n_{i−1}−1}.

It follows that

∏_{i=1}^{k} ( \begin{matrix}n_{i−1} \\ n_{i} \end{matrix} ) < ∏_{i=1}^{k} 2^{(n_{i−1}−1)} = 2^{(∑_{i=1}^{k} n_{i−1}−k)}

Note that

∑_{i=1}^{k} n_{i} ≤ ∑_{i=1}^{k} \frac{n_{i−1} + 1}{2} = \frac{1}{2} ∑_{i=1}^{k}(n_{i−1} + 1)

by the construction of the n_{i}’s. By the definition of n_{0} and n_{k}, rewrite the sum on the left to read

∑_{i=1}^{k} n_{i} = n_{k} − n_{0} + ∑_{i=1}^{k} n_{i−1} = 3 − n + ∑_{i=1}^{k} n_{i−1}

This implies that

3 − n + ∑_{i=1}^{k} n_{i−1} ≤ \frac{1}{2} ∑_{i=1}^{k}(n_{i−1} + 1)

So (after multiplying by 2 and rearranging some terms)

∑_{i=1}^{k} n_{i−1} ≤ k − 6 + 2n

We know from earlier in the proof that

∏_{3<p<n} p| ∏_{i=1}^{k} ( \begin{matrix}n_{i−1} \\ n_{i} \end{matrix} )

Which implies that,

∏_{3<p<n} p ≤ ∏_{i=1}^{k} ( \begin{matrix}n_{i−1} \\ n_{i} \end{matrix} )

Combining this last result with what we just proved, we get

∏_{3<p<n} p < 2^{(∑_{i=1}^{k} n_{i−1}−k)} ≤ 2^{2n−6}

Multiplying both sides by 6 gives us

∏_{p<n} p < 6 · 2^{2n−6} < 8 · 2^{2n−6} = 2^{2n−3} < 2^{2n} = 4^{n}

This proves the lemma.

Now we are almost ready to prove Bertrand’s postulate. Before the proof is given, recall from our discussion of Tchebychef’s inequality that if r is the largest exponent such that

p^{r}| ( \begin{matrix}2n \\ n \end{matrix} )

when p is prime, then p^{r} < 2n. Denote the r corresponding to a prime p by r_{p}.

Proof (Bertrand’s postulate): Suppose not. Then, by the Fundamental Theorem of Arithmetic, there exists an n such that:

( \begin{matrix}2n \\ n \end{matrix} ) = ∏_{p≤n} p^{r_{p}}

That is, there are not any primes in the prime factorization of 2n choose n greater than n since there are no primes between n and 2n.

Partition the integers from 1 to n into 3 segments:

1) 1 < p < \sqrt{2n}, 2) \sqrt{2n} < p < \frac{2n}{3}, 3) \frac{2n}{3} < p ≤ n

where p is a prime. First consider case 3. 2n < 3p, so p appears only twice in 2n!

and once in n!. Therefore, p cannot divide ( \begin{matrix}2n \\ n \end{matrix} ) and r_{p} = 0 by definition. In

case 2, p < 2n < p^{2}. So since p^{r} < 2n, r_{p} is at most one. We therefore conclude that:

( \begin{matrix}2n \\ n \end{matrix} ) ≤ ∏_{p<\sqrt{2n}} p^{r_{p}} · ∏_{\sqrt{2n}<p< \frac{2n}{3}} p · ∏_{\frac{2n}{3} <p<2n} p^{0}

Again using the fact that p^{r} < 2n, we note that

∏_{p<\sqrt{2n}} p^{r_{p}} < (2n)^{\sqrt{2n}}

From our lemma, we get,

∏_{\sqrt{2n}<p< \frac{2n}{3}} p < 4^{\frac{2n}{3}}

Combining these last three results, we observe,

( \begin{matrix}2n \\ n \end{matrix} ) ≤ (2n)^{\sqrt{2n}} · 4^{\frac{2n}{3}}

Recall the expansion for (1+1)^{2n} = 2^{2n} from the proof of the lemma. It has 2n+1

terms, none of which is larger than ( \begin{matrix}2n \\ n \end{matrix} ). Therefore, 2^{2n} ≤ (2n + 1) · ( \begin{matrix}2n \\ n \end{matrix} ).

Since (2n)^{2} > 2n + 1, it follows that,

2^{2n} < (2n)^{2} · ( \begin{matrix}2n \\ n \end{matrix} ) ⇒ 2^{2n}(2n)^{−2} < ( \begin{matrix}2n \\ n \end{matrix} ) ≤ (2n)^{\sqrt{2n}} · 4^{\frac{2n}{3}}

⟹ 2^{\frac{2n}{3}} < (2n)^{\sqrt{2n}+2}

Taking the logs of boths sides:

\frac{2n}{3} log 2 − (\sqrt{2n} + 2) log 2n < 0

If n = 550, this is not true. Furthermore, the function f(n) = \frac{2n}{3} log 2 − (\sqrt{2n} + 2) log 2n is increasing (differentiate with respect to n and show f′ > 0) for n > 550. So a contradiction is achieved for values of n larger than 550. It is left as an excercise to confirm the theorem for n < 550. (Hint: It’s pretty clear that the theorem is true for n < 9. 17 is a prime between n and 2n such that 9 ≤ n ≤ 16. 31 is a prime between n and 2n such that 16 ≤ n ≤ 30. 59 works for n such that 30 ≤ n ≤ 60. Continue this process a few more times, and soon you get to n = 550. It’s not as elegant as the proof presented above, but it works.)

Day 20, October 23, notes scribed by Paco Martorell.