Divisibility

Definition

An integer $a$ divides an integer $b$ (written $a \mid b$) if there exists an integer $k$ such that: $b = ak$

We say $a$ is a divisor or factor of $b$, and $b$ is a multiple of $a$.

If $a \nmid b$, then $a$ does not divide $b$.

Basic Properties

For all integers $a, b, c$:

1. $a \mid 0$ (every integer divides 0)
2. $1 \mid a$ (1 divides every integer)
3. If $a \mid b$ and $b \mid c$, then $a \mid c$ (transitivity)
4. If $a \mid b$ and $a \mid c$, then $a \mid (b + c)$ and $a \mid (b - c)$
5. If $a \mid b$, then $a \mid bc$ for any integer $c$
6. If $a \mid b$ and $a \mid c$, then $a \mid (mb + nc)$ for any integers $m, n$

For positive integers:

If $a \mid b$ and $b \neq 0$, then $|a| \leq |b|$.

Division Algorithm

For any integers $a$ and $d$ with $d > 0$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that: $a = dq + r \quad \text{where } 0 \leq r < d$

Notation

• $a \div d = q$ (integer division)
• $a \mod d = r$ (remainder)

Examples

• $17 = 5 \times 3 + 2$, so $17 \div 5 = 3$ and $17 \mod 5 = 2$
• $-17 = 5 \times (-4) + 3$, so $-17 \div 5 = -4$ and $-17 \mod 5 = 3$

Greatest Common Divisor (GCD)

The greatest common divisor of $a$ and $b$, written $\gcd(a, b)$ or $(a, b)$, is the largest positive integer that divides both.

Properties

$\gcd(a, b) = \gcd(b, a)$ $\gcd(a, 0) = |a|$ $\gcd(a, b) = \gcd(a - b, b) = \gcd(a \mod b, b)$ $\gcd(a, b) = \gcd(a, b - a)$

Coprime (Relatively Prime)

$a$ and $b$ are coprime if $\gcd(a, b) = 1$.

Euclidean Algorithm

Efficiently computes $\gcd(a, b)$ using repeated division.

Algorithm

gcd(a, b):
    while b ≠ 0:
        r = a mod b
        a = b
        b = r
    return a

Example

$\gcd(252, 105)$ $252 = 105 \times 2 + 42$ $105 = 42 \times 2 + 21$ $42 = 21 \times 2 + 0$

$\gcd(252, 105) = 21$

Time Complexity

$O(\log(\min(a, b)))$ divisions

Extended Euclidean Algorithm

Finds integers $x$ and $y$ such that: $\gcd(a, b) = ax + by$

Bézout's Identity

For any integers $a$ and $b$ (not both zero), there exist integers $x$ and $y$ such that: $\gcd(a, b) = ax + by$

Example

Find $x, y$ such that $\gcd(252, 105) = 252x + 105y$

Working backwards: $21 = 105 - 42 \times 2$ $21 = 105 - (252 - 105 \times 2) \times 2$ $21 = 105 \times 5 - 252 \times 2$ $21 = 252 \times (-2) + 105 \times 5$

So $x = -2$, $y = 5$.

Least Common Multiple (LCM)

The least common multiple of $a$ and $b$, written $\text{lcm}(a, b)$ or $[a, b]$, is the smallest positive integer divisible by both.

Relationship to GCD

$\gcd(a, b) \times \text{lcm}(a, b) = |ab|$

$\text{lcm}(a, b) = \frac{|ab|}{\gcd(a, b)}$

Properties

$\text{lcm}(a, b) = \text{lcm}(b, a)$ $\text{lcm}(a, 1) = |a|$ $\text{lcm}(a, a) = |a|$

Divisibility Rules

Divisor	Rule
2	Last digit is even
3	Sum of digits divisible by 3
4	Last two digits form number divisible by 4
5	Last digit is 0 or 5
6	Divisible by both 2 and 3
8	Last three digits divisible by 8
9	Sum of digits divisible by 9
10	Last digit is 0
11	Alternating sum of digits divisible by 11

Linear Diophantine Equations

Equation of the form: $ax + by = c$

Solvability

Has integer solutions if and only if $\gcd(a, b) \mid c$.

Finding Solutions

1. Find particular solution $(x_0, y_0)$ using extended Euclidean algorithm
2. General solution: $x = x_0 + \frac{b}{d}t, \quad y = y_0 - \frac{a}{d}t$ where $d = \gcd(a, b)$ and $t \in \mathbb{Z}$.