Integers and Divisibility

Definitions

• Natural numbers: These are $\dots$ 0, 1, 2, 3, 4, 5, $\dots$

  The set of all natural numbers is denoted by $\N$ .

  We sometimes write $\Z_{\ge 1}$ or $\mathbb{P}$ for the set $\{1,2,3,\dots\}$ of natural numbers that are $\ge 1$ .

• Integers: These are $\dots$ , -3, -2, -1, 0, 1, 2, 3, $\dots$

  The set of all integers is denoted by $\Z$ .

• Variables: We use symbols such as $m$ , $n$ , $r$ , $s$ , $t$ to denote integers whose values are variable or unknown; we call these integer variables.

Let $m$ and $n$ be integers. Then we say that $m$ is a factor of $n$ (or a divisor of $n$ ), or that $m$ divides $n$ , if $n = k \cdot m$ for some integer $k$ .

A prime number is a positive integer $n$ which has exactly two positive factors, namely $1$ and $n$ itself.

A rational number is any number $r$ that can be written in the form $\frac{m}{n}$ where $m$ and $n$ are integers and $n > 0$ .

The integer $m$ is called the numerator and the integer $n$ is called the denominator of the rational number $r = \frac{m}{n}$ .

The set of all rational numbers is denoted by $\mathbb{Q}$ .

$5$ , $0$ , $\frac{\phantom{-}2}{-3}$ ($= \frac{-2}{\phantom{-}3}$ ), and $\frac{11}{123}$ are rational numbers.

Every integer $k$ is a rational number (because $k = \frac{k}{1}\,$ ).

Basic properties of integers

The following hold for all integers $k$ , $m$ and $n\,$ :

Associative laws:

Commutative laws:

Identity laws:

Distributive law:

Other properties:

If $k$ is a factor of $m$ , and $m$ is a factor of $n$ , then $k$ is a factor of $n$ .

Proof. If $m = ku$ and $n = mv$ for integers $u$ and $v$ , then $n = mv = (ku)v = k(uv)$ , with $uv \in \Z$ .

Let $m, n$ be integers such that $m>0$ and $n>0$ : If $m$ is a factor of $n$ , and $n$ is a factor of $m$ , then $m = n$ .

Proof. Since $m$ is a factor of $n$ we have $n = mk$ for some integer $k \ge 1$ . Hence $m \le n$ . Similarly, if $n$ is a factor of $m$ then $n \le m$ . Thus $m \le n$ and $n \le m$ , which together imply that $m = n$ .

We often write $m \mid n$ when $m$ is a factor of $n$ .

With this notation, we can summarise properties of the “factor” relation as follows. For all positive integers $m$ and $n$ :

Let $a, b, c \in \Z$ . Prove the following statements.

• $a \mid 0$ for all $a\in \Z$ .
• If $a \mid b$ and $b \mid a$ then $a = \pm b$ .
• If $a \mid b$ and $a \mid c$ then $a \mid (b+c)$ .
• If $a \mid b$ then $ac \mid bc$ .

Is it true that if $a \mid (bc)$ then either $a \mid b$ or $a \mid c$ ?

Warning: Do not confuse the statement (or relation) $a \mid b$ with the number $a/b$ .

Finding all factors of a positive integer

Let $n$ be a positive integer. How do we find all factors of $n$ ?

But first, why would we want to find all factors of $n$ ?

Secure data transmission (e.g. for internet banking) requires methods of encryption that are impervious to interception.

One of the principal methods (called the ‘RSA algorithm’) uses arithmetic based on integers expressible as product of two large prime numbers, and the difficulty of ‘cracking’ messages encrypted using this method relies on the difficulty of factorising large integers (with 300 digits or more). For more discussion see Section 8.4.

For any positive integer $n$ , let Factors$(n)$ denote the set of all (positive) factors of $n$ .

For example, Factors$(90) = \{1,2,3,5,6,9,10,15,18,30,45,90\}$ .

Question: Given $n$ , how do we find Factors$(n)$ ?

Simple algorithm - called FindFactors$(n)$ :

Given the positive integer $n$ as input,

1. Initialise $k = 1$ ;
2. if $k > n$ then stop; otherwise if $k \mid n$ then output $k$ ;
3. Increment $k$ by $1$ (i.e. $k \leftarrow k+1$ ), then go to step 2.

An algorithm is called correct if it terminates and satisfies its specification - that is, if it does what it is expected to do.

This algorithm terminates after $n$ steps, since $k$ is incremented at each iteration.

Correctness in this case means that the algorithm should find all factors of $n$ .

Proof of correctness of FindFactors $(n)$ :

• If $m$ is a factor of $n$ , then the algorithm outputs $m$ when step 2 is executed for the $m$ th time (that is, when $k = m$ ), and
• If $m$ is an output of the algorithm, then by step 2 it must be a factor of $n$ .

These two things ensure that $m$ is an output of the algorithm if and only if $m$ is a factor of $m$ , so the algorithm is correct.

Lemma 2.1 Let $n$ be any positive integer, and also suppose that $n > 1$ . If $k$ is the smallest factor of $n$ with $k > 1$ , then $k$ is prime.

For example, the smallest factor of $15$ is $3$ , which is prime.

Proof (by contradiction).

Let $k$ be the smallest factor of $n$ with $k > 1$ . Suppose, for a contradiction, that $k$ is NOT prime. Then $k$ has some factor $j$ with $1 < j < k$ . But now $j \mid k$ and $k \mid n$ , so $j \mid n$ , and therefore $j$ is a factor of $n$ smaller than $k$ , and with $j > 1$ . This contradicts the definition of $k$ . Hence the supposition that $k$ was not prime is false, which completes the proof.

This theorem is fundamental to the study of integers: Every integer $n > 1$ can be written as a product of prime numbers.

For example, $90 = 2 \cdot 3 \cdot 3 \cdot 5$ and $2016 = 2^5 \cdot 3^2 \cdot 7$ .

We will discuss this theorem again in Section 3.2. There are many ways to prove this. One of them is to prove the correctness of the following ‘constructive’ algorithm:

Given the integer $n > 1$ as input,

1. Initialise $m = n$ ;
2. Find and output the smallest factor $k$ of $m$ with $k > 1$ ;
3. If $k = m$ then stop; otherwise replace $m$ by $\frac{m}{k}$ , and go to step 2.

The algorithm always terminates, since the value of $m$ decreases each time that step (3) is executed, unless $k = m$ .

Next, let the outputs of the algorithm be $k_1, k_2, \dots, k_s$ , and let $m_1, m_2, \dots, m_s$ be the corresponding values taken by $m$ .

By Lemma 2.1 each $k_i$ is prime, since it is the smallest factor of some integer $m_i$ greater than $1$ .

Also $m_1 = n = k_1 \cdot m_2$ , and then $m_2 = k_2 \cdot m_3$ , and so on, until $m_{s-1} = k_{s-1} \cdot m_s$ , and then $m_s = k_s \cdot 1 = k_s$ .

Thus

which gives $n$ as a product of the primes $k_1, k_2, \dots, k_s$ .

Common divisors

Let $m$ and $n$ be positive integers.

A common divisor of $m$ and $n$ is any (positive) integer $k$ that divides both $m$ and $n$ .

The greatest common divisor of $m$ and $n$ is the largest integer $k$ that divides both $m$ and $n$ . It is denoted by $\gcd(m,n)$ .

The greatest common divisor is $\gcd(18,24) = 6$

Lemma 2.2 If $k$ is a common divisor of $m$ and $n$ , then $k$ divides $am + bn$ for all integers $a$ and $b$ .

Proof. Since $k$ divides $m$ and $n$ , we know that $m = kr$ and $n = ks$ for integers $r$ and $s$ . It then follows that

and therefore $k$ divides $am+bn$ . $\Box$

As a corollary, also $k$ divides $am - bn$ for all integers $a$ and $b$ (because we can simply replace $b$ by $-b$ in the above proof).

Does $\gcd( 0, 0 )$ make sense?

Let $m$ and $n$ be integers with $n > 0$ . Then there exist integers $q$ and $r$ such that $m = qn+r$ , with $0 \le r < n$ .

The integers $q$ and $r$ are called the quotient and remainder of $m$ on division by $n$ , respectively.

Note that the remainder $r$ has to be less than $n$ . Also note that $n$ is a factor of $m$ if and only if the remainder $r$ is zero.

Proof Consider all multiples of $n$ in increasing order, namely

Among these, find the largest multiple $qn$ of $n$ with the property that $qn \le m$ , and then take $r = m - qn$ .

Then $r \ge 0$ (because $m \ge qn$ ), and if $r \ge n$ then we have $m - qn = r \ge n$ , and therefore $m \ge n+qn = (q+1)n$ .

But this shows there is a LARGER multiple $(q+1)n$ of $n$ with $(q+1)n \le m$ , and so contradicts the choice of $q.$

Thus $m = qn +r$ , and $0 \le r < n$ , as required.

The Euclidean algorithm

This is a fast algorithm for finding greatest common divisors. It was written down by Euclid in about 300BC, and re-discovered independently in India and China centuries later.

Let the input be positive integers $m$ and $n$ .

The main idea of the algorithm is that if $m = qn + r$ then

Termination of the algorithm is provided by the case $\gcd( m, 0 ) = m$ .

We give the algorithm in detail:

1. If $m < n$ , then set $a = n$ and $b = m$ ; ${}$ or if $m > n$ , then set $a = m$ and $b = n$ ; ${}$ or if $m = n$ , then output $n$ as $\gcd(m,n)$ and stop;

2. Apply the division theorem to find integers $q$ and $r$ such that $a = qb+r$ , with $0 \le r < b$ ;

3. If $r = 0$ then output $b$ as $\gcd(m,n)$ and stop; otherwise re-set $a = b$ and then re-set $b = r$ , and go to step 2.

1. $a = 120$ and $b = 25$ [initialisation]
2. Find $120 = 4 \cdot 25 + 20$ , and re-set $a = 25$ and $b = 20$ ;
3. Find $\phantom{0}25 = 1 \cdot 20 + 5$ , and re-set $a = 20$ and $b = 5$ ;
4. Find $\phantom{0}20 = 4 \cdot 5 + 0$ , output $b = 5$ and stop [since $r = 0$ ].

This algorithm gives $\gcd(120,25) = 5$ .

First, we can observe that the values of $a$ and $b$ decrease each time that step (3) is executed, except when $r = 0,$ and it follows that the algorithm always terminates.

Now suppose the algorithm terminates after $t$ steps. We wish to show that the value output by the algorithm is the greatest common divisor of the integers $a$ and $b$ . The simplest way to show this is to write $a = bq + r$ , where $0 \le r < b$ , and to note that the correctness of the algorithm follows from the correctness, at each iteration, of the statement

Lemma 2.3 Let $a, b$ be positive integers and let $a = bq + r$ where $0 \le r < b$ . Then $\gcd( a, b ) = \gcd( b, r )$ .

Proof. Consider the sets $S_1 = \{ d \in \mathbb{P} : d \mid a \land d \mid b \}$ and $S_2 = \{ d \in \mathbb{P} : d \mid b \land d \mid r \}$ . So $S_1$ is the set of common divisors of $a$ and $b$ , while $S_2$ is the set of common divisors of $b$ and $r$ . We will show that $S_1 = S_2$ , and hence they have the same largest element.

So let $d \in S_1$ . Then $d \mid a$ and $d \mid b$ and so by Lemma 2.2 we have that $d$ is a divisor of $a - bq = r$ . Hence $d \mid b$ and $d \mid r$ and so $d \in S_2$ . Conversely, suppose $d \in S_2$ . Then $d \mid b$ and $d \mid r$ and so $d \mid (bq + r) = a$ . So $d \mid a$ and $d \in S_1$ . It follows that $S_1 = S_2$ . $\Box$

The extended Euclidean algorithm computes not only the integer $d = \gcd( a,b )$ , but also integers $s, t$ such that $d = as + bt$ . These integers are interesting for some applications. These integers can also be computed by “reversing” the calculations in Euclid’s algorithm.

Congruences and modular arithmetic

The set of integers can be partitioned into two subsets:

These are the sets of integers that leave remainder $0$ or $1$ on division by $2$ , respectively, so we can label them as $[0]$ and $[1]$ .

We can write $\,[0] + [0] = [0]$ , $[0] + [1] = [1]$ , $[1] + [0] = [1]$ and $[1] + [1] = [0]$ , to indicate that

• if $m$ is even and $n$ is even then $m+n$ is even,
• if $m$ is even and $n$ is odd then $m+n$ is odd,
• if $m$ is odd and $n$ is even then $m+n$ is odd,
• if $m$ is odd and $n$ is odd then $m+n$ is even.

Similarly, we write $\,[0] \cdot [0] = [0]$ , $[0] \cdot [1] = [0]$ , $[1] \cdot [0] = [0]$ and $[1] \cdot [1] = [1]$ .

Let $m$ be any integer greater than $1$ .

We say that two integers $a$ and $b$ are congruent modulo $m$ , and write $a \equiv b$ (mod $m$ ), if $a$ and $b$ leave the same remainder on division by $m$ .

Similarly, $a \equiv b$ (mod $2$ ) if and only if $a$ and $b$ are both even (leaving remainder $0$ on division by $2$ ) or both odd (leaving remainder $1$ on division by $2$ ).

Generally, $n \equiv 0$ (mod $m$ ) if and only if $n$ is a multiple of $m$ (leaving remainder $0$ on division by $m$ ).

Theorem 2.1 $a \equiv b$ (mod $m$ ) if and only if $a-b$ is a multiple of $m$

Proof: Suppose that division by $m$ gives $a = qm+r$ and $b = sm+t$ , with remainders $r$ and $t$ (both less than $m$ ). Then we have

’Only if’ part: If $a \equiv b$ (mod $m$ ), then by definition, $r = t$ , and so $a-b = (q-s)m$ , which is a multiple of $m$ .

’If’ part: If $a-b$ is a multiple of $m$ , then so is

But $0 \le r < m$ and $0 \le t < m$ , so $-m < r-t < m$ . Since the only multiple of $m$ strictly between $-m$ and $+m$ is $0$ , it follows that $r-t = 0$ , so $r = t$ , and thus $a \equiv b$ (mod $m$ ). $\Box$

Properties of congruence mod $m$

• $a \equiv a$ (mod $m$ ) [reflexive]
• If $a \equiv b$ (mod $m$ ) then $b \equiv a$ (mod $m$ ) [symmetric]
• If $a \equiv b$ (mod $m$ ) and $b \equiv c$ (mod $m$ ) then $a \equiv c$ (mod $m$ ) ${}$ [transitive]

These are easy to prove from the definition of congruence mod $m$ (viz. leaving the same remainder on division by $m$ ).

Let $k$ be any integer greater than $1$ , and let $m$ be any integer.

By the division theorem, we have $m = qk+r$ with $0~\le~r~<~k$ . Then the set of all integers congruent to $m$ mod $k$ is the set of all integers leaving remainder $r$ on division by $k$ , namely

$\ldots, -3k+r, \, -2k+r, \, -k+r, r, \, k+r, \, 2k+r, \, 3k+r, \ldots \$ .

This set is called the congruence class of $m$ mod $k$ , and is denoted by $[m]$ .

Note that $[m]$ contains $m$ (since $m = qk+r$ ). Also $[m] = [r]$ , and more generally, $[m] = [n]$ if and only if $m \equiv n$ (mod $k$ ).

The number of congruence classes mod $k$ is $k$

Let $k$ be any integer greater than $1$ . Then we know that for any integer $m$ , the congruence class $[m]$ consists of all integers leaving the same remainder $r$ as $m$ on division by $k$ , and in particular, $[m] = [r]$ , where $0 \le r < k$ .

It follows that every integer $m$ lies in exactly one of the $k$ congruence classes $[0]$ , $[1]$ , $[2], ~\dots, [k\!-\!1]$ .

Similarly, the ten congruence classes mod $10$ are

The ring of all congruence classes mod $k$

Any integer $n$ contained in the congruence class $[r]$ is called a representative of the class.

The set of all congruence classes mod $k$ is denoted by $\Z_k$ . In other words,

$\Z_k = \{ [0], [1], [2], \dots, [k\!-\! 1]\}$ .

Most books simply write $\Z_k = \{ 0, 1, \dots, k-1 \}$ .

When equipped with addition and multiplication, $\Z_k$ is an example of an algebraic structure known as a ‘ring’, called the ring of integers modulo $k$ , and if $p$ is a prime number, then $\Z_p$ is a field. Prime fields are very useful in constructing error-correcting codes, and in cryptography.

Fix $m \in \N$ and let $a, b, c, d \in \Z$ be such that $a \equiv b \pmod{m}$ and $c \equiv d\pmod{m}$ . Show that

1. $a + c \equiv b + d \pmod{m}$ .
2. $ac \equiv bd \pmod{m}$ .