2.5 Integers

We shall prove both directions of the ‘if and only if’ statement at once.

By Definition 2.25, $d\mid a$ is equivalent to $\frac{a}{d}$ being an integer. Let $k=\frac{a}{d}$ be that integer. The equation $k=\frac{a}{d}$ is equivalent to $a=kd$.

Suppose $a$ and $b$ are integers with common divisor $d$, and let $m$ and $n$ be integers.

By Definition 2.25, $\frac{a}{d}$ and $\frac{b}{d}$ are both integers. The product of two integers is an integer, and so $n\times\frac{a}{d}=\frac{na}{d}$ and $m\times\frac{b}{d}=\frac{bm}{d}$ are also integers. The sum of two integers is an integer, and so $\frac{na}{d}+\frac{mb}{d}=\frac{na+mb}{d}$ is also an integer. Hence, by Definition 2.25, $d\mid(ma+nb)$.

Let $a$ and $b$ be integers. Suppose there exist integers $m$ and $n$ such that $ma+nb=1$. Let $d$ be a positive common divisor of $a$ and $b$, so that $\frac{a}{d}$ and $\frac{b}{d}$ are integers. The equation

also holds.

Since $m$, $\frac{a}{d}$, $n$ and $\frac{b}{d}$ are integers, so is the entire left-hand side of the equation. Thus $\tfrac{1}{d}$ must be an integer too, hence $d=1$. Therefore $1$ is the only positive common divisor of $a$ and $b$.

Our strategy is to show that every possible linear combination $na+mb$ is a multiple of some constant, then use the fact that $a$ and $b$ are coprime to deduce that this constant must be 1.

Fix integers $a$ and $b$. For each $m$ and $n$, the expression $na+mb$ is some integer. Because each possible value of $na+mb$ is an integer, there must be a smallest positive one – call it $s$. In other words, there exists integers $m_{0}$ and $n_{0}$ such that

First we prove that every linear combination $ma+nb$ must be divisible by $s$. For a contradiction, assume that some $ma+nb$ is not divisible by $s$. Then dividing $ma+nb$ by $s$ must leave some nonzero remainder. Hence we can write

for some integers $c$ and $r$ with $0<r<s$. [Convince yourself of this.] Then

Therefore $r$ is a linear combination of $a$ and $b$ that is positive and strictly smaller than $s$. This is a contradiction, since $s$ is the smallest of these. So no such $r$ can exist in equation 2.3, thus $ma+nb$ must divisible by $s$.

Second, we know two possible linear combinations:

• •
  ​

  putting $m=1$ and $n=0$ gives us the linear combination $1.a+0.b=a$;

• •
  ​

  putting $m=0$ and $n=1$ gives us the linear combination $0.a+1.b=b$.

Above, we proved that any linear combination must be a multiple of the smallest one $s$. In particular, $a$ and $b$ must be multiples of $s$; that is, $s$ is a common divisor of $a$ and $b$. But $a$ and $b$ are coprime, so $s$ must be $1$. Then equation 2.2 gives the result.

Suppose $p\mid ab$ and $p\nmid a$; we shall show that $p$ must divide $b$. Since $p$ is prime and $p\nmid a$ it follows that $\gcd(a,p)=1$. Thus, by Lemma 2.36, there are integers $m$ and $n$ such that

Multiplying both sides by $b$ gives

But $p\mid ab$ and $p\mid npb$, so $p$ divides the left-hand side of the equation. Therefore it must divide $b$, the right-hand side, by the Linear Combination Lemma (Lemma 2.28).

The same argument can be applied to prove that if $p\mid ab$ and $p\nmid b$ then $p\mid a$. Therefore the proof is complete.

For a contradiction, suppose $a_{1},a_{2},\ldots,a_{k}$ is the shortest list of integers such that $p\mid a_{1}a_{2}\cdots a_{k}$ but $p$ does not divide any of $a_{1},a_{2},\ldots a_{k}$. We know from Lemma 2.41 that $k>2$. [Think about where we use this in the proof.]

Now

and so Lemma 2.41 tells us that $p\mid a_{1}$ or $p\mid(a_{2}\cdots a_{k})$. By assumption, $p\nmid a_{1}$ and so $p\mid(a_{2}\cdots a_{k})$. But $a_{2},a_{3},\ldots,a_{k}$ is a shorter list than $a_{1},a_{2},\ldots,a_{k}$ and so it must be the case that $p$ divides one of $a_{2},a_{3},\ldots,a_{k}$. This contradicts the existence of such a list $a_{1},a_{2},\ldots,a_{k}$.

Our strategy is to prove that $n$ can be written as a product of primes, and then prove that this factorisation is unique.

First, we prove that $n$ can be written as a product of primes. For a contradiction, assume that $n>1$ cannot be written as a product of primes and is the smallest integer with this property. Because such an $n$ cannot be prime itself [think about why], it must have a positive non-prime divisor $d$ strictly greater than $1$ and less than $n$. [Think about why – try listing divisors of $n$.] Thus $n=dk$ for some positive integers $d$ and $k$, both strictly smaller than $n$. Because $d$ and $k$ are smaller than $n$, and because we assumed $n$ was the smallest integer that could not be written as a product of primes, it must be possible to write $d$ and $k$ as a product of primes. But then $n$ is the product of $d$ and $k$, both of which are a product of primes. Hence $n$ must also be a product of primes. Contradiction; no such $n$ can exist.

Now we prove that $p_{1},p_{2},\ldots p_{k}$ are unique up to reordering. For a contradiction, assume that $n>1$ is the smallest integer with two different prime factorisations. That is, there is a different list of primes $q_{1},q_{2},\ldots q_{l}$ such that

Now $p_{1}$ divides $p_{1}p_{2}\cdots p_{k}$, so it must also divide $q_{1}q_{2}\cdots q_{l}$. By Lemma 2.42, this means $p_{1}$ divides some $q_{j}$. But $q_{j}$ is prime and so $p_{1}=q_{j}$. In other words, the same prime appears on both lists. Delete this prime from each list to get two new lists:

[Don’t be confused by the notation in the second list – this is just $q_{1},q_{2},\ldots,q_{l}$ with $q_{j}$ missing.] These lists must be different because we removed the same prime from each. But then

is a positive integer smaller than $n$ that can be written as a product of primes in two different ways. Contradiction, since we assumed $n$ was the smallest such integer.

The strategy here is to start with a finite list of primes and then prove that there must be another one not on the list.

Let $p_{1},p_{2},\ldots,p_{n}$ be a list of $n$ primes. Define $q$ to be the integer $p_{1}p_{2}\cdots p_{n}+1$. Since $q$ is an integer greater than $1$, it is either prime or not. Consider these cases separately.

1. (i)
   ​

   Suppose $q$ is prime. Then it cannot be one of $p_{1},p_{2},\ldots,p_{n}$ because it is greater than each $p_{i}$. [Why?] Thus $q$ is a prime not on the list of $n$ primes.

2. (ii)
   ​

   Suppose $q$ is not prime. The integers $p_{1}p_{2}\cdots p_{n}$ and $q$ are consecutive, and each $p_{i}$ in the list divides $p_{1}p_{2}\cdots p_{n}$, so none of the $p_{i}$ can divide $q$ by 2.30. But, by the Fundamental Theorem of Arithmetic, $q$ must have a prime divisor and so there must be a prime number that is not on the list.