Introductory number theory
The integers can be added, subtracted and multiplied, but not always divided. What can be proved about them when every claim must hold for every integer?
Where you are 8 inside
What this area is about
Number theory studies the integers \mathbb{Z}, and here every fact is proved, not checked on examples. The central ideas are divisibility, remainders and common divisors. From them come working tools, such as the Euclidean algorithm and arithmetic modulo n, and classic results, such as the fact that the primes never run out.
How these fit together
Definitions. Divisibility as a relation: for integers a and b, a \mid b when b = ak for some integer k.
Results that make remainders exact. The division algorithm: for any integer a and any integer b > 0 there are unique integers q and r with a = bq + r and 0 \le r < b. Numbers in other bases proves that every positive integer has exactly one numeral in each base b \ge 2.
Procedures. The Euclidean algorithm finds \gcd(a, b) by repeated division, and the extended Euclidean algorithm writes it as ax + by with integers x and y. Modular arithmetic works with remainders alone, up to inverses, Fermat’s little theorem and RSA.
Classic results. There are infinitely many primes, by contradiction, and triangular numbers, the totals 1 + 2 + \cdots + n.
A path through it
Divisibility, then the division algorithm; base conversion follows it. Modular arithmetic is split: congruence notation comes after the division algorithm and before the Euclidean algorithm, then the extended Euclidean algorithm, and only then modular inverses and what follows them. The primes and triangular numbers stand apart from that chain: the first needs proof by contradiction, the second partial sums.