Number theory: 50 theorems from primes to quadratic residues

All 50 cards

1. 1
   What does $a \mid b$ mean?
   $a$ divides $b$: $b = ka$ for some integer $k$
2. 2
   If $d \mid a$ and $d \mid b$, then…
   $d \mid ax + by$ for all integers $x$ and $y$
3. 3
   Division algorithm
   For integers $a$ and $b > 0$ there are unique integers $q$ and $r$ with $a = bq + r$ and $0 \le r < b$
4. 4
   Prime number
   An integer $p > 1$ whose only positive divisors are $1$ and $p$

   1 is neither prime nor composite.
5. 5
   Fundamental theorem of arithmetic
   Every integer greater than 1 is a product of primes, and that factorization is unique apart from the order of the factors
6. 6
   Euclid’s lemma
   If a prime $p$ divides $ab$, then $p \mid a$ or $p \mid b$
7. 7
   If $a \mid bc$ and $\gcd(a, b) = 1$, then…
   $a \mid c$
8. 8
   Euclid’s proof that there are infinitely many primes
   Given primes $p_1, \dots, p_k$, the number $p_1 p_2 \cdots p_k + 1$ leaves remainder 1 when divided by each of them, so its prime factors are new primes

   The number itself need not be prime: $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$.
9. 9
   To test whether $n$ is prime, which divisors must you try?
   Only the primes up to $\sqrt{n}$

   If $n = ab$ with $1 < a \le b$, then $a \le \sqrt{n}$.
10. 10
    Sieve of Eratosthenes
    List the numbers $2$ to $n$. For each unmarked $p \le \sqrt{n}$, which is prime, cross out the multiples of $p$ from $p^2$ on. What remains unmarked is prime
11. 11
    Prime number theorem
    $\pi(x) \sim \dfrac{x}{\ln x}$, where $\pi(x)$ counts the primes up to $x$
12. 12
    Number of positive divisors of $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$
    $(a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$

    Example: $72 = 2^3 \cdot 3^2$ has $4 \cdot 3 = 12$ divisors.
13. 13
    gcd and lcm from prime factorizations
    The gcd takes each prime to the smaller of its two exponents; the lcm takes the larger

    $12 = 2^2 \cdot 3$ and $18 = 2 \cdot 3^2$ give $\gcd = 2 \cdot 3 = 6$ and $\operatorname{lcm} = 2^2 \cdot 3^2 = 36$.
14. 14
    Product of $\gcd(a, b)$ and $\operatorname{lcm}(a, b)$
    $\gcd(a, b) \cdot \operatorname{lcm}(a, b) = ab$ for positive integers $a$ and $b$
15. 15
    Euclidean algorithm
    Replace $(a, b)$ with $(b, a \bmod b)$ until the remainder is $0$; the last nonzero remainder is $\gcd(a, b)$

    It works because $\gcd(a, b) = \gcd(b, a \bmod b)$.
16. 16
    $\gcd(252, 105)$
    $21$

    $252 = 2 \cdot 105 + 42$, $105 = 2 \cdot 42 + 21$, $42 = 2 \cdot 21$.
17. 17
    Bézout’s identity
    For integers $a$ and $b$, not both zero, there are integers $x$ and $y$ with $ax + by = \gcd(a, b)$

    The gcd is the smallest positive integer of the form $ax + by$. The extended Euclidean algorithm finds $x$ and $y$.
18. 18
    Coprime (relatively prime) integers
    Integers $a$ and $b$ with $\gcd(a, b) = 1$
19. 19
    When does $ax + by = c$ have integer solutions?
    Exactly when $\gcd(a, b) \mid c$
20. 20
    All integer solutions of $ax + by = c$, given one solution $(x_0, y_0)$
    $x = x_0 + \dfrac{b}{d}\,t$, $y = y_0 - \dfrac{a}{d}\,t$ for integers $t$, where $d = \gcd(a, b)$
21. 21
    What does $a \equiv b \pmod{n}$ mean?
    $n \mid a - b$: $a$ and $b$ leave the same remainder when divided by $n$
22. 22
    If $a \equiv b$ and $c \equiv d \pmod{n}$, then…
    $a + c \equiv b + d$, $ac \equiv bd$ and $a^k \equiv b^k \pmod{n}$
23. 23
    When can you cancel $c$ from $ac \equiv bc \pmod{n}$?
    When $\gcd(c, n) = 1$. In general, $a \equiv b \pmod{n / \gcd(c, n)}$
24. 24
    When does $a$ have an inverse modulo $n$?
    Exactly when $\gcd(a, n) = 1$

    Bézout gives it: if $ax + ny = 1$, then $x$ is the inverse of $a$.
25. 25
    Inverse of $3$ modulo $7$
    $5$, since $3 \cdot 5 = 15 \equiv 1 \pmod{7}$
26. 26
    How many solutions does $ax \equiv b \pmod{n}$ have?
    None unless $d = \gcd(a, n)$ divides $b$; if it does, exactly $d$ solutions modulo $n$
27. 27
    When are the integers modulo $n$ a field?
    Exactly when $n$ is prime
28. 28
    Why does the digit-sum test for divisibility by 3 and 9 work?
    Because $10 \equiv 1 \pmod{9}$, every power of 10 is $\equiv 1$, so a number is congruent to its digit sum modulo 9, and so also modulo 3
29. 29
    Computing $a^k \bmod n$ efficiently
    Repeated squaring: square repeatedly, multiply in the powers that match the 1 bits of $k$, and reduce modulo $n$ at each step

    It takes at most $2\log_2 k$ multiplications instead of $k - 1$.
30. 30
    Fermat’s little theorem
    If $p$ is prime and $p \nmid a$, then $a^{p-1} \equiv 1 \pmod{p}$

    Equivalently, $a^p \equiv a \pmod{p}$ for every integer $a$.
31. 31
    $2^{100} \bmod 7$
    $2$

    $2^3 = 8 \equiv 1 \pmod{7}$ and $100 = 3 \cdot 33 + 1$, so $2^{100} \equiv 2$.
32. 32
    Euler’s totient $\varphi(n)$
    The number of integers from $1$ to $n$ that are coprime to $n$
33. 33
    $\varphi(p^k)$ for a prime $p$
    $p^k - p^{k-1} = p^{k-1}(p - 1)$

    In particular $\varphi(p) = p - 1$.
34. 34
    Formula for $\varphi(n)$ from the prime factors of $n$
    $\varphi(n) = n \displaystyle\prod_{p \mid n} \left(1 - \frac{1}{p}\right)$

    $\varphi$ is multiplicative: $\varphi(mn) = \varphi(m)\,\varphi(n)$ when $\gcd(m, n) = 1$.
35. 35
    $\varphi(36)$
    $12$

    $36 \left(1 - \tfrac{1}{2}\right)\left(1 - \tfrac{1}{3}\right) = 12$
36. 36
    Euler’s theorem
    If $\gcd(a, n) = 1$, then $a^{\varphi(n)} \equiv 1 \pmod{n}$

    Fermat’s little theorem is the case $n = p$.
37. 37
    Order of $a$ modulo $n$
    The smallest $k > 0$ with $a^k \equiv 1 \pmod{n}$, for $\gcd(a, n) = 1$; it always divides $\varphi(n)$
38. 38
    Primitive root modulo $n$
    An $a$ whose order modulo $n$ is $\varphi(n)$, so its powers run through every residue coprime to $n$

    Primitive roots exist exactly when $n$ is $1$, $2$, $4$, $p^k$ or $2p^k$ for an odd prime $p$.
39. 39
    Carmichael number
    A composite $n$ with $a^{n-1} \equiv 1 \pmod{n}$ for every $a$ coprime to $n$, so it passes the Fermat primality test for all such bases

    The smallest is $561 = 3 \cdot 11 \cdot 17$.
40. 40
    Wilson’s theorem
    An integer $n > 1$ is prime exactly when $(n - 1)! \equiv -1 \pmod{n}$

    Example: $6! = 720 = 7 \cdot 103 - 1 \equiv -1 \pmod{7}$.
41. 41
    Chinese remainder theorem
    If $n_1, \dots, n_k$ are pairwise coprime, the system $x \equiv a_i \pmod{n_i}$ has exactly one solution modulo $n_1 n_2 \cdots n_k$
42. 42
    Solve $x \equiv 2 \pmod{3}$, $x \equiv 3 \pmod{5}$, $x \equiv 2 \pmod{7}$
    $x \equiv 23 \pmod{105}$

    The classic puzzle from the Sunzi Suanjing, a Chinese text from around the 3rd to 5th century.
43. 43
    Quadratic residue modulo $n$
    An $a$ coprime to $n$ for which $x^2 \equiv a \pmod{n}$ has a solution
44. 44
    Quadratic residues modulo $7$
    $1$, $2$ and $4$

    The squares of $1, \dots, 6$ are $1, 4, 2, 2, 4, 1$ modulo 7.
45. 45
    How many nonzero quadratic residues are there modulo an odd prime $p$?
    Exactly $\frac{p-1}{2}$; the other $\frac{p-1}{2}$ nonzero residues are non-residues
46. 46
    Legendre symbol $\left(\frac{a}{p}\right)$
    $1$ if $a$ is a quadratic residue modulo the odd prime $p$, $-1$ if it is a non-residue, and $0$ if $p \mid a$
47. 47
    Euler’s criterion
    $\left(\dfrac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p}$ for an odd prime $p$
48. 48
    When is $-1$ a quadratic residue modulo an odd prime $p$?
    Exactly when $p \equiv 1 \pmod{4}$
49. 49
    Law of quadratic reciprocity
    For distinct odd primes $p$ and $q$: $\left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}$

    So the two symbols are equal unless both $p$ and $q$ are $\equiv 3 \pmod{4}$.
50. 50
    Which odd primes are a sum of two squares?
    Exactly those with $p \equiv 1 \pmod{4}$

    Fermat’s theorem on sums of two squares; for example $13 = 2^2 + 3^2$.