= Number theory
{wiki}
Number theory studies <integers>, their <divisibility>, and the patterns created by <prime numbers>. Its questions often have short statements but rigid answers: which <integers> divide a given one, when does an <equation> have integer solutions, and when can arithmetic with <congruence classes> be reversed? The <Euclidean algorithm> and <modular multiplicative inverses> connect these questions through explicit calculations.
For example, $252=2^2\cdot3^2\cdot7$ and $198=2\cdot3^2\cdot11$. Their shared <prime factors> give <greatest common divisor> $18$. The <Euclidean algorithm> reaches that answer without finding either complete <prime factorization>. It also produces $18=4\cdot252-5\cdot198$, an instance of <Bézout's identity>. This relation certifies every common <divisor> at once and solves an associated <linear Diophantine equation>.
<Modular arithmetic> retains only remainders, but the lost information can be surprisingly controlled. Multiplication by $5$ modulo $17$ is a <permutation> of all residue classes, because $5$ has <modular inverse> $7$. Multiplication by $5$ modulo $15$ collapses fifteen residue classes to three. Thus an apparently small change in the modulus changes whether a calculation can be reversed. The <Chinese remainder theorem> explains another kind of compression: remainders modulo <coprime integers> can be combined into one remainder modulo their product.
Simple restrictions help reveal the structure without telling the whole story. Every <prime number> greater than three is congruent to $1$ or $5$ modulo $6$: the other four residue classes force <divisibility> by $2$ or $3$. The converse fails because $25$ and $35$ lie in those classes but are <composite numbers>. Necessary conditions are useful filters, not substitutes for <primality testing>.
The subject's appeal lies partly in this tension: <prime factorization> gives a clean description of every positive <integer>, while identifying factors and predicting their distribution lead to substantial further questions. <Analytic number theory> uses tools from <analysis> to study global patterns, and <algebraic number theory> extends arithmetic into <number fields>. Applications include <cryptography> and <error-correcting codes>; MIT's discrete applied mathematics course develops modular structures for both purposes. https://ocw.mit.edu/courses/18-200-principles-of-discrete-applied-mathematics-spring-2024/mit18_200_s24_lec15.pdf[Ankur Moitra, MIT 18.200, Modular Arithmetic and Elementary Algebra, 2024, introduction]{ref}
Euclid's \i[Elements] already gives a greatest-common-measure construction in Book VII, Proposition 2, and the argument that a finite list cannot exhaust the <prime numbers> in Book IX, Proposition 20. These are documented ancient treatments, rather than evidence that all of number theory began with one author. https://mathcs.clarku.edu/~djoyce/java/elements/bookVII/propVII2.html[Euclid, Elements VII.2, translated text hosted by David Joyce]{ref} https://mathcs.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html[Euclid, Elements IX.20, translated text hosted by David Joyce]{ref}
Back to article page
