Divisibility and Primes - Core Definitions

Number theory begins with the fundamental concept of divisibility, which describes how integers relate to one another through multiplication. Understanding these relationships forms the foundation for all subsequent developments in the theory of numbers.

DefinitionDivisibility

Let $a, b \in \mathbb{Z}$ with $a \neq 0$ . We say that $a$ divides $b$ , written $a \mid b$ , if there exists an integer $k$ such that $b = ak$ . In this case, we call $a$ a divisor of $b$ , and $b$ a multiple of $a$ . If $a$ does not divide $b$ , we write $a \nmid b$ .

The divisibility relation has several important properties that make it particularly well-behaved. It is reflexive (every integer divides itself), antisymmetric in a certain sense, and transitive. These properties allow us to reason systematically about divisibility.

Remark

Key properties of divisibility:

If $a \mid b$ and $b \mid c$ , then $a \mid c$ (transitivity)
If $a \mid b$ and $a \mid c$ , then $a \mid (bx + cy)$ for any integers $x, y$ (linearity)
If $a \mid b$ and $b \neq 0$ , then $|a| \leq |b|$
$1$ divides every integer, and every integer divides $0$

DefinitionPrime Numbers

An integer $p > 1$ is called prime if its only positive divisors are $1$ and $p$ itself. An integer $n > 1$ that is not prime is called composite. The integer $1$ is considered neither prime nor composite.

Prime numbers are the multiplicative building blocks of all integers, analogous to how atoms form molecules in chemistry. Their seemingly random distribution has fascinated mathematicians for millennia.

ExampleFirst Prime Numbers

The first ten prime numbers are: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$ .

Note that $2$ is the only even prime number. Every other even number $n > 2$ is divisible by $2$ , hence composite. The prime $2$ is therefore unique in its parity.

DefinitionGreatest Common Divisor

Let $a, b \in \mathbb{Z}$ , not both zero. The greatest common divisor of $a$ and $b$ , denoted $\gcd(a, b)$ or $(a, b)$ , is the largest positive integer that divides both $a$ and $b$ .

Two integers $a$ and $b$ are called relatively prime or coprime if $\gcd(a, b) = 1$ .

The Euclidean algorithm provides an efficient method for computing the greatest common divisor, reducing the problem to successively smaller pairs of integers through repeated division with remainder.