Key Number Theory Concepts

Why This Matters

Number theory forms the mathematical backbone of modern computing and cryptography—and discrete math exams know it. You're being tested on your ability to understand divisibility relationships, modular systems, and the elegant theorems that connect them. These concepts don't exist in isolation; they build on each other, from basic divisibility all the way up to the cryptographic applications that secure your 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? These connections are exactly what FRQ prompts target. 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 definition—a number $a$ is divisible by $b$ if there exists an integer $k$ such that $a = b \cdot k$
• Division algorithm guarantees that for integers $a$ and $b$ (with $b > 0$), unique integers $q$ and $r$ exist where $a = bq + r$ and $0 \leq r < b$
• Divisibility rules provide shortcuts for checking factors without full computation—essential for quick work on timed exams

Greatest Common Divisor (GCD) and Euclidean Algorithm

• GCD is the largest positive integer that divides both numbers without remainder—the foundation for simplifying fractions and solving equations
• Euclidean algorithm computes GCD efficiently by repeatedly applying the division algorithm: $\gcd(a, b) = \gcd(b, a \mod b)$
• Extended Euclidean algorithm finds integers $x$ and $y$ such that $ax + by = \gcd(a, b)$—critical for solving Diophantine equations

Least Common Multiple (LCM)

• LCM is the smallest positive integer divisible by both numbers—think synchronization problems and cycle alignment
• GCD-LCM relationship connects these concepts: $\text{LCM}(a, b) = \frac{|a \cdot b|}{\gcd(a, b)}$
• Applications include scheduling problems, finding common denominators, and any scenario requiring simultaneous divisibility

---

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

• Prime definition—a natural number greater than 1 with no positive divisors other than 1 and itself
• Fundamental Theorem of Arithmetic states every integer greater than 1 has a unique prime factorization, up to ordering of factors
• Prime factorization enables GCD/LCM computation by comparing prime power components—exam questions love this approach

Linear Diophantine Equations

• Form and definition—equations $ax + by = c$ where $a, b, c$ are integers and we seek integer solutions for $x, y$
• Existence criterion is elegant: solutions exist if and only if $\gcd(a, b)$ divides $c$
• General solution builds from one particular solution, generating infinitely many solutions parameterized by integers—connects directly to the Extended Euclidean Algorithm

---

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

• Core concept—work with remainders when dividing by a fixed modulus $m$, reducing infinite integers to a finite set $\{0, 1, ..., m-1\}$
• Congruence notation $a \equiv b \pmod{m}$ means $a$ and $b$ have the same remainder when divided by $m$—equivalently, $m$ divides $(a - b)$
• Applications span cryptography, hash functions, computer science, and clock arithmetic—expect real-world context in exam problems

Congruences and Their Properties

• Equivalence relation properties—congruence is reflexive, symmetric, and transitive, allowing algebraic manipulation
• Arithmetic preservation—if $a \equiv b \pmod{m}$, then $a + c \equiv b + c \pmod{m}$ and $a \cdot c \equiv b \cdot c \pmod{m}$
• Division caveat—you can only divide both sides by $c$ if $\gcd(c, m) = 1$; this trips up many students

---

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}$
• Corollary form—for any integer $a$, we have $a^p \equiv a \pmod{p}$, even when $p$ divides $a$
• Applications include primality testing, reducing large exponents, and RSA cryptography foundations

Euler's Theorem and Euler's Totient Function

• Euler's Theorem generalizes Fermat: if $\gcd(a, n) = 1$, then $a^{\phi(n)} \equiv 1 \pmod{n}$
• Totient function $\phi(n)$ counts integers from 1 to $n$ that are coprime to $n$—for prime $p$, $\phi(p) = p - 1$
• Totient formulas for prime powers: $\phi(p^k) = p^k - p^{k-1}$; for coprimes: $\phi(mn) = \phi(m)\phi(n)$

---

Systems of Congruences: The Chinese Remainder Theorem

When you need to solve multiple congruences simultaneously, CRT provides the key. It's the bridge between local (mod each prime) and global (mod the product) perspectives.

Chinese Remainder Theorem

• Statement—for pairwise coprime moduli $m_1, m_2, ..., m_k$, a system of congruences $x \equiv a_i \pmod{m_i}$ has a unique solution modulo $M = m_1 \cdot m_2 \cdots m_k$
• Coprimality requirement is essential—the moduli must share no common factors for the theorem to guarantee existence and uniqueness
• Applications include simplifying computations by breaking large moduli into smaller coprime pieces, then reconstructing—used extensively in computer algebra systems

---

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}$.