Introduction to Number Theory
Integers, primes, divisibility, and beyond
Beginner (high-school level)
About This Section
The introduction to number theory studies the basic properties of integers. Building on divisor/multiple relationships, the concept of primes, and the Euclidean algorithm, the section also covers classification of integers by remainder, proof techniques for integer statements, and positional numeral systems, consolidating the foundations of number theory.
Prerequisites
- The four arithmetic operations on natural numbers (elementary-school level)
Table of Contents
1. Properties of Integers
Definition of integers, divisibility, divisors and multiples, greatest common divisor and least common multiple.
- What integers are and how numbers are classified
- Divisibility, divisors, and multiples
- Greatest common divisor (GCD) and least common multiple (LCM)
2. Primes and Prime Factorization
Definition and infinitude of primes, the Fundamental Theorem of Arithmetic, and applications of prime factorization.
- What primes are and the Sieve of Eratosthenes
- Infinitude of primes (Euclid's proof)
- Fundamental Theorem of Arithmetic and applications to cryptography
3. The Euclidean Algorithm
An efficient algorithm for the GCD. The extended Euclidean algorithm and linear Diophantine equations.
- Principle and algorithm of the Euclidean method
- Extended Euclidean algorithm
- Applications to linear Diophantine equations $ax + by = c$
4. Remainders and Classification of Integers
The division algorithm and case analysis by remainder. Classifying by parity or by mod 3.
- The division algorithm (existence and uniqueness of quotient and remainder)
- Arithmetic of even and odd integers
- Applications of residue classification (calendars, check digits)
5. Proof Techniques for Integers
Basic proof techniques for integer statements: direct proof, proof by contradiction, and induction.
- Direct proof and contrapositive
- Proof by contradiction (irrationality of $\sqrt{2}$)
- Mathematical induction and case analysis
6. Positional Numeral Systems
The principle of positional notation. The relationship between binary, hexadecimal, and computers.
- Positional notation and bases
- Conversion among binary, octal, and hexadecimal
- Applications (computer internal representation, color codes)
7. Repeating Decimals and Their Periods
Whether a fraction's decimal expansion terminates or repeats forever.
- Conditions for terminating and repeating decimals
- Converting repeating decimals to fractions
- Period length and multiplicative order
8. The Field of Rational Numbers
The structure of $\mathbb{Q}$, the number system in which the four arithmetic operations are freely available.
- Definition of rational numbers and the equivalence relation
- The field axioms (properties of addition and multiplication)
- Density and the extension to the real number field
Key Theorems
Division Algorithm
For any integer $a$ and positive integer $b$, there exist unique integers $q$ (the quotient) and $r$ (the remainder) satisfying
$$a = bq + r \quad (0 \leq r < b)$$Fundamental Theorem of Arithmetic
Every positive integer $n > 1$ is expressed uniquely as a product of primes (up to order).
$$n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$$Euclid's Theorem
There are infinitely many primes.
Bézout's Identity
For integers $a, b$ with $\gcd(a, b) = d$, there exist integers $x, y$ such that $ax + by = d$.
Applications Accessible at This Level
Check Digits
ISBN (book codes), JAN codes (barcodes), credit card numbers, and similar identifiers carry an extra digit for verification. This digit is computed via modular arithmetic and detects input errors. For ISBN-13, each digit is multiplied alternately by 1 and 3, and the check digit is chosen so that the resulting sum is divisible by 10.
Calendar Calculations
Formulas such as Zeller's congruence compute the day of the week of a given date using arithmetic modulo 7. The question "what day of the week is 100 days from today?" reduces to $100 \bmod 7 = 2$, so the answer is the day two days after today.
Clock Arithmetic
The 12-hour clock is naturally "arithmetic modulo 12". "It is 9 o'clock now; what time is it 15 hours later?" gives $(9 + 15) \bmod 12 = 0$, i.e., 12 o'clock. This is the most familiar example of congruence.
Puzzles and Games
The solvability of Sudoku and classic puzzles such as the river-crossing and water-pouring problems can be analyzed using GCDs and divisibility. For example, measuring 4 liters using 5-liter and 3-liter containers is possible because $\gcd(5, 3) = 1$ divides 4.
Computers and Binary
Computers represent all data internally in binary. Integers, floating-point numbers, characters, images, sound—every kind of data is encoded as a sequence of 0s and 1s. Hexadecimal (e.g., #FF0000 = red) and IP addresses (e.g., 192.168.1.1) are familiar applications of positional numeral systems.
Study Tips
- Understand divisibility: grasp precisely the relation "$a$ divides $b$"
- The importance of primes: understand the fundamental role primes play in number theory
- Algorithmic thinking: learn about computational efficiency through the Euclidean algorithm
- Remainders and case analysis: systematically study properties of integers by classifying them according to their remainders
- Proof techniques: learn the basic methods of proof for integer statements—direct, by contradiction, and by induction
- Numeral systems: study notations other than base 10 and their connection to computers