A floor measures 1729 by 1001 units. What is the largest square tile that covers it with no cutting, and how can that be found without listing every divisor? The answer is 91, and the unit's second article finds it in five divisions. Along the way, the unit asks what the familiar facts of school arithmetic actually rest on.
Abstract algebra studies sets with operations that obey a few stated rules. The integers, with addition and multiplication, are the model for nearly all of them. So a course that teaches rings first begins with the integers themselves. It asks three questions:
- why does division always leave exactly one remainder?
- why do two numbers have a greatest common divisor, and how can it be computed quickly?
- why does every integer factor into primes in essentially one way?
The answers introduce the tools used for the rest of the course, and each step is proved in full. First, the well-ordering principle (every nonempty set of nonnegative integers has a smallest element) proves that remainders exist. Then repeated division gives the Euclidean algorithm for the greatest common divisor. Run backwards, it writes the gcd as a combination of the two numbers, which is Bezout's identity. Bezout's identity proves Euclid's lemma: a prime dividing a product divides one of the factors. Finally, Euclid's lemma proves that factorization into primes is unique.
One example runs through all three articles: the pair 1729 and 1001, the floor above. It is followed from the Euclidean algorithm to the prime factorizations $1729 = 7 \cdot 13 \cdot 19$ and $1001 = 7 \cdot 11 \cdot 13$. Every number comes from a script in the site's repository.
The unit covers Chapter 1 of the course text (Hungerford, 2014). Later units build on every result in it. Remainders become the elements of the integers modulo $n$. Bezout's identity finds inverses there and makes the RSA cryptosystem work. And the whole chain of arguments returns for polynomials, with degree in place of size.
Articles
- The Division Algorithm: why does division leave exactly one remainder? The well-ordering principle and a full proof of existence and uniqueness. The floor formula, and why programming languages disagree about negative remainders. How remainders sort the integers into classes, applied to last digits.
- Divisibility and the Euclidean Algorithm: how can a greatest common divisor be found fast? Divisibility and its laws, and Euclid's algorithm with proofs that it stops and is correct. Bezout's identity through the extended Euclidean algorithm, relatively prime integers and cancellation, and linear equations in integers. Lamé's bound on the number of steps.
- Primes and the Fundamental Theorem of Arithmetic: why is factorization into primes unique? Primes and Euclid's lemma, and existence and uniqueness of prime factorizations. A number system in which uniqueness fails. Divisibility and gcds read from prime exponents, Euclid's proof that the primes never run out, and the sieve of Eratosthenes.
Related topics
The next unit of the course is congruence and modular arithmetic. It turns the classes of integers with a common remainder into a number system of their own: congruence modulo n and the integers modulo n. It begins with equivalence relations and partitions, which make the sorting precise. The same arguments return for polynomials in polynomial division over a field and in irreducible polynomials, which play the part of the primes.
References
- Hungerford, T. W. (2014). Abstract Algebra: An Introduction (3rd ed.), Chapter 1. Brooks/Cole, Cengage Learning. The course text. record · 44 pages
- Judson, T. W. (2026). Abstract Algebra: Theory and Applications (annual edition, August 2026), Chapter 2. Free online at judsonbooks.org. record · 44 pages