Math · 14
Attempt these before you open a book or a video. Write the argument in the work box and the conclusion in the answer box. Check counts the problem only when both pass, and it does not open the solution. The solution stays locked for twenty minutes after you start the timer.
Attack 1
Prove there are infinitely many primes.
Timer not started. Twenty minutes of real work before a solution.
If \(p_1,\ldots,p_k\) were all the primes, then \(N=p_1\cdots p_k+1\) would have a prime factor, and that factor could not be any \(p_i\), because \(N\) leaves remainder 1 on division by each \(p_i\).
Attack 2
Solve \(3x\equiv 1\pmod{10}\).
Timer not started. Twenty minutes of real work before a solution.
The inverse of 3 mod 10 is 7, because \(21\equiv 1\). So \(x\equiv 7\pmod{10}\).
Attack 3
State Fermat’s little theorem and use it to compute \(2^{10}\mod 11\).
Timer not started. Twenty minutes of real work before a solution.
If \(p\) is prime and \(p\nmid a\), then \(a^{p-1}\equiv 1\pmod p\). Here \(2^{10}\equiv 1\pmod{11}\).
Elementary number theory is the arithmetic of the integers: divisibility, primes, congruences, and the multiplicative group of units modulo \(n\). The theorems you use forever are Euclid’s lemma, the Euclidean algorithm, the Chinese remainder theorem, Fermat’s little theorem, and the existence of primitive roots modulo primes. Quadratic reciprocity is the first theorem that feels deeper than the definitions. Analytic number theory, which counts primes, is a later life. This page stops at reciprocity and at the contest problems that use only this machinery.
William Stein’s Elementary Number Theory is a free PDF and it is the working book. Ireland and Rosen is the paid next book; no edition was verified. Contest number theory at the AIME and early Putnam level is the ceiling that matches this page. Algebraic number theory waits until the abstract-algebra page is real.
If you cannot compute a modular inverse by hand, you do not know the Euclidean algorithm, regardless of how many theorems you can name.
Statements only. Write the argument before you reveal it. A revealed proof you did not attempt is a paragraph you will not be able to rebuild at 2am.
Divisibility. The Euclidean algorithm computes \(\gcd\). Bézout: \(\gcd(a,b)=ax+by\) for some integers \(x,y\). Euclid’s lemma: if a prime divides a product, it divides a factor. Unique factorization follows.
The algorithm produces a descending sequence of remainders and the gcd is preserved at each step. Back-substitution gives Bézout. Euclid’s lemma is Bézout applied to a prime that shares no factor with one of the terms.
Congruences. \(ax\equiv b\pmod n\) has a solution iff \(\gcd(a,n)\) divides \(b\), and then there are exactly that many solutions modulo \(n\). The Chinese remainder theorem: if the moduli are coprime in pairs, the system has a unique solution modulo the product.
Solvability is Bézout. The Chinese remainder theorem for two moduli is an explicit Bézout combination; the general case is induction.
Units. \((\mathbb{Z}/n\mathbb{Z})^\times\) is a group of order \(\varphi(n)\). Euler’s theorem: \(a^{\varphi(n)}\equiv 1\pmod n\) when \(\gcd(a,n)=1\). Fermat is the prime case. For an odd prime \(p\), the multiplicative group mod \(p\) is cyclic.
Euler is Lagrange applied to the unit group. Cyclicity modulo a prime is proved by counting elements of each order using the factorization of \(x^{d}-1\), or by quoting the structure theorem for finite subgroups of the multiplicative group of a field.
Quadratic residues. The Legendre symbol \(\left(\frac{a}{p}\right\)\) is 1, −1, or 0 according as \(a\) is a quadratic residue, a nonresidue, or 0 mod an odd prime \(p\). Euler’s criterion and the law of quadratic reciprocity compute it.
Euler’s criterion is \(a^{(p-1)/2}\equiv\left(\frac{a}{p}\right)\pmod p\), from the cyclic group. Reciprocity is a real theorem; learn one proof, Gauss’s lemma being the most elementary, and be able to use the statement even while the proof is still fragile.
Diophantine samples. Linear Diophantine equations are Bézout. The equation \(x^2+y^2=z^2\) is solved by rational points on the circle, or by the standard parametrization. Fermat’s theorem on sums of two squares characterizes primes that are sums of two squares as 2 and those congruent to 1 mod 4.
The parametrization of Pythagorean triples comes from the slope of the line through \((-1,0)\) on the unit circle. The sum-of-two-squares theorem uses the fact that −1 is a square mod \(p\) exactly when \(p=2\) or \(p\equiv 1\pmod 4\), which is a Legendre-symbol computation, plus a descent.
Four rungs, in order. Do not skip a rung because the next one looks more serious.
Watch or read once. Do not study from this.
Stein, Elementary Number Theory, the PDF’s table of contents
Read once, do not study from this. Skim the contents so you see the path from gcd to reciprocity. Then start at chapter 1 and do the exercises.
The thing you work through.
William Stein, Elementary Number Theory: Primes, Congruences, and Secrets
Free PDF. This is the main text. It includes computation, which keeps the theorems honest.
The problem book.
AIME number theory and Stein’s exercises
AIME is the right hard-problem layer. Stein’s later exercises are the other half.
The hardest questions that exist at this level.
Putnam number theory via Borisov and Kedlaya
The sorted list plus the archive https://kskedlaya.org/putnam-archive/ . Ireland and Rosen is the paid graduate-leaning book; no edition was verified.
Names and links. The problem text stays on the source site. Copyrighted contest problems are not copied here. What follows is where they are and why they hurt.
Pass: Euclidean algorithm and inverse, from memory; proof of infinitely many primes; proof of Euler’s theorem from Lagrange; five AIME number-theory problems numbered 10 or higher. Fail if quadratic reciprocity is a formula you cannot evaluate on a small prime.
Five sets. Finish a set before you touch the next. Full sentences, not a circled answer.
Ten problems to meet again. Logging a writeup schedules them at 1 day, 7 days, and 30 days in this browser.
Prove there are infinitely many primes, compute a modular inverse with the Euclidean algorithm, and state Fermat’s little theorem. No notes.