Introduction to Number Theory

Introduction to Number Theory What is Number Theory? Number theory is the branch of mathematics that studies the properties of integers and the relationships among them. At its core, number theory asks fundamental questions: What makes a number prime? When can we divide one number evenly by another? How can we solve equations where only whole-number answers count? These questions might seem abstract, but they have profound practical applications. Number theory underlies much of modern cryptography—the mathematical systems that protect your online communications and financial transactions. Understanding these foundational concepts will help you see how abstract mathematics solves real-world problems. Divisibility and Prime Numbers Understanding Divisors To build number theory, we start with the simplest relationship between integers: divisibility. We say that $b$ is a divisor of $a$ (or equivalently, "$a$ is divisible by $b$") when dividing $a$ by $b$ leaves no remainder. In other words, there exists an integer $k$ such that $a = bk$. For example, 3 is a divisor of 12 because $12 = 3 \times 4$. Every integer has at least two divisors: 1 and itself. Prime and Composite Numbers A prime number is an integer greater than one whose only positive divisors are 1 and itself. The first few primes are 2, 3, 5, 7, 11, and 13. Notice that 2 is the only even prime. A composite number is an integer greater than one that has at least one divisor other than 1 and itself. For instance, 12 is composite because it has divisors like 2, 3, 4, and 6 in addition to 1 and 12. The number 1 is special—by definition, it is neither prime nor composite. The Fundamental Theorem of Arithmetic Here's one of the most important results in number theory: every integer greater than one can be written uniquely as a product of prime numbers, up to the order of the factors. What does "uniquely" mean here? It means there's only one way to write a number as a prime product (if you ignore the order). For example: $12 = 2^2 \times 3$ $60 = 2^2 \times 3 \times 5$ $17 = 17$ (17 is already prime) If you tried to write 12 as a product of primes in a different way—say, with different primes or different exponents—you'd fail. This uniqueness is what makes prime factorization so powerful. It means primes are the true "building blocks" of all integers. The Euclidean Algorithm and Greatest Common Divisor Finding the GCD Two integers often share common divisors. For instance, both 12 and 18 are divisible by 1, 2, 3, and 6. The greatest common divisor (GCD) of two numbers is the largest positive integer that divides both of them. In this case, $\gcd(12, 18) = 6$. Finding the GCD by listing all divisors works for small numbers, but becomes tedious for large ones. Fortunately, there's an elegant algorithm called the Euclidean algorithm that computes the GCD efficiently. How the Euclidean Algorithm Works The algorithm is based on a simple observation: if we divide the larger number by the smaller one, the GCD of the original pair equals the GCD of the smaller number and the remainder. Here's the process: Divide the larger number by the smaller, keeping track of the remainder Replace the larger number with the smaller, and the smaller with the remainder Repeat until the remainder is zero The last non-zero remainder is the GCD Example: Find $\gcd(48, 18)$ $$48 = 18 \times 2 + 12$$ $$18 = 12 \times 1 + 6$$ $$12 = 6 \times 2 + 0$$ The last non-zero remainder is 6, so $\gcd(48, 18) = 6$. Why does this work? Each remainder is strictly smaller than the previous one, so the algorithm must terminate. The mathematical insight is that the set of common divisors never changes when we perform this operation, so the GCD is preserved. Coprime Integers Definition and Significance Two integers are called coprime (or relatively prime) when their greatest common divisor equals 1. This means they share no common divisors except 1. For example: 8 and 15 are coprime because $\gcd(8, 15) = 1$ 12 and 18 are not coprime because $\gcd(12, 18) = 6$ Why does this matter? Coprimality is a crucial concept in number theory because it describes pairs of numbers that are "independent" in a certain sense. Many theorems in number theory, including Euler's Theorem that we'll see later, require integers to be coprime. Modular Arithmetic The Congruence Relation Modular arithmetic is a system where we work with remainders instead of full values. We say that two integers $a$ and $b$ are congruent modulo $m$ when their difference $a - b$ is divisible by $m$. We write this as: $$a \equiv b \pmod{m}$$ For example: $17 \equiv 5 \pmod{12}$ because $17 - 5 = 12$, which is divisible by 12 $23 \equiv 3 \pmod{10}$ because $23 - 3 = 20 = 10 \times 2$ Think of it this way: $a \equiv b \pmod{m}$ means that $a$ and $b$ have the same remainder when divided by $m$. Both 17 and 5 leave remainder 5 when divided by 12. Arithmetic with Congruences One of the elegant features of modular arithmetic is that congruences behave like equations. You can add, subtract, and multiply both sides: If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then $a + c \equiv b + d \pmod{m}$ If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then $ac \equiv bd \pmod{m}$ This means you can do arithmetic modulo $m$ just like regular arithmetic, but numbers "wrap around" when they reach $m$. This wrap-around behavior is why modular arithmetic is sometimes described using a clock analogy: on a 12-hour clock, adding 3 hours to 10 o'clock gives 1 o'clock (because $10 + 3 \equiv 1 \pmod{12}$). Fermat's Little Theorem The Theorem Fermat's Little Theorem is a powerful tool for computing large powers modulo a prime. It states: If $p$ is a prime number and $a$ is an integer not divisible by $p$, then: $$a^{p-1} \equiv 1 \pmod{p}$$ Let's test this with a concrete example. Take $p = 7$ and $a = 3$: $$3^6 = 729 = 7 \times 104 + 1$$ So $3^6 \equiv 1 \pmod{7}$, confirming the theorem since $6 = 7 - 1$. Why This Matters Fermat's Little Theorem is incredibly useful when you need to compute something like $a^{1000000} \pmod{p}$. Rather than multiplying $a$ by itself a million times, you can use the theorem to reduce the exponent. For instance, if you want $3^{100} \pmod{7}$, you can write: $$3^{100} = 3^{6 \times 16 + 4} = (3^6)^{16} \times 3^4 \equiv 1^{16} \times 81 \equiv 81 \equiv 4 \pmod{7}$$ This dramatic reduction in computation is why the theorem has applications in cryptography and primality testing. Euler's Theorem Euler's Totient Function Before stating Euler's Theorem, we need to introduce a new function. Euler's totient function $\varphi(n)$ counts the number of positive integers less than $n$ that are coprime to $n$. For example: $\varphi(6) = 2$ because only 1 and 5 are coprime to 6 (since $\gcd(1,6) = 1$ and $\gcd(5,6) = 1$) $\varphi(10) = 4$ because 1, 3, 7, and 9 are all coprime to 10 $\varphi(p) = p - 1$ for any prime $p$ (all numbers from 1 to $p-1$ are coprime to $p$) There's a useful formula: if $n = p1^{a1} \times p2^{a2} \times \cdots \times pk^{ak}$ is the prime factorization of $n$, then: $$\varphi(n) = n \prod{i=1}^{k} \left(1 - \frac{1}{pi}\right)$$ For instance, $\varphi(12) = 12 \times (1 - \frac{1}{2}) \times (1 - \frac{1}{3}) = 12 \times \frac{1}{2} \times \frac{2}{3} = 4$. The Theorem Euler's Theorem generalizes Fermat's Little Theorem to composite moduli: If $a$ and $n$ are coprime (i.e., $\gcd(a,n) = 1$), then: $$a^{\varphi(n)} \equiv 1 \pmod{n}$$ Notice that when $n = p$ is prime, $\varphi(p) = p - 1$, so Euler's Theorem reduces exactly to Fermat's Little Theorem. Euler's Theorem is fundamental to understanding RSA encryption, one of the most important cryptographic systems in use today. Linear Diophantine Equations Definition A linear Diophantine equation is an equation of the form: $$ax + by = c$$ where $a$, $b$, and $c$ are given integers, and we seek integer solutions $(x, y)$. The name comes from Diophantus of Alexandria, an ancient Greek mathematician. Unlike regular linear equations where we allow any real solutions, Diophantine equations have the additional constraint that only integer solutions count. For example, $3x + 5y = 1$ is a linear Diophantine equation. The pair $(x, y) = (2, -1)$ is a solution because $3(2) + 5(-1) = 6 - 5 = 1$. When Solutions Exist Here's a key result: A linear Diophantine equation $ax + by = c$ has integer solutions if and only if $\gcd(a, b)$ divides $c$. Why? Suppose $\gcd(a, b) = d$. Then $a = da'$ and $b = db'$ for some integers $a'$ and $b'$. If $ax + by = c$ has a solution, then $da'x + db'y = c$, so $d(a'x + b'y) = c$. This means $d$ must divide $c$. Conversely, if $d$ divides $c$, say $c = dk$, then the Euclidean algorithm (extended version) can find integers $x$ and $y$ such that $ax + by = d$. Multiplying by $k$ gives $a(kx) + b(ky) = dk = c$. Example: Does $6x + 9y = 5$ have integer solutions? We have $\gcd(6, 9) = 3$. Since 3 does not divide 5, this equation has no integer solutions. (It does have real solutions, but none where both $x$ and $y$ are integers.) The Chinese Remainder Theorem The Problem Imagine you need to solve a system of congruences: $$x \equiv a1 \pmod{m1}$$ $$x \equiv a2 \pmod{m2}$$ $$x \equiv a3 \pmod{m3}$$ Can you find a single value of $x$ that satisfies all of them simultaneously? The answer depends on whether the moduli are coprime. The Theorem The Chinese Remainder Theorem (CRT) states: If $m1, m2, \ldots, mk$ are pairwise coprime (meaning $\gcd(mi, mj) = 1$ for all $i \neq j$), then the system of congruences has a unique solution modulo $M = m1 \times m2 \times \cdots \times mk$. In other words, there exists a unique integer $x$ with $0 \le x < M$ that satisfies all the congruences simultaneously. Example Let's solve: $$x \equiv 2 \pmod{3}$$ $$x \equiv 3 \pmod{5}$$ $$x \equiv 2 \pmod{7}$$ Since 3, 5, and 7 are pairwise coprime, CRT guarantees a unique solution modulo $3 \times 5 \times 7 = 105$. By inspection (or using the full CRT algorithm), we find $x = 23$ works: $23 = 7 \times 3 + 2$, so $23 \equiv 2 \pmod{3}$ ✓ $23 = 4 \times 5 + 3$, so $23 \equiv 3 \pmod{5}$ ✓ $23 = 3 \times 7 + 2$, so $23 \equiv 2 \pmod{7}$ ✓ The CRT is important because it shows that complex modular systems can be broken down into simpler pieces and then reassembled—a principle used heavily in computational number theory and cryptography. Quadratic Residues Definition A quadratic residue modulo $m$ is an integer $a$ for which there exists an integer $x$ such that: $$x^2 \equiv a \pmod{m}$$ In other words, $a$ is a quadratic residue modulo $m$ if it's a perfect square in modular arithmetic. Example: Let's find all quadratic residues modulo 7. We compute $x^2 \pmod{7}$ for $x = 0, 1, 2, 3, 4, 5, 6$: $0^2 \equiv 0 \pmod{7}$ $1^2 \equiv 1 \pmod{7}$ $2^2 \equiv 4 \pmod{7}$ $3^2 \equiv 2 \pmod{7}$ $4^2 \equiv 2 \pmod{7}$ $5^2 \equiv 4 \pmod{7}$ $6^2 \equiv 1 \pmod{7}$ So the quadratic residues modulo 7 are $\{0, 1, 2, 4\}$. Notice that 3, 5, and 6 are not quadratic residues modulo 7. Why It Matters Quadratic residues are central to understanding when certain equations have solutions. They also appear in many algorithms, such as the quadratic sieve for factoring large integers. Additionally, the theory of quadratic residues connects to deep results like the law of quadratic reciprocity, which describes patterns in which primes are residues modulo other primes.