Number Theory

Theorem 1.1 (Division Algorithm). For any integers $a$ and $b$ with $b > 0$There exist unique Integers $q$ and $r$ such that $a = bq + r$ with $0 \leq r \lt b$.

Proof. Consider the set $S = \\{a - bk : k \in \mathbb{Z},\ a - bk \geq 0\\}$. This set is non-empty (by the Archimedean property, choosing $k$ sufficiently negative). By the well-ordering principle, $S$ has a least element $r = a - bq$. If $r \geq b$Then $r - b = a - (q+1)b \in S$ with $r - b \lt r$Contradicting minimality. So $0 \leq r \lt b$. For uniqueness, if $a = bq_1 + r_1 = bq_2 + r_2$Then $b(q_1 - q_2) = r_2 - r_1$. Since $|r_2 - r_1| \lt b$We must Have $q_1 = q_2$ and $r_1 = r_2$. $\blacksquare$

We write $d \mid a$ (read ”$d$ divides $a$”) if there exists $k \in \mathbb{Z}$ with $a = dk$.

Proposition 1.2. For all $a, b, c \in \mathbb{Z}$:

1. If $a \mid b$ and $b \mid c$Then $a \mid c$.
2. If $a \mid b$ and $a \mid c$Then $a \mid (mb + nc)$ for all $m, n \in \mathbb{Z}$.
3. If $a \mid b$ and $b \neq 0$Then $|a| \leq |b|$.
4. $a \mid 0$ for all $a$But $0 \mid a$ only when $a = 0$.

Proof. (1) $a \mid b$ means $b = ak$ and $b \mid c$ means $c = b\ell = ak\ell$So $a \mid c$. (2) $a \mid b$ means $b = ak$ and $a \mid c$ means $c = a\ell$So $mb + nc = a(mk + n\ell)$. (3) $a \mid b$ means $b = ak$So $|b| = |a| \cdot |k| \geq |a|$. (4) $0 = a \cdot 0$So $a \mid 0$. If $0 \mid a$Then $a = 0 \cdot k = 0$. $\blacksquare$

Problem. Apply the division algorithm to write $-237 = 14q + r$ with $0 \leq r \lt 14$.

Problem. Find all integers $n$ such that $n \equiv 3 \pmod{7}$ and $n \equiv 2 \pmod{5}$.

Theorem 1.3. Let $a, b \in \mathbb{Z}$Not both zero. The greatest common divisor of $a$ and $b$ Exists and is unique.

Proof. The set $D = \\{d \in \mathbb{N} : d \mid a \mathrm{\ and\ } d \mid b\\}"$ is non-empty since $|a| \in D$ (if $a \neq 0$) or $|b| \in D$ (if $b \neq 0$). By the well-ordering principle, $D$ has A least element $g$. We claim $g = \gcd(a, b)$. By definition $g \mid a$ and $g \mid b$. If $c \mid a$ And $c \mid b$Then $c \leq |c| \leq g$ (since $g$ is the least positive common divisor). For Uniqueness: if $g_1$ and $g_2$ are both greatest common divisors, then $g_1 \mid g_2$ and $g_2 \mid g_1$ So $g_1 = g_2$ (since both are positive). $\blacksquare$

Definition. The least common multiple of positive integers $a$ and $b$Written $\mathrm{lcm}(a, b)$Is the smallest positive integer $m$ such that $a \mid m$ and $b \mid m$.

Theorem 1.4 (GCD—LCM Identity). For all positive integers $a$ and $b$:

$\gcd(a, b) \cdot \mathrm{lcm}(a, b) = ab$

Proof. Write $a = \prod_{i=1}^k p_i^{\alpha_i}$ and $b = \prod_{i=1}^k p_i^{\beta_i}$ where $\alpha_i, \beta_i \geq 0$. Then $\gcd(a, b) = \prod_{i=1}^k p_i^{\min(\alpha_i, \beta_i)}$ and $\mathrm{lcm}(a, b) = \prod_{i=1}^k p_i^{\max(\alpha_i, \beta_i)}$. Since $\min(\alpha_i, \beta_i) + \max(\alpha_i, \beta_i) = \alpha_i + \beta_i$ for each $i$We have:

$\gcd(a,b) \cdot \mathrm{lcm}(a,b) = \prod_{i=1}^k p_i^{\alpha_i + \beta_i} = ab \qquad \blacksquare$

Proposition 1.5. For all positive integers $a, b$:

1. $\mathrm{lcm}(a, b) = ab / \gcd(a, b)$.
2. $\gcd(a, \mathrm{lcm}(b, c)) = \mathrm{lcm}(\gcd(a, b), \gcd(a, c))$.

Problem. Compute $\mathrm{lcm}(252, 105)$ and verify the gcd—lcm identity.

• Forgetting the remainder must be non-negative. For negative $a$, the division algorithm still requires $0 \leq r < b$, which may mean $q$ is not simply $a/b$.
• Confusing “divides” with divisibility by zero. $a \mid 0$ is true for all $a \neq 0$, but $0 \mid a$ is false unless $a = 0$ itself.
• Assuming gcd and lcm are defined for negative numbers. The gcd is always taken as positive; $\gcd(a,b) = \gcd(|a|,|b|)$.
• Thinking the gcd-lcm identity works for more than two numbers. For three numbers, $\gcd(a,b,c) \cdot \mathrm{lcm}(a,b,c) \neq abc$ in general.

• Cryptography: RSA encryption relies on the fact that computing $\gcd$ is easy (Euclidean algorithm) but factoring large numbers is hard. The Carmichael function $\lambda(n)$ depends on lcm of prime-power factors.
• Scheduling: The lcm determines when periodic events coincide. If bus A runs every 12 minutes and bus B every 18 minutes, they coincide every $\mathrm{lcm}(12,18) = 36$ minutes.
• Computer arithmetic: The Euclidean algorithm efficiently computes modular inverses used in the extended Euclidean algorithm for RSA key generation.
• Diophantine equations: The linear Diophantine equation $ax + by = c$ has integer solutions iff $\gcd(a,b) \mid c$, and the solutions are parameterised by the lcm-related step size.