Chapter 9

Six is a number perfect in itself, and not because God created the world in six days; rather the contrary is true. God created the world in six days because this number is perfect, and it would remain perfect, even if the work of the six days did not exist.

-St. Augustine

Perhaps the most fundamental concept in abstract algebra is that of a “group”, so what follows is a slightly informal discussion of algebraic groups and some of their properties.

Definition Let G be a set. A binary operation on G is a function that assigns to each ordered pair of elements of G an element of G.

Definition A group is a set G endowed with a binary operation (usually denoted as + or ·) such that,

i) the operation is associative; i.e. for all elements a, b, c of G,

(ab)c = a(bc)

(if we denote the operation as · for the moment); ii) there exists an identity element e in G such that for any a in G,

ae = ea = a;

iii) for every element a in G, there exists some inverse element, denoted a^{−1}, such that

aa^{−1} = a^{−1}a = e.

So, for example, Z is a group under addition because, for all a, b, c ∈ Z,

(a + b) + c = a + (b + c),
a + 0 = 0 + a = a,
a + (−a) = (−a) + a = 0.

In fact, Z happens to be a commutative group. In other words, for all a, b ∈ Z,

a + b = b + a.

Notice, however, that groups need not be commutative. (Those that are commutative are also referred to as Abelian groups. Hence the joke: “What’s purple and commutes? An Abelian grape.”)

If you keep this example in mind, the next few theorems should not surprise you at all.

Theorem 9.1 The identity element of a group is always unique.

Suppose e and e′ are both identity elements of some group G. Then ee′ = e because e′ is an identity, and also ee′ = e′ because e is an identity, but these two statements together imply that e = e′.

Theorem 9.2 If G is a group under some operation denoted · and a, b, c ∈ G, then, if ba = ca, we can conclude that b = c, and similarly, if ab = ac, then we know that b = c. (In other words, we can cancel.)

Suppose ba = ca. Since G is a group, a must have some inverse, a^{−1}. Multiplying our equation by a^{−1} on the right, we get baa^{−1} = caa^{−1}. By the definition of an inverse, aa^{−1} = e where e is the identity element of G, so we have be = ce. But by the definition of the identity element, this gives b = c. We reason similarly in the case where ab = ac.

Warning Unless the group is Abelian, just because ab = ca, we don’t necessarily know that b = c. Theorem 9.3 Each element of a group has exactly one inverse.

Suppose a ∈ G and b and c are both inverses of a. Then ab = e and ac = e where e is the identity element of G. Therefore ab = ac, but by the previous theorem, this means b = c.

(Theorems 9.2 and 9.3 are modified versions of those on page 40 of the 1986 edition of Joseph Gallian’s book Contemporary Abstract Algebra.)

Before we have another theorem, let’s look at some other examples that you may recognize.

Examples

1) Z is not a group under multiplication because, although it does have an identity (namely 1), most elements have no inverse. In fact, the only elements with inverses are 1 and −1.

2) R is an Abelian group under addition.

3) R is not a group under multiplication because 0 has no inverse. (There is no real number you can multiply by 0 to get 1.)

However, this problem is easily solved: R\{0} (the set of real numbers not including 0) is a group under multiplication.

4)

\{[ \begin{matrix}a & b \\ c & d \end{matrix} ] | a, b, c, d ∈ Q and ad − bc ≠ 0\}

is a group under matrix multiplication. (We must exclude matrices whose determinant is 0 because they have no inverses.)

Notice that this group is not Abelian.

Here’s another theorem which may interest you in light of the problems we’ve been working on lately.

We already know what it means to talk about the order of an element, but groups have orders, too.

Definition Let G be a group under some binary operation. Then G is a set, and the order of the group, denoted |G| is the number of elements in G.

Theorem 9.4 Every element of a finite group has a finite order.

Let a be any element of a finite group G, and consider the set A = {a, a^{2}, a^{3}, …}. Since G is finite, and every element of A must be in G (by the definition of a binary operation), there can be at most |G| distinct elements in A. Thus, there must be some i, j such that a^{i} = a^{j}. Without loss of generality, suppose i ≥ j. Then if e is the identity of G, we can say

a^{i} = a^{j}e,

and then by Theorem 9.2 we can cancel to get

a^{i−j} = e.

Hence, the order of a is no greater than i − j, and therefore the order of a is finite.

More examples

6) If n is an integer, then the set {0, 1, 2, 3, …, n} is a group under addition. This group is usually denoted Z_{n}.

Let’s consider the case where n = 4, i.e. the group Z_{4}. The addition table for this group looks like this:

+ 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2

There are lots and lots of interesting things about this table.

Since the group is Abelian, the table is symmetric about the main diagonal.

Also, every element of the group appears exactly once in each row and once in each column. This will actually happen with all groups. Suppose two elements of the same row were equal. Let a ∈ G be the element which“labels” the row. (So in our example, 3 is the element labelling the fourth row.) Then the two elements in question must be of the form ab and ac for some b, c ∈ G (notice that ab would be in the column headed by b and ac would be in the column headed by c). We were supposing these two elements were equal, so we have ab = ac. By Theorem 9.2, this means b = c. But then the columns headed by b and c are actually the same column, and ab and ac are actually both in the same place on the table.

In particular, 0 appears once in each row and once in each column. You can see this as a result of every element having an inverse.

Notice also that the second row is just the first row shifted one place to the left, and similarly the third row is the first row shifted two places to the left, and the fourth row is the first row shifted three places to the left. In such a situation, we say that the rows are cyclic permutations of each other (i.e. they have the same elements, in the same order, but you just read through them starting at a different place each time). Because the rows are cyclic permutations of each other, we call this a cyclic group. It turns out that there is really only one group of any particular order which is cyclic, so this is “the cyclic group of order four”. (Note that not all groups are cyclic.)

It happens to be true that cyclic groups always have an element whose order is the order of the group. Here, for example, 1 and 3 have order 4 so we get:

1, 1 + 1 = 2, 1 + 1 + 1 = 3, 1 + 1 + 1 + 1 = 4 ≡ 0 (mod 4),

3, 3 + 3 = 6 ≡ 2 (mod 4), 3 + 3 + 3 = 9 ≡ 1 (mod 4), 3 + 3 + 3 + 3 = 12 ≡ 0 (mod 4).

Such elements are called generators and are said to generate the group.

7) It turns out that there are really only two different groups of order 4. One is Z_{4}, and the other is the one we will construct now.

Let’s call the elements of our group e, a, b, c where e is the identity element. We know right away what part of the table for this group must look like, just by the definition of an identity:

· e a b c
e e a b c
a a
b b
c c

So we need to choose what a^{2} will be. It turns out that if we let a^{2} be b or c then we will have no choice about how to fill in the rest of the table (because of the constraint that each element must appear exactly once in each row and once in each column). If we let a^{2} be e, then we do get to choose whether b^{2} is a or e. It so happens that if we let a^{2} be b or c or if we let a^{2} be e and then let b^{2} be a we get the “same” group as Z_{4}. (The groups are the same in the sense that they are all cyclic; each one is generated by one of its elements. This means that if we re-order the row and column headings in the appropriate way the table we get will look exactly the same as the table for Z_{4} except that the names of the elements will have changed. For example, maybe everywhere there was a 2, there is now a b.)

On the other hand, if we let a^{2} = e and we let b^{2} = e we get a group which is genuinely different from all of the others. Its table looks like this:

· e a b c
e e a b c
a a e c b
b b c e a
c c b a e

Notice that all the elements (except e itself) have order 2. Thus, there is no element that generates the group, and no matter how we rearrange the table, it will not look like the table for Z_{4}. This second group of order 4 is called the Klein-4 group.

8) The set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} is not a group under multiplication modulo 10. The elements of the set which are not relatively prime to 10 have no orders (as we have seen in class) and no inverses.

For this reason, we consider the set {1, 3, 7, 9} of those numbers less than 10 and relatively prime to 10. This set under multiplication modulo 10 is normally referred to as “the group of units mod 10” and denoted U(10). (A unit is something with an inverse.)

Notice that the number of elements in U(n) is equal to ϕ(n).

Here is the multiplication table for U(10) (there’s a reason for the seemingly strange ordering of the rows and columns):

\begin{matrix}· & 1 & 3 & 9 & 7 \\ 1 & 1 & 3 & 9 & 7 \\ 3 & 3 & 9 & 7 & 1 \\ 9 & 9 & 7 & 1 & 3 \\ 7 & 7 & 1 & 3 & 9 \end{matrix}

We claimed earlier that there were only two groups of order 4, so this had better be one of them. In fact, if you look at the table it has exactly the same structure as the table for Z_{4}. To see why this is true, notice that 3 generates U(10) because we have

3, 3^{2} = 9, 3^{3} = 27 ≡ 7 (mod 10), 3^{4} = 81 ≡ 1 (mod 10).

Thus, we can rewrite the table as:

\begin{matrix}· & 3^{0} & 3^{1} & 3^{2} & 3^{3} \\ 3^{0} & 3^{0} & 3^{1} & 3^{2} & 3^{3} \\ 3^{1} & 3^{1} & 3^{2} & 3^{3} & 3^{0} \\ 3^{2} & 3^{2} & 3^{3} & 3^{0} & 3^{1} \\ 3^{3} & 3^{3} & 3^{0} & 3^{1} & 3^{2} \end{matrix}

(Now you see why we wrote the columns and rows in the order we did.) Notice that if you only read the exponents, this table really is exactly the same as the one for Z_{4}. This is because any two elements are actually powers of three, so when we multiply them we really just need to add the exponents of the 3’s and then since 3^{4} = 1 we can reduce the exponent of the answer mod 4.

9) Not all groups of units are cyclic, as U(10) was. In fact, U(15) is not cyclic.

U(15) = {1, 2, 4, 7, 8, 11, 13, 14}

Here is the multiplication table:

\begin{matrix}· & 1 & 2 & 4 & 7 & 8 & 11 & 13 & 14 \\ 1 & 1 & 2 & 4 & 7 & 8 & 11 & 13 & 14 \\ 2 & 2 & 4 & 8 & 14 & 1 & 7 & 11 & 13 \\ 4 & 4 & 8 & 1 & 13 & 2 & 14 & 7 & 11 \\ 7 & 7 & 14 & 13 & 4 & 11 & 2 & 1 & 8 \\ 8 & 8 & 1 & 2 & 11 & 4 & 13 & 14 & 7 \\ 11 & 11 & 7 & 14 & 2 & 13 & 1 & 8 & 4 \\ 13 & 13 & 11 & 7 & 1 & 14 & 8 & 4 & 2 \\ 14 & 14 & 13 & 11 & 8 & 7 & 4 & 2 & 1 \end{matrix}

To decide whether the group is cyclic, we need to see if any element generates, i.e. if the order of any element is as the same as the order of the group. Notice first that 4^{2} = 1, so 4 has order 2. Then notice that every element squares to either 4 or 1. Those that square to 1, have order 2 (except 1 itself which has order 1), and those that square to 4 have order 4. Thus, no element has order 8, and the group is not cyclic.

Notice that what we are really looking for, when we try to find an element whose order is the order of the group, is an element of order ϕ(n), in other words, a primitive root of n. Looking at the problem this way, we see that problem 105 tells us when U(n) is cyclic.

Next on the program is a theorem from Gauss which is really another version of problem 98 (showing that every prime modulus has a primitive root).

Theorem 9.5 If d|p − 1 where p is prime, then there are ϕ(d) elements of U(p) = {0, 1, 2, …, p − 1} of order d.

(So in particular this will show that there are ϕ(p − 1) elements of U(p) which have order p − 1.)

Let e be some divisor of p − 1, and consider the equation

x^{e} − 1 ≡ 0 (mod p).

Suppose there is some solution a whose order is e. So

a^{e} ≡ 1 (mod p).

Then a^{k} is also a solution to the equation because

(a^{k})^{e} − 1 = (a^{e})^{k} − 1 ≡ 1^{k} − 1 (mod p) ≡ 0 (mod p).

Since |a| = e, the elements of {a, a^{2}, a^{3}, …, a^{e}} are all distinct. But by Riddle’s Lemma, the equation can have at most e solutions, so {a, a^{2}, a^{3}, …, a^{e}} is actually the entire set of solutions.

Now consider a^{r} where gcd(r, e)= g ≠ 1. Then r = sg and e = tg for some s ≤ t < e. So we get

(a^{r})^{t} = a^{sgt} = (a^{e})^{s} ≡ 1^{s} (mod p) ≡ 1 (mod p),

which means that |a^{r}| ≤ t < e. In other words, the only elements of {a, a^{2}, a^{3}, …, a^{e}} that can have order e are those whose exponents are relatively prime to e.

Now suppose that f(e) is the actual number of elements of order e in U(p). Then by what we’ve just seen f(e) ≤ ϕ(e).

Clearly,

∑_{e|p−1} f(e) = |U(p)| = ϕ(p) = p − 1.

Also, by problem 89,

∑_{e|p−1} ϕ(e) = p − 1.

Therefore,

∑_{e|p−1} ϕ(e) − f(e) = 0.

But we had said that f(e) ≤ ϕ(e), so ϕ(e) − f(e) ≥ 0 for any particular e. Thus, the only way the sum can be 0 is if ϕ(e) − f(e) is actually 0 for all e, in other words if ϕ(e) = f(e) for all e. This is what we set out to prove.

It follows directly that U(p) is cyclic (because it must have an element of order p − 1). Then since |U(p)| = ϕ(p) = p − 1, this means that U(p) is essentially the same as any other cyclic group of order p − 1, including most notably Z_{p−1}.

Continuing our tour of mathematical greats, here are some contributions from Fermat and Euler.

Remember the Fermat primes?

2 + 1 = 3

2^{2} + 1 = 5

2^{2^{2}} + 1 = 17

2^{2^{3}} + 1 = 257

2^{2^{4}} + 1 = 65, 537

These are all prime, and Fermat thought that 2^{2^{n}} + 1 was always prime. Well, the next example is

2^{2^{5}} + 1 = 4, 294, 967, 297,

so you can see where trying to factor it by hand might be a pain.

Euler showed this:

Theorem 9.6 If p is an odd prime, and p|a^{2} + 1, then p = 4k + 1.

By contradiction. Suppose p = 4k + 3 and p|a^{2} + 1. Then a^{4k+2} = a^{p−1} ≡ 1 (mod p) by Fermat’s Little

Theorem. Therefore,

p|a^{4k+2} − 1.

By hypothesis, p|a^{2} + 1, so

p|(a^{2} + 1)(a^{4k} − a^{4k−2} + a^{4k−4} − … + a^{4} − a^{2} + 1)
p|(a^{4k+2} + 1).

But this together with p|a^{4k+2} − 1 means

p|(a^{4k+2} + 1) − (a^{4k+2} − 1)
p|2,

but p is an odd prime, so this is a contradiction.

Day 23, November 2, notes scribed by Beth Robinson.

Theorem 9.7 If p is an odd prime and p|a^{4} + 1, then p = 8k + 1.

Proof:

p must be of one of the following forms: 8k + 1, 8k + 3, 8k + 5 and 8k + 7.

8k + 3 and 8k + 7 can be eliminated because by the previous theorem, p cannot be of the form 4k + 3.

So, we assume that p = 8k + 5 and look for a contradiction. The process is the same as it was for Theorem 9.6.

If p|a^{4} + 1, p must be relatively prime to a, so by Fermat’s Little Theorem,

p|a^{8k+4} − 1

p|a^{4} + 1 also gives us that

p|(a^{4} + 1)(a^{8k} − a^{8k−4} + ... + a^{8} − a^{4} + 1)
p|a^{8k+4} + 1

But then,

p|(a^{8k+4} + 1) − (a^{8k+4} − 1),

so p|2, which gives us a contradiction.

Thus, p must be of the form 8k + 1.

Theorem 9.8 If p is odd prime and p|a^{8} + 1, then p = 16k + 1.

The proof follows the same pattern as the proof of Theorem 2.

Theorem 9.9 p|a^{16} + 1 ⇒ p = 32k + 1.

Theorem 9.10 p|a^{32} + 1 ⇒ p = 64k + 1. etc.

So, why do we care about this? Recall that the Fermat Primes are primes of the form 2^{2^{n}} + 1. So the first few Fermat

primes are: 3, 5, 17, 257, 65537. In Euler’s time these were all known to be prime, but it was not known whether or not the next one, 2^{2^{5}} + 1 = 4, 294, 967, 297 was prime.

Euler noticed that by Thm 5, we know that if p divides 2^{32} + 1, then p = 64k + 1 So we only have to check primes of this form.

The first 5 primes of this form are 193, 257, 449, 577 and 641. The long division will quickly show that 193, 257, 449, and 577 are not factors of 4,294,967,297, but when you get to 641, the result is different. Dividing 4,294,967,297 by 641 you get exactly 6,700,417! So 2^{2^{5}} is not prime, a counter-example to Fermat’s conjecture that all numbers of this form are prime.

One reason we’re interested in Fermat primes is that Gauss showed that they are the only odd primes whose regular polygons can be constructed with a straight edge and compass. The actual construction of a 65537-gon has been completed by some poor graduate student who spent 8 years on it. No one has looked at it since!

Final Projects Here are some interesting topics that we haven’t covered in class.

1. Continued fractions (this is big, way cool)

This is an alternative way of writing numbers that has some nice properties.

If you define a series a_{0}, a_{1}, … as follows: a_{0} = ⌊x⌋, a_{1} = ⌊\frac{1}{x−a_{0}} ⌋, a_{2} = ⌊_{\frac{1}{\frac{1}{x−a_{0}} −a_{1}}} ⌋, etc.

Then you can write x as

x = a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2}+···}}

Here’s an example: Write \sqrt{7} as a continued fraction.

a_{0} = ⌊\sqrt{7}⌋ = 2

a_{1} = ⌊\frac{1}{\sqrt{7} − 2}⌋ = ⌊\frac{\sqrt{7} + 2}{3}⌋ = 1

a_{2} = ⌊ \frac{1}{\frac{\sqrt{7}+2}{3} − 1}⌋ = ⌊\frac{3}{\sqrt{7} − 1}⌋ = ⌊\frac{\sqrt{7} + 1}{2}⌋ = 1

a_{3} = ⌊ \frac{1}{\frac{\sqrt{7}+1}{2} − 1}⌋ = ⌊\frac{2}{\sqrt{7} − 1}⌋ = ⌊\frac{\sqrt{7} + 1}{3}⌋ = 1

a_{4} = ⌊ \frac{1}{\frac{\sqrt{7}+1}{3} − 1}⌋ = ⌊\frac{3}{\sqrt{7} − 2}⌋ = ⌊\sqrt{7} + 2⌋ = 4

a_{5} = ⌊\frac{1}{\sqrt{7} + 2 − 4}⌋ = ⌊\frac{1}{\sqrt{7} − 2}⌋ = ⌊\frac{\sqrt{7} + 2}{3}⌋ = 1

But we have already come accross \frac{\sqrt{7}+2}{3}, so from here on it will repeat. So

\sqrt{7} = 2 + \frac{1}{1 + _{\frac{1}{1+_{\frac{1}{1+ \frac{1}{4+ \frac{1}{1+···}}}}}}}

The standard notation for this is:

\sqrt{7} = [2; 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, …]

So an irrational number like \sqrt{7} can be written as a repeating continued fraction!

2. Pell’s Equation

x^{2} − dy^{2} = 1

where d is a non-square.

Notice that if d = 2, this bears a close resemblance to problem 2g. There is also a close connection between Pell’s equation and continued fractions.

3. Partitions of Integers (big, way cool, could be way deep but need not)

To partition a number is to write it as a sum of smaller numbers (for example, 7 = 1 + 1 + 1 + 1 + 1 + 1 + 1 = 1 + 1 + 2 + 3 = 3 + 4, etc.). Counting the ways of doing this leads to some interesting problems.

4. Sums of Squares

We will be able to characterize the sums of two squares in class, but there are some more questions that we won’t get to. When can a number be written as the sum of 3 squares? Can every number be written as the sum of 4 squares?

5. Waring’s Problem

This is a generalization of the previous problem. Given an exponent k, is there a number g(k) such that you can write any number as the sum of g(k) kth powers? The answer is yes, and the value of g is known for certain numbers. For example, g(3) is known to be 9, though 8 and 9 cubes are only needed for a few special cases - in general, for big numbers 7 cubes is enough.

6. Mersenne primes

This topic includes the Hill-Schroeder conjecture that has been hinted at but never quite stated clearly or proved. Another interesting subject would be the Lucas Test for Primality.

7. Special cases of Fermat’s Last Theorem

There’s a nice, fairly simple proof that X^{4} + Y^{4} = Z^{4} has no solutions. The proof for X^{3} + Y^{3} = Z^{3} is also accessible.

8. Fibonacci numbers (and Lucas Numbers)

These are a couple sequences of numbers that have some interesting properties.

9. Factoring

There are some tricks that can help speed up the factoring of numbers.

10. Pseudoprimes, or Carmichael Numbers

We know from Fermat’s little Theorem that p|a^{p} − a if p is prime. This would be a nice primality test if the converse were true. But we’ve seen that it’s not: for instance 341|2^{341} − 2. But would non-primes such as 341 satisfy x|a^{x} − a for all a? It turns out there are some non-prime numbers which satisfy this expression for all values of a, and these are known as Carmichael numbers.

11. Farey Series

List the numbers (rationals) from 0 to 1 with denominator ≤ n in increasing order. That’s a Farey series. For example, the Farey series for n = 4 is:

\frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1}

12. Möbius Inversions

If

F (n) = ∑_{d|n} f(d)

for some multiplicative function f, then you can find a function μ(m) so

f(n) = ∑_{m|n} μ(m)F (m)

This function mu(m) is known as a Möbius inversion and it has some interesting uses.

13. The average order of arithmetical functions

Looking at ∑_{i=1}^{n} f(i) for erratic functions such as ϕ(i) can help to smooth them out to some extent, and allow us to understand them better.

Let’s get back to problems. Problem 100 If n has a primitive root then it has ϕ(ϕ(n)).

Proof:

Let a be a primitive root of n.

From problem 99, we know that a, a^{2}, … a^{ϕ(n)} are congruent to the positive integers less then and relatively prime to n in some order, so lets say:

a_{1} ≡ a, a_{2} ≡ a^{2}, …, a_{ϕ(n)} ≡ a^{ϕ(n)}

From problem 96, we know that if x is the order of a_{k}, then

x = \frac{ϕ(n)}{gcd(k, ϕ(n))}

a_{k} is a primitive root when x = ϕ(n), which is true exactly when k and ϕ(n) are relatively prime. This occurs for ϕ(ϕ(n)) values of k.

Problem 97 Find primitive roots for n = 11, 15, 71, 191. The primitive roots of the first thousand or so numbers are available on Warren’s website.

Day 24, November 4, notes scribed by Matthew Riddle

An indian chief with three wives discovered that the first was pregnant, and in accordance with custom, constructed her a doehide teepee for her confinement. When the second squaw became simultaneously subject to the same condition, he constructed her a buffalo hide teepee. Then the third became pregnant, and he gave her a hippopotamus hide teepee. The first gave birth to a son, and the second squaw gave birth to a son, and the third squaw gave birth to twin sons. The moral of the story is that the squaw of the hippopotamus hide is equal to the sons of the other two squaws.

-Anonymous

Final Projects: After much die-rolling and group positioning, the groups for the final projects were finally chosen and selected their projects. Presentations will be on the following:

Group (1)  Tim, Matt  Continued Fractions
Group (2)  Beth, Mark  Fermat’s Last Theorem
Group (3)  Krista, Millie  Farey Series
Group (4)  Jordan, Mimi  Partitions of Integers
Group (5) Warren, Drew, Peter  Order of ϕ(n)
Group (6)  Rose, Michael  Pseudoprimes
Group (7)  Annie, Marie  Sums of Squares
Group (8) Steve, Paco, Mike B.  Waring’s Problem

Problem 101. What can you say about ϕ(2^{n} − 1), n > 1?

Theorem 9.11 If p is prime, then p^{b}|ϕ(2^{p} − 1), where b is the number of distinct prime factors of 2^{p} − 1.

Proof: Since p is prime, all prime divisors of 2^{p} − 1 are of the form 2kp + 1. This is by Hill’s Conjecture. So

2^{p} − 1 = (2k_{1}p + 1)^{r_{1}}(2k_{2}p + 1)^{r_{2}}… (2k_{b}p + 1)^{r_{b}}.

Recalling one of our standard formulas for phi(n), this means that ϕ(2^{p} − 1) = (2k_{1}p)(2_{2}kp)… (2k_{b}p)(2k_{1}p + 1)^{r_{1}−1}(2k_{2}p + 1)^{r_{2}−1}… (2k_{b}p + 1)^{r_{b}−1}.

So p^{b}|ϕ(2^{p} − 1).

This theorem gives rise to the conjecture that this is true for all n, whether prime or not. The question was dropped in class, but it is interesting to note that it is true.

Problem 102. The odd prime divisors of n^{2} + 1 are of the form 4k + 1.

Proof: See Problem 74.

Problem 103. There are infinitely many primes of the form 4k + 1.

Proof: By contradiction. Suppose that there are finitely many such primes, and consider the set of all of them: {p_{1}, p_{2}, p_{3}, … p_{N}}. Now consider P = (p_{1}p_{2}p_{3}… p_{N}) + 1. The product of numbers of the form 4k + 1 is always of the form 4k + 1, so when we add one, it must be of the form 4k + 2.

Now, P is not a power of 2 so it has at least one odd prime divisor. From the previous theorem, since P is one more than a square, this divisor is of the form 4k + 1. But none of {p_{1}, p_{2}, p_{3}, … p_{N}} divides P, so there must be another prime of the form 4k + 1, which contradicts our initial assumption.

Problem 104. 2^{k} does not have a primitive root, for k > 2.

Proof: Note, first of all, that 2^{3} = 8 does not have a primitive root. ϕ(8) = 4, but 1^{2} = 1, 3^{2} = 9, 5^{2} = 25, and 7^{2} = 49, which are all congruent to 1 mod 8. So none of these has order 4.

Now to show that 2^{k} does not have a primitive root for k > 3, consider the set A = {1, 3, 5, 7} and the set B = {1, 3, 5, 7,… 2^{k}−1}, and suppose, in order to obtain a contradiction, that there is a primitive root for 2^{k} in B.

Define a function f:B ⟼ A by f(b) = b (mod 8) for all b ∈ B. Notice that f is onto, and that f(cd) ≡ f(c)f(d) (mod 8).

Let x be a primitive root of 2^{k}. So x ∈ B. Now, since x is a primitive root of 2^{k}, every element of B is equal to a power of x which is unique up to equivalence (mod ϕ(2^{k})). So choose any a ∈ A. There is an element in B which maps to a under f, so there is a power of x which maps to a under f, i.e. f(x^{i}) = a for some i. But recall that f(x^{i}) = (f(x))^{i}. So (f(x))^{i} ≡ a (mod 8).

We now have an element of A, f(x), such that every element of A is some power of f(x). So f(x) must be a primitive root of 8. But this is a contradiction, since we have shown that 8 has no primitive roots.

Problem 105. Suppose that m > 2, n > 2, and gcd(m, n)= 1. Then the integer mn has no primitive roots.

Proof: Let a be relatively prime to mn. Show: a^{\frac{ϕ(mn)}{2}} ≡ 1 (mod mn).

This is sufficient, since \frac{phi(mn)}{2} < phi(mn).
Now, a^{ϕ(m)} ≡ 1 (mod m) and a^{ϕ(n)} ≡ 1 (mod n).

Recall from our classification of the parity of phi(n) that ϕ(m) and ϕ(n) are both even, since m, n > 2. So ϕ(m)|\frac{ϕ(m)ϕ(n)}{2} and ϕ(n)|\frac{ϕ(m)ϕ(n)}{2}.

So a^{\frac{ϕ(nm)}{2}} = a^{\frac{ϕ(n)ϕ(m)}{2}} ≡ 1 (mod m) and a^{\frac{ϕ(nm)}{2}} = a^{\frac{ϕ(n)ϕ(m)}{2}} ≡ 1 (mod n). But m and n are relatively prime, so this means that a^{\frac{ϕ(nm)}{2}} ≡ 1 (mod mn), and we’re done.

Characterizing Numbers with Primitive Roots:

Theorem 9.12 If x is a power of an odd prime, or twice a power of an odd prime, or 4, then x has a primitive root. Otherwise it doesn’t.

No proof was given in class, but the ”otherwise” part follows from Problems 104 and 105. It remains to show that powers ≥ 2 of odd primes or their multiples by two actually must have primitive roots.

Problem 107. Suppose that p is an odd prime, and gcd(a, p) = 1. Show that a solution to the quadratic congruence (2ax+b) ≡ (b^{2} −4ac) (mod p) provides a solution to the congruence ax^{2} + bx + c ≡ 0 (mod p).

Proof:

(2ax + b)^{2} ≡ b^{2} − 4ac (mod p)
so …
4a^{2}x^{2} + 4axb + b^{2} ≡ b^{2} − 4ac (mod p)

which means that … 4a^{2}x^{2} + 4axb + 4ac ≡ 0 (mod p)

4a(ax^{2} + bx + c) ≡ 0 (mod p)

but 4 and a are both relatively prime to p, so by the cancellation law for modular congruences, ax^{2} + bx + c ≡ 0 (mod p)

Problem 108. Solve 5x^{2} − 6x + 2 ≡ 0 (mod 13).

Solution: Consider the congruence (2(5)x + (−6))^{2} ≡ (6^{2} − 4(5)(2)) (mod 13). This is (10x − 6)^{2} ≡ 9 (mod 13). First, let’s solve y^{2} ≡ 9 (mod 13). y could be 3 or -3, i.e. 3 or 10. So 10x − 6 ≡ 3 (mod 13) and 10x − 6 ≡ 10 (mod 13) give us our solutions to the original quadratic congruence. From the first, we get x = 10, and from the second, we get x = 12.

Definition: Let p be an odd prime, and gcd(a, p) = 1. Then if the congruence x^{2} ≡ a (mod p) has a solution, we say that a is a quadratic residue of p. Otherwise, a is a quadratic nonresidue of p.

Problem 109. Which integers modulo 13 are quadratic residues (mod 13)?

a a^{2}(mod13)
1  1
2  4
3  9
4  3  Notice that the list repeats itself in reverse
5  12  in the second half. But of course this is true,
6  10  since 12 = -1, so 12^{2} ≡ (−1)^{2} (mod 13).
7  10
8  12
9  3
10  9
11  4
12  1

Problem 110. Let p be an odd prime, and gcd(a, p) = 1. Then a is a quadratic residue of p if and only if a^{(p−1)/2} ≡ 1 (mod p).

Proof: First, assume that a is a quadratic residue of p. Then there is some x such that x^{2} ≡ a (mod p). So a^{(p−1)/2} ≡ (x^{2})^{(p−1)/2} ≡ x^{n−1} ≡ 1 (mod p).

Now, in the other direction: Assume that a^{(p−1)/2} ≡ 1 (mod p). Show that there is an x such that x^{2} ≡ a (mod p).

Let b be a primitive root of p. (p is an odd prime, so it must have one.) Now, a ≡ b^{k} (mod p) for some k.

Case 1: k is even: k = 2n for some n. So a ≡ b^{2n} ≡ (b^{n})^{2} (mod p). So b^{n} is an x which works, and a must be a quadratic residue of p.

Case 2: k is odd: k = 2n + 1 for some n. So a ≡ b^{2n+1} (mod p). Therefore a^{(p−1)/2} ≡ (b^{2n+1})^{(p−1)/2} ≡ b^{m(p−1)}b^{(p−1)/2} ≡ b^{(p−1)/2} (mod p). By our assumption, a^{(p−1)/2} ≡ 1 (mod p), so b^{(p−1)/2} ≡ 1 (mod p). However, this is a contradiction, since b was chosen to be a primitive root of p.

Problem 111. If a is a quadratic residue of an odd prime p, then a is not a primitive root of p.

Proof: Let a be a quadratic residue of an odd prime p. Then by 110, the order of a is at most \frac{p−1}{2}. But ϕ(p) = p − 1, and the last time that Jordan checked, \frac{ϕ(p)}{2} was less than ϕ(p).

25th day, November 6th, notes scribed by Mark Schroeder