If $n\not=0$ and $a$ are integers, we say that $n$ **divides** $a$ (and write $n|a$) if there exists an
$m$ such that $a=nm$. When $n|a$ we also say $n$ is a **divisor** of $a$ and $a$ is a **multiple** of $n$.

A word of caution: The symbol $n|a$ is *not* a fraction,
but a formula. It means that there is a relationship between the two
numbers which is either true or false (2 and 6 have this relationship,
2 and 7 do not). While we are studying number theory we will have no
occasion to mention the rational numbers—we
will, in fact, avoid them. There are several reasons for this. One is
practical: a given fraction has more than one representation (e.g.,
$4/12=5/15$). It is also possible that a number that doesn't look like
an integer is, in fact, an integer (e.g., $45/15$). These ambiguities
can be a real source of confusion. A second reason is theoretical:
the integers can be used to define the other number systems (more on
this in chapter 5), so the integers should be
studied as a self-contained subject before dealing with these other
systems. A third reason is aesthetic:
number theory is the study of the *integers*; it is somehow more
elegant and satisfying to provide proofs that use only number
theoretic results and techniques. (We do not mean to overstate this.
Mathematics is a single discipline, and some of the most beautiful and
elegant proofs bring apparently unrelated parts of mathematics
together to solve a problem. These surprising connections between
different parts of mathematics enhance the whole mathematical
enterprise.)
The following theorem will be very
useful, despite its simplicity.

Theorem 2.2.1 If $n|a$ and $n|b$ then $n|ax+by$ for any $x,y\in \Z$, so in particular $n|(a+b), n|(a-b)$ and $n|ax$.

**Proof.**

Suppose $a=ni$, $b=nj$. Then $ax+by=nix+njy=n(ix+jy)$ which
shows that $n|ax+by$. The second statement contains particular
instances of the first, where in the first case $x=1$, $y=1$, in the
second case $x=1$, $y=- 1$ and in the third case $y=0$.

Corollary 2.2.2 If $n|a$ and $a|b$, then $n|b$.

**Proof.**

Since $a|b$, there is an $x$ such that $b=ax$. Now the result
follows from 2.2.1.

An integer $p>0$ is called **prime** if it has
exactly two positive divisors, namely, $1$ and $p$. If $a>0$ has more
than two positive divisors, we say it is **composite**. It is important, but easy to forget,
that $1$ is not prime (neither is it composite). A prime has exactly
two positive divisors, but $1$ has only one ($1$
itself). Observe that if $a>1$ is composite, then
$a=nm$ where $n,m>1$ (just let $n$ be any positive divisor other than
1 and $a$).

There are many theorems about primes that are amazing (some are
amazingly hard to prove). There are also many questions involving
primes which, though they are easy to state, have resisted all
attempts at proof. A simple one has to do with so-called **twin
primes**, pairs of primes
of the form $p$ and $p+2$ (e.g. 5 & 7, 11 & 13). No one knows
whether there are an infinite number of such pairs, though they occur
as far out as anyone has checked (by computer). There also are some
arguments that make it appear likely that the number of twin primes is
infinite.

## Exercises 2.2

**Ex 2.2.1**
For the given $n$, $a$, show $n|a$ by finding an
$m$ with $a=nm$.

a) $4|20$

b) $5|-25$

c) $-3|9$

d) $-9|-27$

e) $1|23$

f) $-1|17$

g) $-5|0$

h) $75|75$

**Ex 2.2.2**
Prove, directly from the definition of `$|$', that for
any integer $x\not=0$, $x|0$, $1|x$ and $x|x$.

**Ex 2.2.3**
Find all integers $n$ such that $n|(2n+3)$.

**Ex 2.2.4**
Prove that if $m|a$ and $n|b$, then
$mn|ab$.

**Ex 2.2.5**
Show that if $m\ne 0$, then $nm|am$ iff $n|a$.

**Ex 2.2.6**
Prove that if $a|b$, then $|a|\big||b|$.

**Ex 2.2.7**
If $n$ is an integer, let $(n)$ be the set of all
multiples of $n$, i.e., $(n)=\{a:n|a\}$.

a) If $a$,$b$ are in $(n)$ and $x$ and $y$ are any integers, prove $ax+by$ is in $(n)$.

b) If $(n)\subseteq (m)$, prove $m|n$.

c) If $m|n$, prove $(n)\subseteq (m)$.