Section 2 - Primes - The Basics

Some integers have lots of factors, and some have few, but since 1*n = n, all integers n have at least two factors, namely 1 and n.

Definition. A **prime** is a positive
integer that has exactly two factors. Alternatively, a prime is a positive
integer p, different from 1, such that the only two factors of p are 1 and p.

Note : The integer 1 is not considered a
prime. In advanced algebra, 1, and -1,
are known as **units** of the ring of integers. There is an analogous
definition of a prime that guarantees that a unit can never be a prime and vice
versa. For instance, the product of a unit and a prime is a prime, whereas the
product of two primes is not. Much of the basic theory relating to primes can
be viewed within the abstract algebra context of integral domains, but we shall
restrict ourselves to the integers for now.

All integers greater than 1 that are not
primes are called **composite** numbers. If n is composite, then it must be
of the form n = ab for some a and b such that both a and b are greater than 1
and less than n.

Lemma 2.1 If p is a prime and p divides ab then p divides a or p divides b.

Proof : Suppose not. Then a = px_{1} +
x_{2} and b = py_{1} + y_{2}. Multiplying, we have ab =
p^{2}.x_{1}y_{1} + px_{1}y_{2} + px_{2}y_{1}
+ x_{2}y_{2} = pz + x_{2}y_{2} from some z. If
x_{2}y_{2} is greater than p, then we can subtract occurrences
of p and add them to z so that we can suppose that x_{2}y_{2}
< p. But since p divides ab, we must have x_{2}y_{2} = 0,
and so either x_{2} = 0 or y_{2} = 0, and so either p divides a
or p divides b.

This result extends to an arbitrary product,
that is, if p | a_{1}a_{2} … a_{n} then p | a_{k}
for some k.

Definition. A set of numbers whose product is
n is known as a **factorisation **of n.

Lemma 2.2 (Fundamental Theorem of Arithmetic). Every positive integer n can be represented uniquely as a product of primes. (Alternatively, every positive integer has a unique prime factorisation).

Proof : Suppose n is not a prime, since
otherwise the result is immediate. Then by definition, n has at least one
factor d such that 1 < d < n. If we choose the smallest such d, call it p_{1},
which exists by the well-ordering principle, then d must be prime, otherwise it
would have a divisor q such that 1 < q < d < n and since q | d and d |
n, we have q | n, a contradiction of our choice of d. Now, n = p_{1}n_{1}
for some n_{1}, and either n_{1} is prime or similarly n_{1}
= p_{2}n_{2} for some prime p_{2} and cofactor n_{2}.
The decreasing sequence n > n_{1} > n_{2} … > 1 cannot
continue forever by the well-ordering principle, and so stops at step k with n_{k}_{-1} being a prime, p_{k}. Then
we have n = p_{1}p_{2}…p_{k}. Basically, the argument
is that if n = ab, then either a and b are both prime, or can be similarly
represented as a product of a pair of smaller integers. If we continue to break
down every composite factor we come across in this way, we eventually reach a
product of primes since we cannot keep finding smaller and smaller factors
forever.

Uniqueness is guaranteed by Lemma 2.1: suppose
there is an integer with two distinct prime factorisations p_{1}p_{2}…p_{r}
and q_{1}q_{2}…q_{s}. Now pick a prime from the left
hand side. Lemma 2.1 demands that this prime divides one of the primes on the
right hand side. But this can only happen if the primes are identical. We can
then cancel out this prime from either side. Suppose without loss that r <
s. Then by repeating the previous step, we would eventually reach 1 = q_{r+1}q_{r+2}…q_{s},
which is absurd, so r = s and the two factorisations are identical.

This result is of immense importance: it identifies the primes as being the fundamental building blocks for all integers, and allows many important properties of integers to be extrapolated from those of the primes.

Lemma 2.3. The number of primes is infinite.

Proof : Suppose not, and let P be the product of all primes. The number P+1 is therefore composite but cannot be expressed as a product of primes, contrary to the Fundamental Theorem of Arithmetic.

Primes are the building blocks of the integers, and it would therefore perhaps be reasonable to expect them to behave appropriately, for instance, they should be easy to find, be evenly spread, obey lots of rules and even perhaps be defined by some formula. Well, yes and no. Primes are easy to find and obey lots of rules, but don’t ever try to pin them down too exactly, or they will fight back.

The Sieve of Eratosthenes.

Starting from 1, it is quickly apparent that 2
and 3 are primes: there simply isn't enough room to manoeuvre down there. But
every other even number, being divisible by 2, must be composite, and every
other number divisible by 3 is also composite, so we are quickly narrowing the
possibilities. The Sieve of Eratosthenes is a simple mechanism which uses this
concept for finding small primes. First, list all the numbers (greater than 1)
up to some limit n. Leave 2 alone, but score out every 2^{nd} number
following. Now for each succeeding survivor p, leave the first occurrence alone
but score out every other p-th number. Repeat this until every survivor has
been considered. The numbers not scored out are the primes less than or equal
to n.

This mechanism is useful for finding the first few primes, but is unsuitable over a large range. However, is does demonstrate that there are patterns of divisibility, of which other examples will be given later. We are more interested at present in finding convenient tests of primality, in particular, ones that can be converted into computer programs.

Trial Division.

A composite number n will always be divisible by a prime p such that p £ Ön. Therefore a simple test of primality is to divide each prime up to this limit into n. If the remainder is ever 0, then n is not a prime. This test is known as Trial Division (up to the square root of n) and is basically an alternative formulation of the Sieve of Eratosthenes.

Full trial division is effective for small numbers, but eventually becomes too time-consuming. However, trial division up to a reasonable limit (which depends on the situation) is used to remove most large numbers from consideration as primes. For those that survive, other methods come into force, but we'll need to develop some additional theory.

Let us first introduce the theory of congruences into the theory of primes.

Lemma 2.4 (Fermat's Little Theorem). If p is a
prime and a is relatively prime to p, then a^{p}^{-1} º
1 (mod p).

Proof : Consider the first p - 1 positive multiples of a : a, 2a, 3a, … ,
(p - 1)a. Suppose that ra º sa (mod p). Then we have r º s (mod p) by Lemma 1.9, and so the p - 1 multiples of a above are distinct and
non-zero. By the pigeon-hole principle, each must be congruent to 1, 2, 3, ...,
p - 1 in some order. Multiplying all
these congruences together, we have a*2a*3a*...*(p - 1)a º 1*2*3*...*^{.}(p
- 1) (mod p), so a^{p}^{-1}(p -
1)! º (p -
1)! (mod p). We can divide both sides by (p -
1)!, again by Lemma 1.9, to complete the proof.

Definition : A **pseudoprimality test** is
a test that all primes are known to pass, but which cannot guarantee primality.
A **pseudoprime** is a composite integer that satisfies a pseudoprimality
test. A **probable prime** is an integer that has passed at least one
pseudoprimality test and for which there is no special reason to believe that
it is not prime.

Fermat's Little Theorem can be used as a quick
pseudoprimality test to filter out all but a few composites from consideration
as primes. For instance, if p is odd, we can take a = 2, so if 2^{p}^{-1} ¹
1 (mod p) then p cannot be a prime. On the other hand, just because 2^{p}^{-1} º
1 (mod p), we cannot presume that p is prime. For instance, 341 = 11*31, but
341 satisfies the condition. Composite numbers that satisfy the condition in
Fermat's Little Theorem are called pseudoprimes to the base a. There are even
some composites that are pseudoprime to every base. These are known as

Note : there are other types of pseudoprime, associated with different tests, as we shall see.

Fermat's Little Theorem is of immense use throughout number theory. A particular advantage is that it can be generalised to an arbitrary modulus. First we need a definition.

Definition : For any positive integer, the Euler phi-function j(n) is the number of positive integers less than or equal to n that are relatively prime to n, i.e.

j(n) = {m £ n : gcd(m, n) = 1}

The definition ensures that j(1) = 1. If n is a prime, then every integer less than n is relatively prime to n, so we have j(n) = n - 1. On the other hand, if n is composite, then there are at least two integers less than n which are not relatively prime to n, and so j(n) £ n - 2. This provides the following characterisation of primes :

Lemma 2.5. j(n) = n - 1 if and only if n is a prime.

Lemma 2.6. If p is a prime, then j(p^{k}) = p^{k} - p^{k}^{- 1} = p^{k} (1 -
(1/p)).

Proof : It is obvious that gcd(n, p^{k})
= 1 if and only if p doesn't divide n. There are p^{k}^{- 1} integers between 1 and p^{k}
divisible by p, i.e. p, 2p, 3p, … , p^{k}^{- 1}p, and so p^{k} -
p^{k}^{- 1} integers
not divisible by p. Hence result.

Lemma 2.7. j(mn) = j(m)j(n) whenever gcd(m, n) = 1 (i.e. j is a multiplicative arithmetic function).

Proof : Consider an m by n grid. We use the fact that gcd (m, km + r) = gcd(m, r) using Lemma 1.7. It is then obvious that for each of the values of r between 1 and m such that gcd(m, r) = 1, we have gcd(m, km + r) = 1, for k < n, so there are j(m) columns of the grid that are relatively prime to m. These intersect with j(n) rows of the grid which are relatively prime to n, making a total of j(m)j(n) positions that are relatively prime to both m and n, and hence to their product mn by Lemma 1.5(i).

Lemma 2.8. The previous two results automatically provide the following :

j(n) = n*

Lemma 2.9. If n > 2 then 2 | j(n) (that is, j(n) is even).

Proof : First suppose n = 2^{k} for
some k > 1. Then j(2^{k}) =
2^{k} - 2^{k}^{-1} = 2^{k}^{-1}, which is even. Now suppose n is not
a power of 2. Then n is divisible by some odd prime p, that is, n = p^{k}m
for some k > 0 and gcd(p^{k}, m) = 1. Then j(n) = j(p^{k}m)
= j(p^{k})j(m) = p^{k}^{-1}(p-1)j(m). Since 2 | p - 1, we have 2 | j(n).

Lemma 2.10. (A generalisation of Lemma 3.4). j(mn) = j(m)j(n).(d/j(d)) where d = gcd(m, n).

Proof : Use Lemma 2.8.

We are just about in a position to give Euler's generalisation of Fermat's Little Theorem. We need one more simple result.

Lemma 2.11. Let n > 1. If a_{1}, a_{2},
… , aj _{(n)} are the j(n) positive integers less than n that are
relatively prime to n, and a is any number that is also relatively prime to n
(i.e. gcd(a, n) = 1) then the numbers aa_{1}, aa_{2}, … , aaj _{(n)} are congruent modulo n to
the a_{1}, a_{2}, … , aj
_{(n)}.

Proof : No two of aa_{1}, aa_{2},
… , aaj _{(n)} are congruent to
each other modulo n by Lemma 1.9. Also, Lemma 1.5(i) (again) implies that
gcd(aa_{i}, n) = 1 for all i. By Lemma 1.10, for each i, we have aa_{i}
º a_{j} (mod n) for some j.
Hence result.

Lemma 2.12 (Euler's Theorem). If n is a positive
integer and gcd(a, n) = 1 then aj ^{(n)}
º 1 (mod n)

Proof : Let a_{1}, a_{2}, … ,
aj _{(n)} be as in Lemma 2.11,
so that they are congruence modulo n to aa_{1}, aa_{2}, … , aaj _{(n)}. Multiplying all these
congruences together, we have aa_{1}*aa_{2}*…*aaj _{(n)} º a_{1}*a_{2}*…*aj
_{(n)} (mod n), so aj ^{(n)}.(a_{1}*a_{2}*…*aj _{(n)}) º a_{1}*a_{2}*…*aj
_{(n)} (mod n). We divide both
sides by the product of the a_{i} to complete the proof.

Definition. Let n > 1 and gcd (a, n) = 1.
Then the **order** of a modulo n is the smallest positive integer k such
that a^{k} º 1 mod n.

For each suitable n and a, the order of a is
guaranteed to exist by Euler's Theorem. However, it is not always equal to j(n), e.g. 2^{3} º 1 (mod 7). Fortunately, even in these
cases, we can find useful restrictions.

Lemma 2.13. With n and a as above, and k the order of a modulo n, we have :

- a
^{x}º a^{y}(mod n) if and only if x º y (mod k) - a
^{x}º 1 (mod n) if and only if k | x. - k | j(n)
- If
h > 0 then a
^{h}has order k/gcd(h, k) modulo n.

Proof of (i): If a^{x} º a^{y} (mod n) then a^{x}^{-y} º
1 (mod n). Now x-y = qk + r for some 0 £ r < k, and so 1 º a^{x}^{-y}
º a^{qk+r} º a^{r} (mod n). If r > 0, this
contradicts definition of k, so we have r = 0, i.e. x º y (mod k). The converse is similarly straightforward.

Proof of (ii) : Take y = k in (i). Then x º 0 (mod k), i.e. k | x.

Proof of (iii) : Take x = j(n) in (ii).

Proof of (iv): Let d = gcd(h, k). Then h = h'd
and k = k'd for some h' and k', such that gcd(h', k') = 1. Now (a^{h})^{k'}
º a^{h'dk'} º (a^{k})^{h'} º 1 (mod n). Let r be the order of a^{h}
modulo n. Then we have r | k'. Also, since a^{hr} º 1 (mod n), k | hr, that is, k'd | h'dr, and
so k' | h'r. Since gcd(h', k') = 1, we must have k' | r. Hence r = k' = k/d =
k/gcd(h, k) as required.

Definition : Given a and n as above and k the
order of a modulo n, if k = j(n), then
a is said to be a **primitive root** of n.

For composite numbers, the existence of a primitive root is the exception rather than the rule. However, for primes, and certain other numbers, we can guarantee existence.

Lemma 2.14. If n is a positive integer and
gcd(a, n) = 1, let a_{1}, a_{2}, … , aj_{(n)} be the j(n)
positive integers less than n that are relatively prime to n. If a is a
primitive root of n then the powers a, a^{2}, … , aj^{(n)} are congruent modulo n to the
a_{i} in some order.

Proof : Since gcd(a, n) = 1, gcd(a^{k},
n) = 1 for all k, so each a^{k} must be congruent modulo n to one of
the a_{i}. By Lemma 2.13(i), the powers a, a^{2}, … , aj^{(n)} are incongruent to each
other, so there must be a 1-to-1 correspondence between the a_{i} and
the a^{j}.

Lemma 2.15. If n has a primitive root, then it has exactly j(j(n)) primitive roots.

Proof : Let a be a primitive root of n. Then
any other primitive root must be in the set a, a^{2}, … , aj^{(n)} by Lemma 2.14. Suppose a^{k}
is a primitive root for some k £ j(n). If d = gcd(k, j(n)) then (a^{k})^{h} º 1 (mod n) for h = j(n)
/ d by Lemma 2.13(iv). This contradicts the fact that a^{k} is a
primitive root unless d = 1. The number of k for which gcd(k, j(n)) = 1 is j(j(n)). Hence result.

In order to prove that primes always have primitive roots, we need the following conveniently concise result, often called Gauss' Lemma.

Lemma 2.16. If n is a positive integer, then n
= S _{d | n} j(d), the sum over all positive divisors d of
n.

Proof : We can partition the integers from 1
to n into the union of the sets A(d), where A(d) = {m : gcd(m, n) = d}. Now
gcd(m, n) = d if and only if gcd(m/d, n/d) = 1 by Lemma 1.4, and so A(d)
consists precisely of those numbers between 1 and n/d which are relatively
prime to n/d, i.e. j(n/d). Since each
of the integers 1 to n lies in exactly one of the A(d), we must have n = S_{ }_{d | n} j(n/d). As d runs through all the divisors of
n, so does n/d. Hence result.

We need one last lemma before the main result in this section. I shall present it without proof to conserve space, and hope that those interested enough will seek it elsewhere.

Lemma 2.17. If p is a prime and d | p - 1, then the congruence x^{d} º 1 (mod p) has exactly d solutions.

Now we can finish, as follows :

Lemma 2.18. If p is a prime, then there are exactly j(p - 1) primitive roots of p.

Proof : We can partition the integers from 1
to n into the union of sets the B(d), where B(d) = {m : the order of m modulo p
is d}. Let y(d) = |B(d)|. Since d | p - 1, we have p -
1 = S _{d | p}_{-1} y(d).
Now Lemma 2.16 gives p - 1 = S _{d | p}_{-1} j(d),
and so we have S _{d | p}_{-1} y(d)
= S _{d | p}_{-1} j(d),
call this equation 1. We will show that y(d)
£ j(d)
for each divisor d of p - 1, since
equation 1 will then guarantee equality. The result will follow immediately by
considering d = p - 1.

If y(d)
= 0, then the condition holds, so let us suppose y(d)
> 0, and let a be an integer of order d. Then the d integers a, a^{2},
… , a^{d} are incongruent modulo p by Lemma 2.13(i), and each satisfies
the congruence x^{d} º 1 (mod
p). By Lemma 2.17, there are no other solutions of this congruence, and so any
integer of order d must be congruent to one of a, a^{2}, … , a^{d}.
By Lemma 2.13(iv), only j(d) of these
powers have order d. Hence y(d) = j(d), as required.

Note that the proof gives us more than we initially needed, in that it tells us that the number of integers between 1 and p - 1 which have order d is j(d).

We could go further, producing results that indicate whether an arbitrary number has primitive roots or not. I will content myself with stating the summarised position.

Lemma 2.19. An integer n > 1 has a
primitive root if and only if n = 2, 4, p^{k} or 2p^{k}, where
p is an odd prime.

Now that we have established the concept of primes, in Section 3 we investigate how frequently they occur.