1.1: Divisibility and Primality

Last updated
Save as PDF

Page ID: 17655

$Shoup.jpg$
Victor Shoup
Professor (Computer Science) at Courant Institute of Mathematical Sciences (New York University)

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

A central concept in number theory is divisibility.

Consider the integer $\mathbb{Z}=\left \{..., -2, -1, 0, 1, 2, ...\right \}$. For $a, b \in \mathbb{Z}$, we say that $a$ divides $b$ if $az=b$ for some $z \in \mathbb{Z}$. If $a$ divides $b$, we write $a \mid b$, and we may say that $a$ is a divisor of $b$, or that $b$ is a multiple of $a$, or that $b$ is a divisible of $a$. If $a$ does not divide $b$, then we write $a \nmid b$.

We first state some simple facts about divisibility:

Theorem $\PageIndex{1}$

For all $a, b, c \in \mathbb{Z}$, we have

$a \mid a,\ 1 \mid a,$ and $a \mid 0$;
$a \mid 0$ if and only if $a=0$;
$a \mid b$ if and only if $ -a \mid b$ if and only if $ a \mid -b$;
$a \mid b$ and $a \mid c$ implies $ a \mid (b+c)$;
$a \mid b$ and $b \mid c$ implies $a \mid c$.

Proof

These properties can be easily derived from the definition of divisibility, using elementary algebraic properties of the integers. For example, $a \mid a$ because we can write $a \cdot 1= a$; $1 \mid a$ because we can write $1 \cdot a= a$; $a \mid 0$ because we can write $a \cdot 0= 0$. We leave it as an easy exercise for the reader to verify the remaining properties.

$\square$

Theorem $\PageIndex{2}$

For all $a,b \in \mathbb{Z}$, we have $a \mid b$ and $b \mid a$ if and only if $a = \pm b$. In particular, for every $a \in \mathbb{Z}$, we have $a \mid 1$ if and only if $a = \pm 1$.

Proof

Clearly, if $a = \pm b$, then $a \mid b$ and $b \mid a$. So let us assume that $a \mid b$ and $b \mid a$, and prove that $a = \pm b$. If either of $a$ or $b$ are zero, then the other must be zero as well. So assume that neither is zero. By the above observation, $a \mid b$ implies $\left|a\right| \leq \left|b\right|$, and $b \mid a$ implies $\left|b\right| \leq \left|a\right|$; Thus, $\left|a\right| = \left|b\right|$, and so $a = \pm b$. That proves the first statements. The second statement follows from the first by setting $b := 1$, and noting that $1 \mid a$.

$\square$

The product of any two non-zero integers is again non-zero. This implies the usual cancellation law: if $a$, $b$, and $c$ are integers such that $a \neq 0 $ and $ab=ac$, then we must have $b=c$; indeed, $ab=ac$ implies $a(b-c)=0$, and so $a \neq 0 $ implies $b-c=0$, and hence $b=c$.

Primes and Composites

Let $n$ be a positive integer. Trivially, $1$ and $n$ divide $n$. If $n>1$ and no other positive integers besides $1$ and $n$ divide $n$, then we say $n$ is prime. If $n>1$ but $n$ is not prime, then we say that $n$ is composite. The number $1$ is not considered to be either prime or composite. Evidently, $n$ is composite if and only if $n = ab$ for some integers $a,b$ with $1<a<n$ and $1<b<n$. The first few primes are

2, 3, 5, 7, 11, 13, 17, ....

While it is possible to extend the definition of prime and composite to negative integers, we shall not do so in this text: whenever we speak of a prime or composite number, we mean a positive integer.

A basic fact is that every non-zero integer can be expressed as a signed product of primes in an essentially unique way. More precisely:

Theorem $\PageIndex{3}$: fundamental theorem of arithmetic

Every non-zero integer $n$ can be expressed as

\[n = \pm {p_1}^{e_1} \dotsb {p_r}^{e_r}\ ,\]

where $p_1 \, \dotsb \, p_r$ are distinct primes and $e_1 \, \dotsb \, e_r$ are positive integers. Moreover, this expression is unique, up to a reordering of the primes.

Note

Note that if $n = \pm 1$ in the above theorem, then $r = 0$, and the product of zero terms is interpreted (as usual) as 1.

The theorem intuitively says that the primes act as the “building blocks” out of which all non-zero integers can be formed by multiplication (and negation). The reader may be so familiar with this fact that he may feel it is somehow “self evident,” requiring no proof; however, this feeling is simply a delusion, and most of the rest of this section and the next are devoted to developing a proof of this theorem. We shall give a quite leisurely proof, introducing a number of other very important tools and concepts along the way that will be useful later.

proof

To prove Theorem 1.3, we may clearly assume that $n$ is positive, since otherwise, we may multiply $n$ by −1 and reduce to the case where $n$ is positive.

The proof of the existence part of Theorem 1.3 is easy. This amounts to showing that every positive integer $n$ can be expressed as a product (possibly empty) of primes. We may prove this by induction on $n$. If $n = 1$, the statement is true, as n is the product of zero primes. Now let $n > 1$, and assume that every positive integer smaller than n can be expressed as a product of primes. If $n$ is a prime, then the statement is true, as $n$ is the product of one prime. Assume, then, that $n$ is composite, so that there exist $a, b \in \mathbb{Z}$ with $1<a<n$, $1<b<n$, and $n=ab$. By the induction hypothesis, both $a$ and $b$ can be expressed as a product of primes, and so the same holds for $n$.

The uniqueness part of Theorem 1.3 is the hard part(Check the section 2). An essential ingredient in this proof is the following:

Theorem $\PageIndex{4}$: Division with remainder property

Let $a,b \in \mathbb{Z}$ with $b>0$. Then there exist unique $q, e \in \mathbb{Z}$ such that $a = bq + r$ and $0 \leq r < b$.

Proof

Consider the set $S$ of non-negative integers of the form $a-bt$ with $t \in \mathbb{Z}$. This set is clearly non-empty; indeed, if $a \geq 0 $, set $t:=0$, and if $a < 0$, set $t:=a$. Since every non-empty set of non-negative integers contains a minimum, we define $r$ to be the smallest element of $S$. By definition, $r$ is of the form $r=a-bq$ for some $q \in \mathbb{Z}$, and $r \geq 0$. Also, we must have $r<b$, since otherwise, $r-b$ would be an element of $S$ smaller than $r$, contradicting the minimality of $r$; indeed, if $r \geq b$, then we would have $0 \leq r-b=a-b(q+1) $.

That proves the existence of $r$ and $q$. For uniqueness, suppose that $a=bq+r$ and $a=bq'+r'$, where $0 \leq r<b$ and $0 \leq r'<b$. Then subtracting these two equations and rearranging terms, we obtain

\[r'-r=b(q-q').\]

Thus, $r'-r$ is a multiple of $b$; however, $0 leq r <b $ and $0 \leq r'<b$ implies $\left|r'-r\right| < b$; therefore, the only possibility is $r'-r=0$. Moreover, $0=b(q-q')$ and $b \neq 0$ implies $q-q'=0$.

$\square$

Theorem $\PageIndex{4}$ can be visualized as follows:

$clipboard_ee6c52daf271dc61069a884c0b9e51902.png$

Starting with $a$, we subtract (or add, if $a$ is negative) the value $b$ until we end up with a number in the interval $[0,b)$.

Floor and Ceilings

Let us briefly recall the usual floor and ceiling functions, denote $\lfloor . \rfloor$ and $\lceil . \rceil$, respectively. These are functions from $\mathbb{R}$ (the real numbers) to $\mathbb{Z}$. For $x \in \mathbb{R}$, $\lfloor x \rfloor$ is the greatest integer $m \leq x$; equivalently, $\lfloor x \rfloor$ is the unique integer $m$ such that $m \leq x < m+1$, or put another way, such that $x = m+\varepsilon$ for some $\varepsilon \in [0,1)$. Also, $\lceil x \rceil$ is the smallest integer $m \geq x$; equivalently, $\lceil x \rceil$ is the unique integer $m$ such that $m-1 < x \leq m $, or put another way, such that $x = m - \varepsilon$ for some $\varepsilon \in [0,1)$.

The mod operator

Now let $a,b \in \mathbb{Z}$ with $b>0$. If $q$ and $r$ are the unique integers from Theorem 1.4 that satisfy $a=bq+r$ and $0 \leq r<b$, we define

\[(a \bmod b)=a-b \lfloor a/b \rfloor. \]

that is, $a \bmod b$ denotes the remainder in dividing $a$ by $b$. It is clear that $b \mid a$ if and only if $a mod b =0$. Dividing both sides of the equation $a=bq+r$ by $b$, we obtain $a/b=q+r/b$. Since $q \in \mathbb{Z}$ and $r/b \in [0,1)$, we see that $q= \lfloor a/b \rfloor$. Thus,

\[(a \bmod b)=a-b \lfloor a/b \rfloor .\]

One can use this equation to extend the definition of $a \bmod b$ to all integers $a$ and $b$, with $b \neq 0$; that is, for $b<0$, we simply define $a \bmod b$ to be $a-b \lfloor a/b \rfloor$.

Theorem $\PageIndex{4}$ may be generalized so that when dividing an integer $a$ by a positive integer $b$, the remainder is placed in an interval other than $[0,b)$. Let $x$ be any real number, and consider the interval $[x,x+b)$. As the reader may easily verify, this interval contains precisely $b$ integers, namely, $\lceil x \rceil , \dotsc , \lceil x \rceil+b-1$. Applying Theorem 1.4 with $a - \lceil x \rceil $ in place of $a$, we obtain:

Theorem $\PageIndex{5}$

Let $a,b \in \mathbb{Z}$ with $b>0$, and let $x \in \mathbb{R}$. Then there exist unique $q,r \in \mathbb{Z}$ such that $a=bq+r$ and $r \in [x,x+b)$.

EXERCISE 1.1 Let $a,b,d \in \mathbb{Z}$ with $d \neq 0 $. Show that $a \mid b$ if and only if $da \mid db$.

EXERCISE 1.2 Let $n$ be a composite integer. Show that there exists a prime $p$ dividing $n$, with $p \leq n^{1/2}$.

EXERCISE 1.3 Let $m$ be a positive integer. Show that for every real number $x \geq 1$, the number of multiples of $m$ in the interval $[1,x]$ is $\lfloor x/m \rfloor$; in particular, for every interger $n \geq 1$, the number of multiples of $m$ among $1\, \dotsc , n$ is $\lfloor n/m \rfloor $.

EXERCISE 1.4 Let $x \in \mathbb{R}$. Show that $2 \lfloor x \rfloor \leq \lfloor 2x \rfloor \leq 2 \lfloor x \rfloor +1$.

EXERCISE 1.5 Let $x \in \mathbb{R}$ and $n \in \mathbb{Z}$ with $n>0$. Show that $\lfloor \lfloor x \rfloor /n \rfloor = \lfloor x/n \rfloor$; in particular, $\lfloor \lfloor a/b \rfloor /c \rfloor = \lfloor a/bc \rfloor$ for all positive integers $a,b,c$.

EXERCISE 1.6 Let $a,b \in \mathbb{Z}$ with $b<0$. Show that $(a \bmod b) \in (b,0]$.

EXERCISE 1.7 Show that Theorem 1.5 also holds for the interval $(x,x+b]$. Does it hold in general for the intervals $[x,x+b]$ or $(x,x+b)$?