Number Theory

The Integers

The integers are the chief concern of number theory. For the next several sections, we will discuss properties of the integers.

Integer Division

Theorem. For integers ${a}$ and ${b \neq 0,}$ there exist unique integers ${q}$ and ${r}$ such that

$$a = qb + r$$

with ${0 \leq r \leq \vert b \vert - 1.}$ We denote ${r}$ with the expression ${a~\text{rem}~b}$ and ${q}$ with the expression ${a ~ \text{div} ~ b.}$

In the theorem above, we call ${q}$ the quotient and ${r}$ the remainder. When ${r = 0,}$ there exists a special relation between ${a}$ and ${b.}$ Namely, that ${b}$ is a divisor of ${a}$ (i.e., ${b}$ divides ${a}$). We define this relation explicitly:

Definition. Let ${a}$ and ${b}$ be integers, with ${b \neq 0.}$ We say that ${b}$ divides ${a}$ if there is an integer ${q}$ such that ${a = q \cdot b.}$ If ${b}$ divides ${a,}$ we write ${b~\vert~a.}$ If ${b}$ does not divide ${a,}$ we write ${b \not\vert ~~ a.}$

Extending this definition, an integer that divides both ${a}$ and ${b}$ is called a common divisor or common factor of ${a}$ and ${b.}$

Definition. Given integers ${a,}$ ${b,}$ and ${c,}$ we say that ${c}$ is a common divisor of ${a}$ and ${b}$ if, and only if, ${c ~ \vert ~ a}$ and ${c ~ \vert ~ b.}$