Divisibility and Greatest Common Divisors

Math 304: Number Theory - Spring 2026

This notebook explores the fundamental concepts of divisibility and greatest common divisors in the integers.

1. Divisibility

Definition (Formal)

Let $n$ and $m$ be integers with $n \neq 0$. We say that $n$ divides $m$, written $n \mid m$, if there exists an integer $k$ such that

$$m = nk$$

We also say that $n$ is a divisor of $m$, or that $m$ is a multiple of $n$, or that $m$ is divisible by $n$.

If $n$ does not divide $m$, we write $n \nmid m$.

Definition (Informal)

Informally, $n$ divides $m$ means that when you divide $m$ by $n$, you get an integer with no remainder. In other words, $m$ can be evenly split into groups of size $n$.

Examples

  1. $3 \mid 12$ because $12 = 3 \cdot 4$
  2. $5 \mid 35$ because $35 = 5 \cdot 7$
  3. $7 \nmid 30$ because there is no integer $k$ such that $30 = 7k$ (we have $30 = 7 \cdot 4 + 2$)
  4. $1 \mid n$ for any integer $n$ because $n = 1 \cdot n$
  5. $n \mid 0$ for any nonzero integer $n$ because $0 = n \cdot 0$
  6. $(-3) \mid 15$ because $15 = (-3) \cdot (-5)$

Testing Divisibility with SageMath

We can check divisibility in SageMath using the modulo operator % or the divides() method:

Division in the Integers

If $a, b$ are integers with $b \neq 0$, there are unique integers $q, r$ such that:

  1. $a = bq + r$
  2. $0 \leq r < |b|$

The $q$ is called the quotient of $a$ by $b$ (in SageMath: a // b), and $r$ is the remainder of $a$ divided by $b$. The remainder is also written as $a \mod b$ (in SageMath: a % b).

Examples

  1. $10 = 3 \cdot 3 + 1$. Dividing $10$ by $3$ gives quotient $3$ and remainder $1$.
  2. $-10 = (-3) \cdot 4 + 2$. Dividing $-10$ by $4$ gives quotient $-3$ and remainder $2$.
  3. $25 = 7 \cdot 3 + 4$. Dividing $25$ by $7$ gives quotient $3$ and remainder $4$.

The following lemma is mostly an exercise in playing with the definitions given so far.

Lemma

Let $a, b$ be integers such that $b \neq 0$. Show that $a \mid b$ if and only if $b \mod a = 0$.

Proof: Suppose $a \mid b$. Then, by definition, there exists an integer $k$ such that $b = ak = ak + 0$. This implies $b \mod a = 0$. Conversely, suppose $b \mod a = 0$. Then $b = a \cdot q + 0$ for some integer $q$, which implies $a \mid b$. □

From a coding point of view, this lemma says that a.divides(b) is the same thing as b%a == 0.

Properties of Divisibility

Let $a, b, c$ be integers. Then:

  1. Transitivity: If $a \mid b$ and $b \mid c$, then $a \mid c$
  2. Linear combination: If $a \mid b$ and $a \mid c$, then $a \mid (bx + cy)$ for any integers $x, y$
  3. Reflexivity: $a \mid a$ for any nonzero integer $a$
  4. If $a \mid b$ and $b \neq 0$, then $|a| \leq |b|$

2. Greatest Common Divisor (GCD)

Definition

Let $a$ and $b$ be integers, 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$.

More formally, $d = \gcd(a,b)$ if:

  1. $d \mid a$ and $d \mid b$ (i.e., $d$ is a common divisor)
  2. If $c \mid a$ and $c \mid b$, then $c \mid d$ (i.e., $d$ is divisible by every common divisor)

Equivalently, $d = \gcd(a,b)$ is the largest integer such that $d \mid a$ and $d \mid b$.

GCD of More Than Two Integers

For integers $a_1, a_2, \ldots, a_n$ (not all zero), we define

$$\gcd(a_1, a_2, \ldots, a_n)$$

to be the largest positive integer that divides all of $a_1, a_2, \ldots, a_n$.

Examples

  1. $\gcd(12, 18) = 6$ because the common divisors of 12 and 18 are $\{1, 2, 3, 6\}$, and 6 is the largest.
  1. $\gcd(25, 35) = 5$
  1. $\gcd(17, 19) = 1$ (17 and 19 are relatively prime or coprime)
  1. $\gcd(0, 5) = 5$ because every integer divides 0, so the common divisors of 0 and 5 are exactly the divisors of 5.
  1. $\gcd(12, 18, 24) = 6$
  1. $\gcd(-12, 18) = 6$ (the GCD is always positive)

Computing GCD with SageMath

Properties of GCD

Let $a, b, c$ be integers. Then:

  1. $\gcd(a, b) = \gcd(b, a)$ (commutativity)
  2. $\gcd(a, b) = \gcd(|a|, |b|)$ (GCD depends only on absolute values)
  3. $\gcd(a, 0) = |a|$ for $a \neq 0$
  4. $\gcd(a, 1) = 1$ for any integer $a$
  5. If $d = \gcd(a, b)$, then $\gcd(a/d, b/d) = 1$
  6. $\gcd(ca, cb) = |c| \cdot \gcd(a, b)$ for $c \neq 0$

Relatively Prime Integers

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

Examples:

3. Practice Problems

Use SageMath to solve the following problems: