Chapter 8

Much Madness is divinest Sense To a discerning Eye …

-Emily Dickinson

The last chapter concludes with a proof that for n ≥ 1 there is a prime, p, such that n < p ≤ 2n. Here we will tie up some loose ends. Under the assumption that there is an n such that this is false, we arrived at the following inequality:

2^{2n/3} < (2n)^{\sqrt{2n}}

We can take the natural log of both sides and move the terms to the left side of the equation.

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

Since \sqrt{2n} is positive, we can divide it out.

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

For n = 500 the quantity on the left is greater than 0, so this inequality does not hold.

\frac{10\sqrt{10}}{3} ln 2 − 3 ln(10) ≈ .399

We want to show that if n ≥ 500, then \frac{\sqrt{2n}}{3} ln 2 − ln(2n) is increasing. So, we can take its derivative, which gives us:

\frac{ln(2)}{3\sqrt{2n}} − \frac{1}{n}

A little algebra shows that this quantity is positive when \sqrt{n} > \frac{3\sqrt{2}}{ln 2}. So, for all n ≥ 38, \frac{\sqrt{2n}}{3} ln 2 − ln(2n) is increasing. Since this function is positive at n = 500, and it is increasing for all n ≥ 500, it must be positive for all n ≥ 500. Therefore, any counterexamples must be less than 500. In order to conclude the proof, we can check all the numbers in this range.

n  prime between n and 2n
1  2
2  3
3, 4  5
5, 6  7
7 − 12  13
13 − 22  23
23 − 42  43
83 − 162  163
163 − 316  317
317 − 500  631

The Test Of the 19 people who took the test, 6 received prime scores. No two people received the

same prime score. The solutions to problems 1-7, or problems which are very similar, are found in previous chapters of the class notes. Here are the solutions to problems 8, 9, and 10.

Problem 8 Prove that any odd prime, other than 5, divides infinitely many of the numbers 1, 11, 111, 1111, …

Proof:

Let r_{n} = 10^{n} + 10^{n−1} + … + 10^{2} + 10 + 1. We can multiply r_{n} by (10 − 1), giving (10^{n+1} − 1). By Fermat’s Little Theorem,

p | 10^{p−1} − 1

So,

p | 9r_{p−2}

Therefore, if p ≠ 3, then p | r_{p−2}. We can use this to construct infinitely many more numbers of this form. If p divides a string of n consecutive 1’s, then p must also divide a strings of 2n, 3n, … consecutive 1’s. More formally, if p | r_{p−2} then p | (10^{p−1}r_{p−2} + r_{p−2}), and p | 10^{p−1}(10^{p−1}r_{p−2} + r_{p−2}) + r_{p−2}, etc.

If p = 3, it is easy to see 3 | 111. So, 3 divides any string of 3n 1’s, where n is an integer.

Problem 9 Prove that no power of 2 can be written as the sum of two or more consecutive integers and that the powers of 2 are the only numbers which cannot be written in this form.

Proof: (first part)

Suppose 2^{m} can be written as the sum of k consecutive integers, k > 1. Then

2^{m} = (n + 1) + (n + 2) + … + (n + k)

Using the formula for triangular numbers, we can rewrite this as:

2^{m} = nk + \frac{k(k + 1)}{2}

2^{m+1} = 2nk + k(k + 1) = k(2n + (k + 1))

So, both k and 2n + (k + 1) must be powers of 2. But, if k is a power of 2, then 2 cannot divide k +1. Hence, 2 cannot divide 2n+(k +1), giving us a contradiction.

Proof: (second part)

All odd numbers can be written as the sum of two consecutive integers. Since every odd number has the form 2k + 1, it can be written as k + (k + 1).

So, now we only need to concern ourselves with the even numbers. Suppose we wish to write 2^{n}q, q odd, as the sum of consecutive integers.

Case 1:

2^{n} ≥ \frac{q − 1}{2}

We can write:

(2^{n} − \frac{q − 1}{2}) + … + (2^{n} − 1) + 2^{n} + (2^{n} + 1) + … + (2^{n} + \frac{q − 1}{2})

= (2^{n} − \frac{q − 1}{2}) + (2^{n} + \frac{q − 1}{2}) + … + (2^{n} − 1) + (2^{n} + 1) + 2^{n}

= \frac{q − 1}{2} · 2 · 2^{n} + 2^{n} = (q − 1)2^{n} + 2^{n} = 2^{n}q

Case 2:

2^{n} < \frac{q − 1}{2}

We can write:

(\frac{q − 1}{2}−(2^{n}−1))+…+(\frac{q − 1}{2}−1)+\frac{q − 1}{2}+\frac{q + 1}{2}+(\frac{q + 1}{2}+1)+…+(\frac{q + 1}{2}+(2^{n}−1))

= (\frac{q − 1}{2} −(2^{n}−1))+(\frac{q + 1}{2} +(2^{n}−1))+…+(\frac{q − 1}{2} −1)+(\frac{q + 1}{2} +1)+ \frac{q − 1}{2} + \frac{q + 1}{2}

= (\frac{q − 1}{2} + \frac{q + 1}{2})2^{n} = 2^{n}q

Notice that in each of these cases we reordered the sum of consecutive integers so that each element of the sum could be paired up with another element, leading to a much simpler form.

All that remains to be done is to show that \frac{q−1}{2} − (2^{n} − 1) ≥ 0. By the original assumption

2^{n} < \frac{q − 1}{2}

So, we can construct the following inequality:

\frac{q − 1}{2} − (2^{n} − 1) > \frac{q − 1}{2} − 2^{n} > 0

Hence, all the terms in the sum are nonnegative.

Problem 10 Prove that

X = ∑_{i=1}^{k} a_{i}N_{i}x_{i}

is a solution to the system of linear congruences x ≡ a_{i} (mod n_{i}), 1 ≤ i ≤ k, where N_{i} = \frac{n_{1}n_{2}...n_{k}}{n_{i}}, and x_{i} is the unique solution less than n_{i} to the congruence N_{i}x ≡ 1 (mod n_{i}).

Proof:

Consider X mod n_{j}. If i ≠ j, then a_{i}N_{i}x_{i} ≡ 0 (mod n_{j}) because there is a factor of n_{j} in each of the N_{i}’s. So, the only nonzero term is a_{j}N_{j}x_{j}.

Now we must show a_{j}N_{j}x_{j} ≡ a_{j} (mod n_{j}). By definition, N_{j}x_{j} ≡ 1 (mod n_{j}). So, X ≡ ∑_{i=1}^{k} a_{i}N_{i}x_{i} ≡ a_{j}N_{j}x_{j} ≡ a_{j} · 1 ≡ a_{j} (mod n_{j}).

Day 21, October 26, notes scribed by Tim McMurry

Lemma:

If am is congruent to bm mod p, where m and p are relatively prime then by an earlier theorem, a ≡ b(modp).

Therefore km ranges over 0, ..., p − 1 (although not neccessarily in the same order), where k ranges over 0, ..., p − 1, and this is a one to one relationship.

Now, for an example: let p = 7, and m = 3.

0m ≡ 0(mod7)
1m ≡ 3(mod7)
2m ≡ 6(mod7)
3m ≡ 9 ≡ 2(mod7)
4m ≡ 12 ≡ 5(mod7)
5m ≡ 15 ≡ 1(mod7)
6m ≡ 18 ≡ 4(mod7)

Problem 89 Show for each n ≥ 1, n = ∑_{d|n} ϕ(d) where the sum is taken over the divisors of n.

Before we go into details in the proof remember that ϕ(k) is the number of integers less than k that are relatively prime to it. We have previously shown that for a prime p, ϕ(p^{k}) = p^{k} − p^{k−1}. Also it has been shown that ϕ(k) is multiplicative, meaning ϕ(xy) = ϕ(x)ϕ(y).

This is a proof by induction.

Case 1: Suppose n = p^{k} for some prime p and some positive integer k. Then

∑_{d|n} ϕ(d) = ϕ(1) + ϕ(p) + ϕ(p^{2}) + ... + ϕ(p^{k})
= 1 + (p − 1) + (p^{2} − p) + ... + (p^{k} − p^{k−1})
= p^{k} = n

as we wished to show. Case 2: Suppose n = p^{t}q^{r} for p, q prime and t,r positive integers.

∑_{d|n} ϕ(d) = ϕ(1) + ϕ(p) + ϕ(p^{2}) + ... + ϕ(p^{t})
+ϕ(1q) + ϕ(pq) + ϕ(p^{2}q) + ... + ϕ(p^{t}q)
+ϕ(1q^{2}) + ϕ(pq^{2}) + ϕ(p^{2}q^{2}) + ... + ϕ(p^{t}q^{2})
⋮
+ϕ(1q^{r}) + ϕ(pq^{r}) + ϕ(p^{2}q^{r}) + ... + ϕ(p^{t}q^{r})

But ϕ(x) is multiplicative, we can make the following transformation:

∑_{d|n} ϕ(d) = 1 ∗ (ϕ(1) + ϕ(p) + ϕ(p^{2}) + ... + ϕ(p^{t}))
+ϕ(q)(ϕ(1) + ϕ(p) + ϕ(p^{2}) + ... + ϕ(p^{t}))
+ϕ(q^{2})(ϕ(1) + ϕ(p) + ϕ(p^{2}) + ... + ϕ(p^{t}))
⋮
+ϕ(q^{r})(ϕ(1) + ϕ(p) + ϕ(p^{2}) + ... + ϕ(p^{t}))

And from Case 1, we can reduce each line:

∑_{d|n} ϕ(d) = 1p^{t}
+ϕ(q)p^{t}
+ϕ(q^{2})p^{t}
⋮
+ϕ(q^{r})p^{t}

Now factoring out a p^{t} we get:

∑_{d|n} ϕ(d) = p^{t}(1 + ϕ(q) + ϕ(q^{2}) + ... + ϕ(q^{r}))

Which again by Case 1 reduces:

∑_{d|n} ϕ(d) = p^{t}q^{r} = n

Case 3: Now for induction on the number of distinct prime factors, assume n = ∑_{d|n} ϕ(d) is true for all n = p_{1}^{t_{1}}p_{2}^{t_{2}}...p_{k}^{t_{k}} where p_{i} are distinct. Consider n′ = p_{1}^{t_{1}}p_{2}^{t_{2}}...p_{k}^{t_{k}}q^{r} where q ≠ p_{i} for all i. Note that the divisors of n′ are the divisors of n times each of the powers of q, so ∑_{d|n′} ϕ(d) = ∑_{d|n} ϕ(d) + ∑_{d|n} ϕ(qd) + ... + ∑_{d|n} ϕ(q^{r−1}d) + ∑_{d|n} ϕ(q^{r}d). Since ϕ(x) is multiplicative:

∑_{d|n′} ϕ(d) = ϕ(1) ∑_{d|n} ϕ(d) + ϕ(q) ∑_{d|n} ϕ(d) + ... + ϕ(q^{r}) ∑_{d|n} ϕ(d)

Since we already know that n = ∑_{d|n} ϕ(d), by our assumption this reduces to: = ϕ(1)n + ϕ(q)n + ... + ϕ(q^{r})n Now pulling the n out, and expanding ϕ(q^{i}) we get:

= n(1 + (q − 1) + (q^{2} − q) + ... + (q^{r} − q^{r−1})) = nq^{r}
= p_{1}^{t_{1}}p_{2}^{t_{2}}...p_{k}^{t_{k}}q^{r}
∑_{d|n′} ϕ(d) = n′

As we wished to show.

Therefore we have shown that ∑_{d|n} ϕ(d) = n for all n where n can be written as a multiplication of distinct prime factors to arbitrary integer powers. Since we know all n can be written as such, we know that this sum holds for all n.

Problem 92

Orders of x mod 13.

1 1  7 12
2 12  8 4
3 3  9 3
4 6  10 6
5 4  11 12
6 12  12 2

Orders of x mod 26.

1 1  9  3  19 12
3 3  11 12  21 4
5 4  15 12  23 6
7 12  17 6  25 2

Orders of x mod 16.

1 1  9 2
3 4  11 4
5 4  13 4
7 2  15 2

Now look at 2^{k} mod 13.

\begin{matrix}k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 2^{k} & 2 & 4 & 8 & 3 & 6 & 12 & 11 & 9 & 5 & 10 & 7 & 1 \end{matrix}

Notice that the order of 2 is the same as the number of elements in the set Z_{13}. By taking powers of 2 we are able to compute the values for every other value in the set. Such generators are called primitive roots.

Notice also that in Z_{16} there are no primitive roots.

Definition of Coset: Given a group G, and element g of G, and a subgroup H of G, the set gH = {gh | h ∈ H} is called a left coset of H. The group element g is fixed while h ranges over the elements of H. It is easy to prove that the left cosets of H in G all have the same number of elements and any two of them are either disjoint or identical.

An example: The evens and the odds modulo 60. Clearly there are no elements in both sets. The evens are a subgroup, if you choose any element in your group, i.e., a number less than 60 and add to it every even number you get either all the evens back, or all the odds. Try it. Then try the same thing with the multiples of 4. In this case there will be 4 distinct cosets, which we could characterize as the 4k, 4k + 1, 4k + 2, and 4k + 3 cosets. Each has the same number of elements, they are pairwise disjoint, and each is formed by choosing a single number less than 60 and addint it to every multiple of 4 and reducing modulo 60.

Now for a more complex example. Consider the complete set B of values mod n. Consider a which is an element of B, and let the operator be multiplication by a modulo n. If a is a primitive root of n then, the set A = {a, a^{2}, ..., a^{n−1}, a^{n}} is B because every element of A is distinct, and the sets A and B are of the same size.

If a is not a primitive root but instead of order k, then A = {a, a^{2}, ..., a^{k}} is one coset of B. Now select some c_{1} from B − A. Consider the set c_{1} · A = {c_{1}a, c_{1}a^{2}, ..., c_{1}a^{k}}. c_{1}A must have order k as well, if not then there exists c_{1}a^{i} ≡ c_{1}a^{j}(modn) which implies c_{1}^{i−j} ≡ 1(modn), which is a contradiction. Clearly also c_{1}A ⋂ A = ∅, because otherwise we could reduce some element to c_{1} ≡ a^{j}(modn) for some j, which contradicts our initial assumption about c_{1}.

If B ≠ A ⋃ c_{1}A, we can then find some c_{2} ∈ B − A − c_{1}A and construct another coset c_{2}A. Now we can define a set of generators of the cosets of a as C = {1, c_{1}, c_{2}, ..., c_{f}}. Clearly this set of generators is not unique because any c_{i} could be replaced by c_{i}a.

B must contain an integral number of cosets of a, otherwise there would be some leftover d, which would be the basis of another coset, but that would then have k elements, and some of these elements sould have to overlap other sets causing a contradiction.

Problem 93 Let the integer a have order k modulo n. Then a^{m} ≡ 1(mod n) iff k|m. Infact k|ϕ(n).

Show if gcd(a,n) =1 then a^{ϕ(n)} ≡ 1(mod n).

Let B = {b_{1}, b_{2}, ..., b_{ϕ(n)}} where b_{i} < n and all b_{i} are relatively prime to n.

Consider the cosets of a under multiplication modulo n. We know that the order of a is k, so each coset of a is of size k. Since the sum of the cosets of a must be B, then k divides the number of elements of B, so k|ϕ(n) as we wished to show.

Now proving the other direction: If k|ϕ(n) then ϕ(n) = qk, so a^{ϕ(n)} ≡ a^{qk} ≡ (a^{k})^{q} ≡ 1^{q} ≡ 1 (mod n)

Problem 91 Prove that order modulo n is well defined i.e. for any pair of integers a,n, with gcd(a,n) = 1, there exists a smallest positive integer k such that a^{k} ≡ 1 (mod n).

From problem 93 we know that for any a raised to some power mod n, (where gcd(a, n) = 1) that a^{ϕ(n)} ≡ 1(modn). We also know that factors of ϕ(n) might also be equivalent to 1, so by the well ordering principle, there exists a smallest such value k such that a^{k} ≡ 1(modn).

Problem 94 If a has order k mod n then a^{i} ≡ a^{j}(mod n) iff i ≡ j(mod k).

Assume a^{i} is congruent to a^{j} modulo n.

Case 1: If i = yk then a^{i} ≡ a^{yk} ≡ (a^{k})^{y} ≡ 1(mod n). Since a^{i} ≡ a^{j}(modn), a^{j} ≡ 1(modn). The only way a^{j} ≡ 1(modn) is for j = zk. Therefore j ≡ i(modk).

Case 2: If i ≠ yk then i = b + xk where 0 < b < k, so a^{i} ≡ a^{b}a^{xk} ≡ a^{b}(modn). From i = b+xk we know that i ≡ b(modn). Since a^{i} ≡ a^{j}(modn), a^{j} ≡ a^{b}(modn). Therefore j ≡ b(modk) so j ≡ i(modk).

Now proving the other direction.

Assume i ≡ j(mod k).

Then there exist c, l, m such that i = kl + c and j = km + c (from the given) where 0 ≤ c < k.

Then a^{i} ≡ a^{kl+c} ≡ a^{kl}a^{c} ≡ (a^{k})^{l}a^{c} ≡ 1^{l}a^{c} ≡ a^{c} (mod n) and a^{j} ≡ a^{km+c} ≡ a^{km}a^{c} ≡ (a^{k})^{m}a^{c} ≡ a^{c}(mod n), so a^{i} ≡ a^{j}(mod n) as we wished to show.

Problem 95 If a has order k mod p, then A = {a, a^{2}, a^{3}, ..., a^{k}} are incongruent mod n.

Suppose not. This implies that there exist some l, m such that 1 ≤ l < m ≤ k and a^{l} ≡ a^{m}(mod n). This in turn means that 1 ≡ a^{m−l}(modn), but this is a contradiction. We assumed that the order is k, but we have just found that the order is m − l which by construction is less than k. Therefore the elements of A are incongruent mod n.

Problem 96 Suppose a has order k mod n, what is the order of a^{h}?

The order of a^{h} is \frac{k}{gcd(h,k)}.

Proof:

Clearly, \frac{h}{gcd(h,k)} is an integer since gcd(h, k) is a factor of h. Therefore since we

know a^{k} ≡ 1(modn), then (a^{h})^{\frac{k}{gcd(h,k)}} ≡ (a^{k})^{\frac{h}{gcd(h,k)}} ≡ 1^{\frac{h}{gcd(h,k)}} ≡ 1(mod n), so \frac{k}{gcd(h,k)} is a multiple of the order of a^{h}.

Show minimal:

Let c = gcd(h, k), d = \frac{h}{c}, e = \frac{k}{c}. Clearly, c, d, e are all integers by construction and gcd(d, e) = 1.

Consider (a^{h})^{\frac{k}{gcd(h,k)}} = (a^{h})^{e} = a^{cde} = (a^{ec})^{d} = (a^{k})^{d} = 1^{d} = 1(modn).

Assume there is the order of a^{h} is smaller, call it f, then we know that hf ≡ 0(modk). However, \frac{k}{gcd(h,k)} is the first time the exponent is a multiple of k, therefore we have a contradiction, and \frac{k}{gcd(h,k)} is the smallest.