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$. $\qed$

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. $\qed$

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$.

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\}$.