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 = px1 + x2 and b = py1 + y2. Multiplying, we have ab = p2.x1y1 + px1y2 + px2y1 + x2y2 = pz + x2y2 from some z. If x2y2 is greater than p, then we can subtract occurrences of p and add them to z so that we can suppose that x2y2 < p. But since p divides ab, we must have x2y2 = 0, and so either x2 = 0 or y2 = 0, and so either p divides a or p divides b.

This result extends to an arbitrary product, that is, if p | a1a2 … an then p | ak 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 p1, 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 = p1n1 for some n1, and either n1 is prime or similarly n1 = p2n2 for some prime p2 and cofactor n2. The decreasing sequence n > n1 > n2 … > 1 cannot continue forever by the well-ordering principle, and so stops at step k with nk-1 being a prime, pk. Then we have n = p1p2…pk. 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 p1p2…pr and q1q2…qs. 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 = qr+1qr+2…qs, 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 2nd 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 ap-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 ap-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 2p-1 ¹ 1 (mod p) then p cannot be a prime. On the other hand, just because 2p-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 Carmichael numbers, the smallest of which is 561.

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(pk) = pk - pk- 1 = pk (1 - (1/p)).

Proof : It is obvious that gcd(n, pk) = 1 if and only if p doesn't divide n. There are pk- 1 integers between 1 and pk divisible by p, i.e. p, 2p, 3p, … , pk- 1p, and so pk - pk- 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 = 2k for some k > 1. Then j(2k) = 2k - 2k-1 = 2k-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 = pkm for some k > 0 and gcd(pk, m) = 1. Then j(n) = j(pkm) = j(pk)j(m) = pk-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 a1, a2, … , 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 aa1, aa2, … , aaj (n) are congruent modulo n to the a1, a2, … , aj (n).

Proof : No two of aa1, aa2, … , aaj (n) are congruent to each other modulo n by Lemma 1.9. Also, Lemma 1.5(i) (again) implies that gcd(aai, n) = 1 for all i. By Lemma 1.10, for each i, we have aai º aj (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 a1, a2, … , aj (n) be as in Lemma 2.11, so that they are congruence modulo n to aa1, aa2, … , aaj (n). Multiplying all these congruences together, we have aa1*aa2*…*aaj (n) º a1*a2*…*aj (n) (mod n), so aj (n).(a1*a2*…*aj (n)) º a1*a2*…*aj (n) (mod n). We divide both sides by the product of the ai 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 ak º 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. 23 º 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 :

  1. ax º ay (mod n) if and only if x º y (mod k)
  2. ax º 1 (mod n) if and only if k | x.
  3. k | j(n)
  4. If h > 0 then ah has order k/gcd(h, k) modulo n.

Proof of (i): If ax º ay (mod n) then ax-y º 1 (mod n). Now x-y = qk + r for some 0 £ r < k, and so 1 º ax-y º aqk+r º ar (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 (ah)k' º ah'dk' º (ak)h' º 1 (mod n). Let r be the order of ah modulo n. Then we have r | k'. Also, since ahr º 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 a1, a2, … , 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, a2, … , aj(n) are congruent modulo n to the ai in some order.

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

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, a2, … , aj(n) by Lemma 2.14. Suppose ak is a primitive root for some k £ j(n). If d = gcd(k, j(n)) then (ak)h º 1 (mod n) for h = j(n) / d by Lemma 2.13(iv). This contradicts the fact that ak 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 xd º 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, a2, … , ad are incongruent modulo p by Lemma 2.13(i), and each satisfies the congruence xd º 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, a2, … , ad. 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, pk or 2pk, where p is an odd prime.

 

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