Key Number Theory Concepts

Why This Matters

Number theory forms the mathematical backbone of modern computing and cryptography. In discrete math, you're expected to understand divisibility relationships, modular systems, and the theorems that connect them. These concepts build on each other, from basic divisibility all the way up to the cryptographic applications that secure online transactions.

Don't just memorize definitions and formulas. For each concept, know why it works, how it connects to other ideas, and when you'd apply it. Can you explain why the Euclidean algorithm is efficient? Do you see how Euler's Theorem generalizes Fermat's Little Theorem? Master the underlying logic, and the individual facts will stick.

---

Foundations: Divisibility and Division

These concepts establish the ground rules for how integers relate to each other. Every theorem that follows depends on understanding what it means for one number to divide another.

Divisibility and Division Algorithm

Divisibility has a precise definition: $b$ divides $a$ (written $b \mid a$) if there exists an integer $k$ such that $a = b \cdot k$. For example, $3 \mid 12$ because $12 = 3 \cdot 4$.

The Division Algorithm guarantees that for any integers $a$ and $b$ (with $b > 0$), there exist unique integers $q$ (quotient) and $r$ (remainder) such that:

$a = bq + r \quad \text{where } 0 \leq r < b$

For instance, dividing 17 by 5 gives $17 = 5(3) + 2$, so $q = 3$ and $r = 2$. The uniqueness of $q$ and $r$ is what makes this a theorem, not just long division.

Greatest Common Divisor (GCD) and Euclidean Algorithm

The GCD of two integers is the largest positive integer that divides both of them. It's the foundation for simplifying fractions and solving equations.

The Euclidean Algorithm computes the GCD efficiently by repeatedly applying the division algorithm. The key identity is:

$\gcd(a, b) = \gcd(b, a \bmod b)$

Here's how it works step by step for $\gcd(252, 198)$:

1. $252 = 198(1) + 54$, so $\gcd(252, 198) = \gcd(198, 54)$
2. $198 = 54(3) + 36$, so $\gcd(198, 54) = \gcd(54, 36)$
3. $54 = 36(1) + 18$, so $\gcd(54, 36) = \gcd(36, 18)$
4. $36 = 18(2) + 0$, so $\gcd(36, 18) = 18$

The algorithm terminates when the remainder hits 0. The last nonzero remainder is the GCD.

The Extended Euclidean Algorithm goes further: it finds integers $x$ and $y$ such that $ax + by = \gcd(a, b)$. This is critical for solving Diophantine equations and finding modular inverses.

Least Common Multiple (LCM)

The LCM of two integers is the smallest positive integer divisible by both. Think of it as solving synchronization problems: if one event repeats every 6 days and another every 8 days, they coincide every $\text{lcm}(6, 8) = 24$ days.

The GCD and LCM are connected by this relationship:

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

This means if you know one, you can always compute the other.

---

Prime Numbers: The Building Blocks

Primes are the atoms of number theory. Every integer greater than 1 is either prime or can be broken down into prime factors, and this decomposition is unique.

Prime Numbers and Prime Factorization

A prime number is a natural number greater than 1 whose only positive divisors are 1 and itself. The first several primes are 2, 3, 5, 7, 11, 13, ...

The Fundamental Theorem of Arithmetic states that every integer greater than 1 has a unique prime factorization, up to the ordering of factors. For example, $360 = 2^3 \cdot 3^2 \cdot 5$ and no other combination of primes will produce 360.

Prime factorization also gives you a way to compute GCD and LCM: take the minimum power of each shared prime for GCD, and the maximum power of every prime for LCM. For example, with $12 = 2^2 \cdot 3$ and $18 = 2 \cdot 3^2$:

• $\gcd(12, 18) = 2^1 \cdot 3^1 = 6$
• $\text{lcm}(12, 18) = 2^2 \cdot 3^2 = 36$

Linear Diophantine Equations

A linear Diophantine equation has the form $ax + by = c$, where $a, b, c$ are integers and you need integer solutions for $x$ and $y$.

The existence criterion is clean: solutions exist if and only if $\gcd(a, b)$ divides $c$. For example, $6x + 9y = 12$ has solutions because $\gcd(6, 9) = 3$ and $3 \mid 12$. But $6x + 9y = 11$ has no integer solutions because $3 \nmid 11$.

Once you find one particular solution (using the Extended Euclidean Algorithm), the general solution generates infinitely many solutions parameterized by an integer $t$.

---

Modular Arithmetic: Computing with Remainders

Modular arithmetic transforms infinite integer problems into finite, cyclic systems. This is where number theory meets practical computation.

Modular Arithmetic Basics

The core idea: work with remainders when dividing by a fixed modulus $m$, reducing the infinite integers to a finite set $\{0, 1, \ldots, m-1\}$.

The congruence notation $a \equiv b \pmod{m}$ means $a$ and $b$ have the same remainder when divided by $m$. Equivalently, $m \mid (a - b)$. For example, $17 \equiv 2 \pmod{5}$ because $5 \mid (17 - 2)$.

Clock arithmetic is the classic example: 14:00 and 2:00 are the same on a 12-hour clock because $14 \equiv 2 \pmod{12}$.

Congruences and Their Properties

Congruence modulo $m$ is an equivalence relation, meaning it's reflexive, symmetric, and transitive. This lets you manipulate congruences algebraically, much like equations.

Arithmetic works as expected for addition and multiplication. If $a \equiv b \pmod{m}$, then:

• $a + c \equiv b + c \pmod{m}$
• $a \cdot c \equiv b \cdot c \pmod{m}$

Division is the exception. You can only divide (cancel) both sides by $c$ if $\gcd(c, m) = 1$. For example, $6 \equiv 6 \pmod{6}$ is trivially true, but dividing both sides by 2 gives $3 \equiv 3 \pmod{6}$, which happens to work. However, $4 \equiv 10 \pmod{6}$ is true (both leave remainder 4 mod 6), but dividing by 2 gives $2 \equiv 5 \pmod{6}$, which is false. The safe rule: only cancel $c$ when $\gcd(c, m) = 1$.

---

Power Theorems: Fermat and Euler

These theorems reveal deep structure in modular exponentiation. They're not just theoretical; they power modern cryptography.

Fermat's Little Theorem

Statement: If $p$ is prime and $\gcd(a, p) = 1$, then:

$a^{p-1} \equiv 1 \pmod{p}$

There's also a corollary form that drops the coprimality requirement: for any integer $a$, $a^p \equiv a \pmod{p}$. This version holds even when $p$ divides $a$.

The main use in practice is reducing large exponents. For example, to compute $3^{100} \pmod{7}$: since 7 is prime and $\gcd(3, 7) = 1$, you know $3^6 \equiv 1 \pmod{7}$. Then $3^{100} = 3^{6 \cdot 16 + 4} = (3^6)^{16} \cdot 3^4 \equiv 1^{16} \cdot 81 \equiv 81 \pmod{7}$. And $81 = 7(11) + 4$, so $3^{100} \equiv 4 \pmod{7}$.

Euler's Theorem and Euler's Totient Function

Euler's Theorem generalizes Fermat to any modulus: if $\gcd(a, n) = 1$, then:

$a^{\phi(n)} \equiv 1 \pmod{n}$

The totient function $\phi(n)$ counts the integers from 1 to $n$ that are coprime to $n$. Key formulas:

• For a prime $p$: $\phi(p) = p - 1$
• For a prime power: $\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$
• For coprime integers: $\phi(mn) = \phi(m)\phi(n)$ when $\gcd(m, n) = 1$

These formulas combine to handle any integer via its prime factorization. For example, $\phi(12) = \phi(4)\phi(3) = (4 - 2)(3 - 1) = 2 \cdot 2 = 4$. The four integers from 1 to 12 coprime to 12 are: 1, 5, 7, 11.

---

Systems of Congruences: The Chinese Remainder Theorem

When you need to solve multiple congruences simultaneously, the Chinese Remainder Theorem (CRT) provides the tool.

Chinese Remainder Theorem

Statement: Given pairwise coprime moduli $m_1, m_2, \ldots, m_k$, the system of congruences

$x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2}, \quad \ldots, \quad x \equiv a_k \pmod{m_k}$

has a unique solution modulo $M = m_1 \cdot m_2 \cdots m_k$.

The pairwise coprimality requirement is essential. If two moduli share a common factor, the system might have no solution or might not have a unique one modulo $M$. For example, $x \equiv 1 \pmod{4}$ and $x \equiv 2 \pmod{6}$ has no solution because any number that's 1 mod 4 is odd, but any number that's 2 mod 6 is even.

CRT is powerful because it lets you break a hard problem into easier pieces. To compute something mod 105, you can work mod 3, mod 5, and mod 7 separately (since $105 = 3 \cdot 5 \cdot 7$), then reconstruct the answer. Computer algebra systems use this technique extensively.

---

Quick Reference Table

---

Self-Check Questions

1. What condition must be satisfied for the linear Diophantine equation $ax + by = c$ to have integer solutions, and how does this connect to the Euclidean algorithm?

2. Compare Fermat's Little Theorem and Euler's Theorem: under what conditions does each apply, and how is Fermat's theorem a special case of Euler's?

3. If you need to find $\gcd(252, 198)$, which method would be more efficient: prime factorization or the Euclidean algorithm? Trace through the steps of your chosen method.

4. Why does the Chinese Remainder Theorem require the moduli to be pairwise coprime? What would go wrong if $\gcd(m_1, m_2) > 1$?

5. Given that $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, explain why you can conclude $ac \equiv bd \pmod{m}$ but cannot always conclude $\frac{a}{c} \equiv \frac{b}{d} \pmod{m}$.