3.1 Divisors

We all know that \(2\) is a divisor or factor7, of \(6\), but that it is NOT a divisor of \(7\). It is tempting to say that this is because \(6/2\) is a whole number but \(7/2\) is not, and if we are working in the world of fractions (or the real numbers or the complex numbers) this would make sense. However the very fact that \(7/2\) is not an integer means that the operation of division is not defined in general for pairs of integers unless we do work in these worlds.

In this course we want to work inside the set of integers without reference to the larger number systems, so we won’t usually be allowed to divide and we therefore try to avoid using arguments involving the concept of division, wherever possible.

This raises the question of how to define a factor or a divisor without referring to division. We do this as follows:

Definition 3.1

We say that an integer \(d\) is a divisor of the integer \(a\) if and only if there is an integer \(b\) such that \(db=a\). We write \(d|a\) as a shorthand for the statement ‘\(d\) is a divisor of \(a\)’, which we are also allowed to phrase as ‘\(d\) divides \(a\)’.

Example 3.2

Since \(2\cdot 3=6\), \(2\) is a divisor of \(6\). On the other hand if we consider the equation \(2b=7\) we see that the left hand side is even and the right hand side is odd so there are no solutions, hence \(2\) is not a divisor of \(7\). We denote this by \(2\ \nmid \ 7\).

The fact that not every integer is a divisor of every other integer is what makes number theory interesting. The question of which integers divide a given integer is of crucial importance as the factorisation of large numbers plays a key role in modern cryptography and secure communications. It can be reduced to the question of finding the prime factorisation of a number. While in general it is hard to do this there is a related problem that is a lot easier to solve, and we will start with that.

Let \(a,b,d\) be integers.

If \(d| a\) and \(d| b\) we say that \(d\) is a common divisor (or common factor) of \(a\) and \(b\); for instance, \(1\) is a common divisor of any pair of integers \(a\) and \(b\).

The greatest common divisor (or highest common factor) of \(a\) and \(b\) is the unique integer \(d\) satisfying

  • \(d| a\) and \(d| b\) (so that \(d\) is a common divisor),
  • If \(c| a\) and \(c| b\) then \(c\le d\) (so that no common divisor exceeds \(d\)).

We denote the greatest common divisor of \(a,b\) by \(\gcd(a,b)\).

Example 3.3

Find the gcd of \(a=30\) and \(b=42\):

The set of divisors of \(30\) is \(X=\{\pm1, \pm 2, \pm 3, \pm 5, \pm 6, \pm 10, \pm 15, \pm 30\}\).

The set of divisors of \(42\) is \(Y=\{\pm1, \pm 2, \pm 3, \pm 6, \pm 7, \pm 14, \pm 21, \pm 42\}\).

The set of common divisors of \(30\) and \(42\) is \(X\cap Y = \{\pm1, \pm 2, \pm 3, \pm 6\}\)

This is fine for relatively small integers such as 30 and 42, but how would we find the greatest common divisor of \(765432\) and \(56789\)?

  1. The words divisor and factor mean the same thing. We will tend to use the word divisor when talking about integers, though we may talk about factors in the context of algebra e.g. \(x+1\) is a factor of \(x^2-1\).↩︎