Number Theory Basics

While often viewed as the purest form of mathematics, number theory—the study of the properties of whole numbers—forms the bedrock of our digital security. It governs the flow of information in modern cryptography, ensures data integrity, and solves fundamental problems in computer science. Understanding its core principles, from the simple idea of divisibility to the elegant system of modular arithmetic, provides you with a powerful lens for both theoretical exploration and practical application.

Divisibility and Prime Numbers

At the heart of number theory is the concept of divisibility. We say an integer $a$ divides an integer $b$, written as $a\mid b$, if there exists an integer $k$ such that $b=a\cdot k$. For example, $3\mid 12$ because $12=3\cdot 4$. If $a$ does not divide $b$, we write $a\nmid b$.

From this springs the most important building blocks of the integers: prime numbers. A prime number is an integer greater than 1 whose only positive divisors are 1 and itself. Numbers greater than 1 that are not prime are called composite. The first few primes are 2, 3, 5, 7, 11, and 13. The number 1 is neither prime nor composite; it is a unit. A cornerstone theorem, the Fundamental Theorem of Arithmetic, states that every integer greater than 1 can be expressed uniquely as a product of prime numbers, up to the order of the factors. This process is called prime factorization. For instance: $$84=2\cdot 2\cdot 3\cdot 7=2^2\cdot 3\cdot 7$$ This unique "prime fingerprint" of a number is a property you will leverage constantly.

Greatest Common Divisor and the Euclidean Algorithm

Given two integers, a fundamental question is: what is the largest integer that divides them both? This is called the greatest common divisor (GCD). For example, the GCD of 54 and 24 is 6. When the GCD of two numbers is 1, we say they are relatively prime or coprime; they share no prime factors.

Finding the GCD by listing all divisors is inefficient. The ancient and remarkably efficient Euclidean Algorithm provides a systematic method. It is based on this principle: if $a=bq+r$, then $\gcd (a,b)=\gcd (b,r)$. We repeatedly apply this division algorithm until the remainder is zero. The last non-zero remainder is the GCD.

Example: Find $\gcd (270,192)$.

1. $270=192\cdot 1+78$ → $\gcd (270,192)=\gcd (192,78)$
2. $192=78\cdot 2+36$ → $\gcd (192,78)=\gcd (78,36)$
3. $78=36\cdot 2+6$ → $\gcd (78,36)=\gcd (36,6)$
4. $36=6\cdot 6+0$ → $\gcd (36,6)=6$

Therefore, $\gcd (270,192)=6$.

Congruences and Modular Arithmetic

Modular arithmetic is a system for integers that considers numbers that wrap around after reaching a certain value—the modulus. It is foundational for cyclic phenomena like clock time. We say $a$ is congruent to $b$ modulo $n$, written $a\equiv b(\mathrm{mod}n)$, if $n$ divides their difference $(a-b)$. Equivalently, $a$ and $b$ leave the same remainder when divided by $n$.

For a fixed modulus $n$, we work within the set $\{0,1,2,...,n-1\}$, the set of possible remainders or residues. Arithmetic operations (addition, subtraction, multiplication) behave much like ordinary arithmetic, but we reduce the result modulo $n$. For example, modulo 12 (like a clock): $$9+5\equiv 14\equiv 2(\mathrm{mod}12)$$ Crucially, division is not always possible. In modular arithmetic, dividing by a number $a$ means multiplying by its modular inverse—an integer $a^{-1}$ such that $a\cdot a^{-1}\equiv 1(\mathrm{mod}n)$. An inverse for $a$ exists only if $\gcd (a,n)=1$ (they are coprime).

Applications in Cryptography and Computer Science

The leap from abstract theory to real-world power is most visible in cryptography. Modern public-key cryptography, like the RSA algorithm, relies entirely on number-theoretic concepts that are easy to state but computationally hard to reverse without a secret key.

The security of RSA rests on two ideas:

1. Prime Factorization is Hard: While multiplying two large primes is trivial for a computer, factoring the resulting product back into its two prime components is, for sufficiently large primes, computationally infeasible with current technology. This trapdoor function (easy one way, hard the other) forms the basis.
2. Modular Exponentiation with Large Moduli: The encryption and decryption processes involve raising numbers to large powers modulo $n$, where $n$ is the product of two secret primes. This operation can be done efficiently using algorithms like exponentiation by squaring, but reversing it without knowing the prime factors of $n$ is equivalent to the factoring problem.

Beyond cryptography, modular arithmetic is essential for check digits in identification numbers (like ISBNs), hash functions in computer science, and generating pseudorandom numbers. The study of congruences also solves classic problems of finding integer solutions to equations (Diophantine equations), with applications in scheduling and resource allocation.

Common Pitfalls

1. Misapplying the Euclidean Algorithm: A frequent error is stopping the Euclidean Algorithm at the first zero remainder without checking if the previous remainder was zero. The GCD is the last non-zero remainder. In our example, stopping at step 4 and taking the remainder 0 would be incorrect; you must take the remainder from the step before it became zero, which is 6.
2. Assuming Division is Always Possible Modulo n: In ordinary arithmetic, you can divide by any non-zero number. In modular arithmetic, you can only "divide" by a number if it has a multiplicative inverse modulo $n$. For instance, trying to solve $4x\equiv 1(\mathrm{mod}8)$ is impossible because $\gcd (4,8)=4\ne 1$, so 4 has no inverse mod 8.
3. Confusing Modulo with Remainder for Negative Numbers: The definition of $a\mathrm{mod}n$ is the remainder $r$ where $0\le r<n$. For a negative number, you must add multiples of $n$ until you land in this range. For example, $-5\mathrm{mod}7$ is not $-5$. You compute: $-5+7=2$, so $-5\equiv 2(\mathrm{mod}7)$.
4. Overlooking the "Uniqueness" in Prime Factorization: The Fundamental Theorem of Arithmetic guarantees uniqueness up to order. Students sometimes think $2\cdot 3\cdot 5$ is a different factorization from $5\cdot 2\cdot 3$. They are considered the same unique factorization, as the order of multiplication does not matter.

Summary

• Number theory studies integers, with core concepts including divisibility, prime numbers, and the unique prime factorization of every integer greater than 1.
• The greatest common divisor (GCD) of two numbers can be efficiently found using the Euclidean Algorithm, and numbers with a GCD of 1 are coprime.
• Modular arithmetic deals with remainders upon division by a modulus $n$. Two numbers are congruent modulo *n* if they leave the same remainder, and arithmetic operations can be performed within this cyclic system.
• Division in modular arithmetic (finding a modular inverse) is only possible when the number and the modulus are coprime.
• These abstract concepts have profound real-world applications, most notably in public-key cryptography (e.g., RSA), where the computational difficulty of factoring large numbers and calculating discrete logarithms secures digital communication.