Divisibility §

Theorem: For integers $a$, $b$, $c$, the following hold:

• $a \mid 0$, $1 \mid a$, $a \mid a$, $\pm a \mid \pm a$

• $a \mid 1$ iff $a = \pm 1$

• if $a \mid b$ and $c \mid d$, $ac \mid bd$

• if $a \mid b$ and $b \mid c$, $a \mid c$

• if $a \mid b$ and $b \mid a$, $a = \pm b$

• if $a \mid b$ and $b \neq 0$, $|a| \leq |b|$

• if $a \mid b$ and $a \mid c$, $a \mid (bx + cy)$ for all $x, y \in \mathbb{Z}$

  if $x + y = z$ and $a$ divides any two of $x, y, z$, then $a$ also divides the other number

GCD: for $a, b \in \mathbb{Z}$, the GCD is the largest integer that divides both $a$ and $b$. aka the unique integer $d$ such that: $d \mid a$, $d \mid b$, and $c \mid a \wedge c \mid b \implies c \leq d$.

well-ordered principle:

• any non-empty $S \subseteq \mathbb{N}$ has a least element
• any non-empty $S \subseteq \mathbb{Z}$ bounded above/below a greatest/least element

if $\gcd(a, b) = 1$, $a$ and $b$ are relatively prime (coprime).

Given $a, b \in \mathbb{Z}$ st $b \neq 0$, there exist unique integers $q$ and $r$ such that $a = qb + r$ and $0 \leq r < |b|$.

Bezout’s Theorem: Let $a, b \in \mathbb{Z}$ such that they’re not both zero. $\gcd(a, b)$ is the smallest positive integer $d$ that can be written in the form $d = ax + by$ with $x, y \in \mathbb{Z}$.

If $c$ is a common divisor of $a$ and $b$, $c \mid \gcd(a, b)$

Multiples of $\gcd(a, b)$ are precisely the integers of the form $ax + by$ for $x, y \in \mathbb{Z}$. In other words, $ax + by = c$ has a solution iff $\gcd(a, b) \mid c$.

$a$ and $b$ are relatively prime iff there exist $x, y \in \mathbb{Z}$ such that $ax + by = 1$.

If $\gcd(a, b) = d$, $\gcd\left(\frac{a}{d}, \frac{b}{d}\right) = 1$.

If $a \mid b$, $b \mid c$, and $\gcd(a, b) = 1$, then $ab \mid c$.

Euclid’s Lemma: If $a \mid bc$ and $\gcd(a, b) = 1$, then $a \mid c$.

If $p$ is prime and $p \mid ab$, then $p \mid a \vee p \mid b$.

$\gcd(a, b) = \gcd(a + bq, b)$

Euclid’s Algorithm: Let $a, b \in \mathbb{Z}$ st they’re not both zero. $r_{-1} = a$, $r_0 = b$. $r_{i + 1}$ is the remainder of the division algorithm applied to $r_{i-1}$ and $r_i$.

Linear equation theorem: Let $a, b$ be non-zero integers with $d = \gcd(a, b)$. $ax + by = d$ always has an integer solution $(x_0, y_0)$ which can be found using the extended Euclid’s algorithm. All other solutions are of the form $\left(x_0 + k \frac{b}{d}, y_0 - k \frac{a}{d}\right)$ for $k \in \mathbb{Z}$.

Linear equations where solutions must be integers are called diophantine equations.

If $p$ is prime and $p \mid a_1 a_2 \dots a_n$, then $p \mid a_k$ for some $k$, $1 \leq k \leq n$.

If $p, q_1, q_2, \dots, q_n$ are prime and $p \mid q_1 q_2 \dots q_n$, then $p = q_k$ for some $k$, $1 \leq k \leq n$.

Every positive integer ($n > 1$) can be expressed as a product of primes $n = p_1 p_2 \dots p_n$. This representation is unique up to the order of primes.

Any positive integer $n > 1$ can be written canonically as $n = p_1^{a_1} \dots p_r^{a_r}$ where $p_1 < \dots < p_r$ are prime and $0 < a_1, \dots, a_n$.

There are infinitely many primes.

Prime Number Theorem: The function $\pi$ is asymptotic to $\frac{x}{\ln x}$.

The proportion of primes at most $n$ is $~ \frac{1}{\ln n}$.

Goldbach Conjecture: Every even number $n \geq 4$ can be written as the sum of two primes.

Twin Prime Conjecture: There are infinitely many primes $p$ such that $p + 2$ is also prime.

A pythagorean triplet is an integer solution to the equation $x^2 + y^2 = z^2$. A pythagorean triple is called primitive if $\gcd(x, y, z) = 1$.

Modular Arithmetic §

The least common multiple of $a, b \in \mathbb{N}$ is the smallest positive integer $n$ such that $a \mid n$ and $b \mid n$.

$\gcd(a, b) = \prod_{\text{primes }p} p^{\min(a_p, b_p)}$

$lcm(a, b) = \prod_{\text{primes }p} p^{\max(a_p, b_p)}$

$ab = \prod p^{a_p + b_p} = \prod p^{\min(a_p, b_p) + \max(a_p, b_p)} = \gcd(a, b) \cdot lcm(a, b)$

For a given $m \in \mathbb{N}$, two integers $a, b$ are congruent modulo $m$ if $m \mid a - b$.

$a \equiv b \mod m$

Every integer is congruent modulo $m$ to precisely one integer $a$ where $0 < a < m$.

The set of integers $0, 1, 2, \dots, m - 1$ is called the least residue system modulo $m$.

$a_1, a_2, \dots, a_m$ is a complete residue system modulo $m$ if every integer is congruent modulo $m$ to precisely one of $a_i$.

$a \equiv b \mod m$ iff $a$ and $b$ leavea the same remainder when divided by $m$.

Equivalence relation.

• reflexive: $a \equiv a \mod m$
• symmetric: if $a \equiv b \mod m$, then $b \equiv a \mod m$
• transitive: if $a \equiv b \mod m$, $b \equiv c \mod m$, then $a \equiv c \mod m$

for a given $m \in \mathbb{N}$, $a, b, c, d \in \mathbb{Z}$:

• if $a \equiv b \mod m$ and $c \equiv d \mod m$, then $a \pm c \equiv b \pm d \mod m$
• if $a \equiv b \mod m$ and $c \equiv d \mod m$, then $ac \equiv bd \mod m$
• if $a \equiv b \mod m$, then $a + c \equiv b + c \mod m$ and $ac = bc \mod m$.
• if $a \equiv b \mod m$, then $a^n \equiv b^n \mod m$ for all $n \in \mathbb{N}$

If $ac \equiv bc \mod m$ and $d = \gcd(c, m)$, then $a \equiv b \mod \frac{m}{d}$

If $\gcd(c, m) = 1$ and $ac \equiv bc \mod m$, then $a \equiv b \mod m$.

If $p$ is prime and $p \nmid c$, then $ac \equiv bc \mod p \implies a \equiv b \mod p$.

Linear Congruences §

$ax \equiv b \mod m$

mutually incongruent solutions

If $ax \equiv b \mod m$ and $d = \gcd(a, m)$:

• there exists a solution iff $d \mid b$
• if $d \mid b$, there are exactly $d$ mutually incongruent solutions modulo $m$
• if $x_0$ is a solution, the complete set of incongruent solutions is $\{x_0, x_0 + \frac{m}{d}, x_0 + \frac{2m}{d}, \dots, x_0 + (d - 1) \frac{m}{d}\}$

$ax \equiv b \mod m$ has a unique solution modulo $m$ iff $a$ and $m$ are coprime.

Let $m > 1$, $a \in \mathbb{Z}$. An integer $b \in \mathbb{Z}$ is an inverse of of $a \mod m$ if $ab \equiv 1 \mod m$. $a$ has an inverse modulo $M$ iff $\gcd(a, m) = 1$.

Fermat’s Little Theorem: if $p$ is prime and $p \nmid a$, then $a^{p - 1} \equiv 1 \mod p$

A solution to $ax \equiv 1 \mod m$ is called a (multiplicative) inverse of $a$ modulo $m$. $a \cdot a^{-1} \equiv 1 \mod m$. Inverses exist only if $\gcd(a, m) = 1$.

If $\gcd(a, m) = 1$, for any $c \in \mathbb{Z}$, $c, c + a, \dots, c + (m - 1)a$ is a complete residue system. Order needn’t match up.

If $\gcd(a, m) \equiv 1 \mod m$ and $a^{m - 1} \not\equiv 1 \mod m$, then $m$ is composite.

Primality testing: if $\gcd(a, b) = 1$ and $a^{m - 1} \equiv 1 \mod m$, then $m$ is composite. Test of compositeness: converse is false. Composite numbers for which the test holds are called Carmichael numbers.

Wilson’s Theorem: $p$ is prime iff $(p - 1)! \equiv -1 \mod p$

The Euler totient $\phi$: $\phi(n) = \#\{a : 1 \leq a \leq n - 1, \gcd(a, n) = 1\}$

Euler’s Theorem: $a^{\phi(m)} \equiv 1 \mod m$

Chinese Remainder Theorem: Suppose $m_1, m_2, \dots, m_r > 1$ such that $\gcd(m_1, m_j) = 1$ for $i \neq j$. Then, for any integers $a_1, \dots, a_r$, the system $x \equiv a_i \mod m_i$ for $1 \leq i \leq r$ has a solution. Additionally, any solution is unique modulo $m_1 \cdots m_r$.

The Euler totient $\phi$ is multiplicative. if $m, n \in \mathbb{Z}^+$ and $\gcd(m, n) = 1$, $\phi(mn) = \phi(m) \phi(n)$.

If $p$ is prime:

• $\phi(p) = p - 1$
• $\phi(p^2) = p^2 - p$
• $\phi(p^k) = p^k - p$

$\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$

$n = \sum_{d \mid n} \phi(d)$

RSA §

• pick two large primes $p$ and $q$

• compute $\phi(pq) = (p - 1)(q - 1)$

• choose an exponent $e$ that is coprime to $\phi(pq)$

• find a $d$ such that $ed \equiv 1 \pmod {pq}$

• public: $(e, pq)$; private: $d$, $p$, $q$

• encryption of a message $w$: $w^e \pmod {pq}$

• decryption of ciphertext $w^e \pmod {pq}$:

  ${(w^e)}^d \pmod {pq} \equiv w^{ed} \pmod {pq} \equiv w^{1 + \phi(pq)} \pmod {pq} \equiv w \pmod {pq}$

For $a, m \in \mathbb{Z}$ st $\gcd(a, m) = 1$. The order of $a$ is the smallest positive exponent $e$ st $a^e \equiv 1 \pmod{m}$. $ord_m(a)$.

$a^k \equiv 1 \pmod{m}$ implies that $ord_m(a) \mid k$.

$ord_m(a) \mid \phi(m)$

Let $\gcd(a, m) = 1$. $a^i \equiv a^j \pmod{m} \iff i \equiv j \pmod{ord(a)}$

$a, a^2, \dots, a^{ord(a)}$ are distinct modulo $m$.

An integer $a$ (relatively prime to $m$) is called a primitive root of $m$ if $ord(a) = \phi(m$.

If $a_1, a_2, \dots, a_{\phi(m)}$ are the positive ints less than $m$ and coprime to $m$ and $a$ is a primitive root of $m$, then $a, a^2 \dots a^{\phi(m)}$ are congruent to $a_1, a_2,b \equiv a^k \pmod{m}$ \dots, a_{\phi(m)}$ in some order modulo $m$. For any integer $b$, $b \equiv a^k \pmod{m}$ for some $1 \leq k \leq ord(a)$.

If $m$ has a primitive root, then it has exactly $\phi(\phi(m))$ primtive roots.

Suppose $a$ is a primitive root of $m$. Then $a^k$ is also a primitive root of $m$ iff $\gcd(k, \phi(m)) = 1$.

Lagrange theorem: Let $p$ be a prime and $f(x) = a_n x^n + \dots + a_0$ where $a_i \in \mathbb{Z}$ and $a_n \not\equiv 0 \pmod{p}$. Then $f(x) \equiv 0 \pmod{p}$ has at most $n$ solutions modulo $p$.

If $p$ is an odd prime divisor of $n^2 + 1$, then $p \equiv 1 \pmod{4}$.

If $ord_n(a) = k$, then $ord_n(a^h) = \frac{k}{\gcd(k, h)}$

If $\gcd(h, ord_n(a)) = 1$, then $ord_n(a^h) = ord_n(a)$.

An integer $n$ has a primitive root iff $n = 2, 4, p^k, 2 p^k$ where $p$ is an odd prime.

Let $g$ be a primitive root of $n$ and $\gcd(a, n) = 1$. $a \equiv g^e \pmod{n}$ for some positive $e$. The smallest such exponent is called the index of $a$ mod $n$ for the base $g$. $ind_g(a)$. Discrete logarithm.

Indices satisfy:

• $ind(ab) \equiv ind(a) + ind(b) \pmod{\phi(n)}$
• $ind(a^k) \equiv k ind(a) \pmod{\phi(n)}$

Theorem: Let $n$ be an integer with a primitive root and $\gcd(a, n) = 1$. Then $x^k \equiv a \pmod{n}$ has a solution iff $a^{\frac{\phi(n)}{d}} \equiv 1 \pmod{n}$ has a solution where $d = \gcd(k, \phi(n))$. There are exactly $d$ solutions.

Quadratic Reciprocity §

There are exactly $\frac{p - 1}{2}$ integers $a$ ($p \nmid a$) that are squares modulo $p$. These $\frac{p - 1}{2}$ integers occur as squares of $1^2, 2^2, \dots, \left(\frac{p - 1}{2}\right)^2$.

If $p \nmid a$ and $a \equiv b^2 \pmod{p}$ for some $b$, then we call $a$ a quadratic residue modulo $p$.

If $p$ and $q$ are distinct odd primes, then $(p/q)(q/p) = {(-1)}^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}$

If $p$ is an odd prime ad $a$ is an odd integer st $\gcd(a, p) = 1$:

$\sum_{k = 1}^{\frac{p - 1}{2}} \lfloor\frac{ka}{p}\rfloor \equiv \mu(a, p) \pmod{2}$

if $2^k + 1$ is an odd prime, $k$ is a power of 2.

a fermat number is a positive integer of the form $F_n = 2^{(2^n)} + 1$. if $F_n$ is prime, we $F_n$ is a fermat prime.

• are all fermat numbers prime? no
• are there infinitely many fermat primes? open
• are there infinitely many compositive fermat numbers? open
• are there any fermat primes $F_n$ for $n > 4$? open

Jacobi Symbol:

$(a | n) = {(a | p_1)}^{e_1} \cdots {(a | p_r)}^{e_r}$

• $(ab | n) = (a | n)(b | n)$
• $(a | mn) = (a | m)(a | n)$

Let $a, b$ be odd positive integers with $\gcd(a, b) = 1$.

$(a | b) = \begin{cases} (b | a) & a \equiv 1 \pmod{4} \vee b \equiv 1 \pmod{4} \\ - (b | a) & a \equiv b \equiv 3 \pmod{4} \end{cases}$

$(2 | b) = \begin{cases} 1 & b \equiv 1 \pmod{8} \vee b \equiv 7 \pmod{8} \\ -1 & b \equiv 3 \pmod{8} \vee b \equiv 5 \pmod{8} \end{cases}$

$(-1 | b) = \begin{cases} 1 & b \equiv 1 \pmod{4} \\ -1 & b \equiv 3 \pmod{4} \end{cases}$

Euler’s criterion doesn’t hold for the Jacobi symbol.

• if $n$ is prime, jacobi = legendre
• if $n$ is composite and $(a | n) = -1$, then $a$ is a NR of $n$
• if $n$ is composite and $(a | n) = 1$, then $a$ may or may not be a QR of $n$

Euler’s primality test: check if $a^{\frac{p - 1}{2}} \equiv \pm 1 \pmod{p}$

Diophantine Approximation §

Approximate real numbers by rational numbers.

Let $\alpha$ be an irrational number. Then there exist infinitely many $\frac{a}{b}$ st $|\alpha - \frac{a}{b} < \frac{1}{2b^2}$.

If $\alpha$ is irrational, the line $x = \alpha$ intersects infinitely many Ford circles.

Continued Fractions §

the continued fraction made from $[a_0; a_1, \dots, a_n]$ by cutting off the expansion after the $k$-th partial denominator is called the $k$-th convergent of the continued fraction and is denoted as $C_k$

an infinite continued fractino $[a_0, a_1, \dots]$ is the real number $\lim_{n \rightarrow \infty} [a_0; a_1, \dots, a_n]$

infinite continued fractions are irrational

all irrational numbers have infinite continued fraction expressions

distinct infinite continued fractions correspond to distinct irrational numbers

Quadratic Forms §

A binary integral quadratic form is a polynomial $Q(x, y) = ax^2 + bxy + cy^2$. if $n = Q(x, y)$ has a solution, we say that $n$ is represented by $Q$.

representation problem: given a quadratic form $Q$, which integers are represented by $Q$?

pairs with gcd greater than one can be reduced to pairs with gcd = 1. pairs with gcd = 1 are called primitive pairs.