From The Student Room

TSR Wiki > Study Help > Subjects and Revision > Revision Notes > Mathematics > Introduction to Number Theory

---

This page is an introduction to some of the ideas that you might be in an introductory course in Number Theory at university. The material is at about first-year level, and I plan to include a couple of follow-up articles with more advanced material. It might be a good idea to look at the page on Foundations before reading this page, as some of the ideas there are used here.

Contents 1 Prime Numbers 1.1 Divisors and divisibility 1.2 Euclid's algorithm 1.3 Some more results 2 Modular Arithmetic 2.1 The quotient ring

Prime Numbers

We use the symbol Z to denote the set of integers, i.e. the whole numbers, including 0 and negative numbers. These can be thought of as an extension of the natural numbers, where for every natural number n (except 0) we introduce another number -n, which satisfies n + (-n) = 0. We also have the rule that m x (-n) = -(m x n) and (-m) x (-n) = m x n.

When we are multiplying two numbers together we will sometimes put the multiplication symbol in explicitly, as in 10 = 5 x 2. Sometimes we will just use a dot instead, as in 10 = 5.2 and you should remember that a dot means multiplication, not a decimal point. If we are using letters instead of numbers we will normally just miss out the symbol altogether, and write a = bc.

Divisors and divisibility

If m and n are integers, then we say that m divides n (or that n is divisible by m) if there is an integer a ∈ Z such that n = am. We use the notation m|n to mean "m divides n". Notice that every positive integer n has at least two divisors, which are 1 and n. If these are the only divisors of n then we say that n is a prime number. If it has any other divisors then we call it a composite number. A special case is the number 1 -- although its only divisor is itself, it is not counted as a prime number. The reason for this will be explained later.

The first few prime numbers are therefore 2, 3, 5, 7, 11, 13, ... . Sometimes you will see this set of numbers referred to using the notation , although this tends to be quite rare.

The following properties of divisibility are easy to verify, just using the definition of divisibility:

• If a|b and c is any integer, then a|bc.
• If a|b and b|c then a|c.
• If a|b and a|c then a|b+c.

You should check that you understand why each of these statements is true before going any further -- this is to check that you understand the definition of divisibility and can use it in proofs.

The Fundamental Theorem of Arithmetic says that every positive integer can be written uniquely as a product of prime numbers, except for the ordering of the numbers. For example, the number 39 = 3.13, and this is the only way that it can be written as a product of prime numbers. This is why we don't count the number 1 as a prime number - if we did, we would be able to write 39 = 1.3.13, which would be a different way of expressing the number 39 as a product of prime numbers.

We can prove that every natural number can be written as a product of primes quite easily, using proof by contradiction. We suppose that there are numbers which can't be written as a product of primes, and consider the smallest of these numbers, calling it n. Now n can't be prime (or its prime factorisation would just be n) and so it must be composite, so we can write n = ab with a > 1 and b > 1. But then a and b must both be less than n, and therefore they can be written as products of primes, since n is the smallest number which can't be written as a product of primes. But then n = ab can be written as a product of primes, because we know that a and b can. This is a contradiction, and so all numbers can be written as a product of primes.

We can also prove a theorem, due to Euclid, that there are infinitely many prime numbers:

Theorem: There are infinitely many prime numbers.

Proof: If there are only finitely many prime numbers then we can list them, as p₁, p₂, ..., p_k. Now define the number N = p₁p₂...p_k + 1. None of the primes on our list can divide N, since if they did then they would also have to divide 1, which is impossible. But N has at least one prime factor, and therefore there must be a new prime q which wasn't on our list.

As a historical note, we should say that firstly, Euclid wasn't thinking about prime numbers when he wrote his proof - he was thinking about lengths of lines, and was concerned with finding smaller lines which he could use to 'measure' the lengths of longer lines. Secondly, Euclid didn't say that there were infinitely many primes, since he didn't have any concept of infinity. He merely said that given any list of prime numbers, you can find a new one that isn't on the list.

If we have two positive integers a and b then we write gcd(a,b) to mean the greatest common divisor of a and b. This is the largest integer d which divides both a and b. If you know the prime factorisations of a and b then it's easy to work out their greatest common divisor. Simply take all of the prime numbers that occur in both factorisations and multiply them together. If the same prime number p appears more than once in a or b then you see which one it occurs the fewest times in, and multiply that many p 's together.

Euclid's algorithm

If you're working with very large numbers then you probably won't know their prime factorisations. Fortunately there's a relatively quick way to work out gcd(a,b) even when you don't know the prime factors of a or b. It's called Euclid's algorithm, and we'll tell you what it is shortly. A key part of Euclid's algorithm is that for any pair of positive integers m, n with m > n you can find two more positive integers q and r such that m = qn + r, and 0 ≤ r < n. This looks obvious, but in mathematics many 'obvious' statements turn out not to be true, so we should prove it:

Theorem: For any two positive integers m, n with m > n we can find q, r with 0 ≤ r < n such that m = qn + r.

Proof: Let q be the largest integer such that qn ≤ m. Then define r = m - qn, so that m = qn + r. We definitely have r ≥ 0, since qn ≤ m. We must also have r < n, since if not then we would have (q+1)n ≤ m, and we already assumed that q was the largest integer such that qn ≤ m.

Euclid's algorithm works like this. To find gcd(a,b), where we assume that a > b, we follow these steps:

• First we divide b into a and write down the quotient q₁ and the remainder r₁, so that we have a = q₁b + r₁.
• Then we do a second division, with b playing the role of a and r₁ playing the role of b, so we get b = q₂r₁ + r₂.
• Now divide r₂ into r₁, finding r₁ = q₃r₂ + r₃.
• Keep doing these, each time dividing the last remainder into the second-last remainder, getting a new quotient and a new remainder each time. When we finally obtain a remainder that divides the previous remainder exactly, we are done: that final remainder is the greatest common divisor of a and b.

For example, to find the greatest common divisor of 1547 and 560 we do:

• 1547 = 2 x 560 + 427
• 560 = 1 x 427 + 133
• 427 = 3 x 133 + 28
• 133 = 4 x 28 + 21
• 28 = 1 x 21 + 7

We stop here because 7|21. We have finished the algorithm, and we know that gcd(1547, 560) = 7.

Why does Euclid's algorithm work? It relies on simplifying the problem at each stage, until the problem is so simple that we can give the answer just by looking at it. The key point is that when we write a = qb + r, we find that gcd(a,b) = gcd(b,r). To see this, assume that d is any common divisor of a and b, so that we have a = md and b = nd. Then we can write r = a - qb = (m - qn)d, and so d is a divisor of r as well. Similarly, if d is any common divisor of r and b then we can show that it is a divisor of a as well. Therefore the common divisors of a and b are the same as the common divisors of b and r -- in particular, the greatest common divisor is the same in each case. Now since the gcd doesn't change at each stage of the algorithm, then it must still be the same at the last stage. But at the last stage it's easy to see what the greatest common divisor is!

Some more results

We can also prove a very useful result called Bezout's Theorem:

Theorem: For two positive integers m and n, we can find integers h and k such that hm + kn = gcd(m,n).

Proof: Let d be the smallest positive integer that can be written in the form d = hm + kn. We will show that it must divide both m and n. If it doesn't divide m then we can write m = qd + r, with 0 < r < d. But then r = m - qd = m - q(hm + kn) = (1 - hm)m - qkn. This is a number smaller than d which can be written as a multiple of m plus a multiple of n -- but d was the smallest number for which this was true, and so we must have d|m. Similarly we can argue that d|n.

Now suppose that c|m and c|n. Then c must divide d, since d = hm + kn. In particular, gcd(m,n) must divide d, and so gcd(m,n) ≤ d. But d is a common factor of m and n and gcd(m,n) is the highest common factor of m and n -- so we must have d = gcd(m,n).

Using this theorem, we can prove a very important fact about prime numbers:

Theorem: If a and b are positive integers and p is prime, then if p|ab we must have p|a or p|b.

Proof: If p doesn't divide a then gcd(p,a) = 1, so by Bezout's theorem we can find integers h and k so that we can write ha + pk = 1. But then hab + pkb = b, and since p|ab we must have p|hab + pkb, and thus p|b.

In fact we can use mathematical induction on this argument, to deduce that if p|a₁...a_n for integers a₁, ..., a_n then p must divide a_j for at least one value of j.

Modular Arithmetic

Let m be a positive integer. We say that two integers a and b are congruent modulo m if m divides b - a, or equivalently if the difference between b and a is a multiple of m. We write

a ≡ b (mod m)

to mean that a and b are congruent modulo m. For example, we have

26 ≡ 2 (mod 12)

because 26 - 2 = 24, and 24 is a multiple of 12. We can think of congruence as saying that two numbers a and b have the same remainder when divided by m, i.e. a = pm + r and b = qm + r.

Congruence is an equivalence relation, i.e. it is reflexive, symmetric and transitive. The equivalence class of an integer a under congruence modulo m is the set of all integers that differ from a by a multiple of m. If we write [a] for the equivalence class of a, then

[a] = { ..., a - 2n, a - n, a, a + n, a + 2n, ...}

Two fo the most important properties of modular arithmetic are that if a ≡ a' (mod m) and b ≡ b' (mod m), then

(i) a + b ≡ a' + b' (mod m)

(ii) ab ≡ a'b' (mod m)

We can prove these assertions as follows:

(i) We must be able to find integers p, q such that a' = a + pm and b' = b + qm. But then a' + b' = a + b + (p + q)m ≡ a + b (mod m).

(ii) Writing a' = a + pm and b' = b + qm as before, we have a'b' = (a + pm)(b + qm) = ab + m(aq + bp + pqm) ≡ ab (mod m).

These two observations underpin the whole of modular arithmetic.

The quotient ring

We can think of arithmetic modulo m as just being arithmetic on the set {0, 1, 2, ..., m - 1}, where if the result of adding or multiplying two numbers is greater than m - 1 we only pay attention to the remainder after division by m. However, this is a bit unwieldy for doing proofs with.

A better (more formal) way is to write Z/mZ to mean the set of equivalence classes of integers under the equivalence relation "congruence modulo m", i.e.

Z/mZ = { [0], [1], [2], ..., [m - 1] }

Note that m ≡ 0 (mod m), so we do not need to include the equivalence class of m as a separate element of Z/mZ. This is called the 'quotient ring', although we won't find out what the reason for this name is until later. We then define addition and multiplication in Z/mZ by:

[a] + [b] = [a + b]

[a] x [b] = [ab]

Note that these are not the same binary operations as addition and multiplication in the integers. This is why properties (i) and (ii) which we listed above are so important. We need to know that no matter what member of the equivalence classes [a] and [b] we pick to work out [a] + [b] or [a] x [b], we will end up with the same result. This is exactly what properties (i) and (ii) tell us. We can then list some properties of addition and multiplication in Z/mZ:

1. Addition and multiplication are commutative and associative.

2. Multiplication is distributive over addition, i.e. [a] ([b] + [c]) = [a][b] + [a][c].

3. [0] is an identity for +.

4. [1] is an identity for x.

5. For every [a] ∈ Z/mZ, [-a] is an additive inverse.

These properties can easily be proved using our definitions of addition and multiplication given above. For example, to prove property 2 we simply do

[a] ([b] + [c]) = [a][b + c] = [a(b + c)] = [ab + ac] = [ab] + [ac] = [a][b] + [a][c].

One thing that we don't necessarily have in this system is inverses for multiplication - we can't always find a number b such that ab ≡ 1 (mod m). However, if p is a prime then we can prove that every element a of Z/pZ has a multiplicative inverse:

Theorem: If p is prime, then for any a ∈ Z/pZ that is not congruent to 0 we can find b such that ab ≡ 1 (mod p).

Proof: Since gcd(a,p) = 1 we can find h and k such that ha + kp = 1. But then ah = -kp + 1, and so ah ≡ 1 (mod p), and we just choose b = h.

This means that we have cancellation laws for multiplication in Z/pZ. If ab ≡ ac (mod p) then simply multiplying both sides by a^-1 implies that b ≡ c. Similarly, if ab ≡ 0 (mod p) and a is not congruent to 0, then multiplying by a^-1 shows that b ≡ 0.