Number Theory Summary

Intro to Proofs · Axiom Academy

A review of how divisibility, primes, and modular arithmetic reveal deep structure in the integers — and underpin modern cryptography. Foundation of mathematics: number theory supplies rigorous proofs for the arithmetic we take for granted, exposing deeper structure in the integers. Primes are central: the Fundamental Theorem of Arithmetic makes primes the building blocks of every integer, with a unique factorization. Algorithms are proofs: the Euclidean algorithm is at once an efficient computation and a constructive proof of Bézout's identity. Modular arithmetic simplifies: congruences collapse infinitely many integers into n residue classes, turning hard divisibility questions into finite ones. Theory meets practice: these abstract results directly enable RSA and the rest of modern cryptography. Core Concept Divisibility & the Division Algorithm Divisibility, written , is the relation that drives all integer arithmetic — it is transitive and respects sums. The division algorithm pins down the quotient and remainder exactly. Division algorithm: for integers a and b>0 , there exist unique q,r with a = bq + r and . When to use: the workhorse identity for any x,y . Watch out for: uniqueness needs — a remainder outside that range is the wrong r . Core Concept GCD & the Euclidean Algorithm is the largest integer dividing both; every common divisor divides it. Repeatedly replacing (a,b) with reaches in steps.

This is the written version of the interactive lesson above. See the full Intro to Proofs course.