Number Theory

Recall that $a\equiv b\pmod m$ denotes $m\mid a-b$. Congruence is closed under addition, subtraction and multiplication, so one can "replace everything with remainders and then calculate".

The most useful point is that the values of squares (and higher powers) are restricted modulo small numbers:

When proving that a number of a certain form does not have a certain property, first calculate the set of possible values of the target expression modulo some modulus; if the target falls outside the set, the proof is complete. For example, a sum of two squares modulo $4$ can only be $0,1,2$, so $4k+3$ is not a sum of two squares.

Every positive integer is uniquely written as a product of prime powers (the Fundamental Theorem of Arithmetic). From this:

• If the product of two coprime numbers is a perfect square, then $\Rightarrow$ each of the two numbers is a perfect square (e.g. to prove that $n(n+1)(n+2)=m^3-m$ is not a square, use $\gcd(m,m^2-1)=1$).
• Use Euclid's method to prove that there are infinitely many primes: construct a number that "escapes the list" and take its new prime factor. By modifying the congruence class in which the constructed number lies, one can prove that there are infinitely many primes of type $4k+3$ (together with the lemma that "$\equiv3\pmod4$ must have a prime factor $\equiv3\pmod4$").
• Fermat numbers $F_k=2^{2^k}+1$ are pairwise coprime (by $F_0\cdots F_{k-1}=F_k-2$), which also gives that there are infinitely many primes.

For primes $p$ and $p\nmid a$: Fermat's little theorem $a^{p-1}\equiv1\pmod p$. Let $d=\operatorname{ord}_p(a)$ denote the smallest positive integer such that $a^d\equiv1$; then $d\mid p-1$, and $a^n\equiv1\iff d\mid n$.

Signature killer move (handling $n\mid a^n\pm1$): take the smallest prime factor $p$ of $n$ and look at $\operatorname{ord}_p(a)$—it simultaneously divides $n$ and $p-1$, while the smallest prime factor forces $\gcd(n,p-1)=1$, forcing the order to be $1$, a contradiction. Hence $n\mid2^n-1$ has only $n=1$.

Wilson's theorem: $p$ prime $\iff(p-1)!\equiv-1\pmod p$ (proved by "pairing elements with their inverses; only $\pm1$ is self-inverse").

When proving that an equation has "no positive integer solutions": assume a solution exists, take the set that makes some variable minimal, then construct another set of the same type that is strictly smaller, contradiction (positive integers cannot descend infinitely). The engine is often congruence.

Typical: $x^2+y^2=3z^2$. Modulo $3\in\{0,1\}$, squaring gives $x^2+y^2\equiv0$ forcing $3\mid x,\ 3\mid y$, and after substitution we get $3\mid z$, so $(x/3,y/3,z/3)$ is a smaller solution—contradiction, hence only the trivial solution exists. The same method proves $\sqrt3$ irrational (descent for $p^2=3q^2$).

If the moduli $m_1,\dots,m_k$ are pairwise coprime, then the system of congruences $x\equiv r_i\pmod{m_i}$ has a solution, and it is unique modulo $\prod m_i$.

CRT is a powerful tool for "constructing existence": if you want a string of numbers each satisfying a different divisibility requirement, assign a coprime modulus to each position. For example, to prove "there exist arbitrarily long runs of consecutive integers, each divisible by some square $>1$": take distinct primes $p_1,\dots,p_n$, solve $x\equiv-i\pmod{p_i^2}$, then $x+i$ is divisible by $p_i^2$.