Number Theory – Formula Sheet

Divisibility

Definition

$a \mid b$ (read "$a$ divides $b$") iff $\exists k \in \mathbb{Z}: b = ak$

Properties

$a \mid b$ and $b \mid c \Rightarrow a \mid c$

$a \mid b \Rightarrow a \mid bc$ for any $c$

$a \mid b$ and $a \mid c \Rightarrow a \mid (bx+cy)$

$a \mid b$ and $b \mid a \Rightarrow a = \pm b$

GCD & LCM

$\gcd(a,b)$: largest $d$ dividing both

$\text{lcm}(a,b)$: smallest positive $m$ divisible by both

$\gcd(a,b) \cdot \text{lcm}(a,b) = ab$

Key: $\gcd(a,b) = 1$ means $a,b$ are coprime

Euclidean Algorithm

Standard Algorithm

$\gcd(a,b) = \gcd(b, a \bmod b)$

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

Extended Euclidean

Finds $x,y$ such that $ax + by = \gcd(a,b)$

Bézout's Identity: $\gcd(a,b) = ax + by$

Used to find modular inverses

Modular Inverse

$a^{-1} \bmod n$ exists $\iff \gcd(a,n)=1$

Compute via Extended Euclidean Algorithm

Time complexity: $O(\log \min(a,b))$

Prime Numbers

Definition

$p > 1$ is prime iff its only divisors are $1$ and $p$

Fundamental Thm of Arithmetic

Every $n > 1$ uniquely factors as: $$n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$$

Prime Facts

Infinitely many primes (Euclid)

Prime Number Theorem: $\pi(n) \sim \frac{n}{\ln n}$

Goldbach Conjecture: every even $n>2$ is sum of 2 primes

1 is NOT prime; 2 is the only even prime

Modular Arithmetic

Congruences

$a \equiv b \pmod{n} \iff n \mid (a-b)$

Equivalence relation on $\mathbb{Z}$

Properties

$a \equiv b \land c \equiv d \Rightarrow a+c \equiv b+d$

$a \equiv b \land c \equiv d \Rightarrow ac \equiv bd$

$a \equiv b \Rightarrow a^k \equiv b^k$

Division Rule

If $\gcd(c,n)=1$: $ac \equiv bc \pmod{n} \Rightarrow a \equiv b$

If $d = \gcd(c,n)$: $ac \equiv bc \pmod{n} \Rightarrow a \equiv b \pmod{n/d}$

$\mathbb{Z}_n^* = \{a : \gcd(a,n)=1\}$ forms a group

Linear Congruences

General Form

$ax \equiv b \pmod{n}$

Solvability

Solvable iff $d = \gcd(a,n)$ divides $b$

If solvable: exactly $d$ solutions mod $n$

Solution Steps

Check if $\gcd(a,n) \mid b$

Reduce: divide by $d$

Find $x_0$ using Extended Euclidean Alg

General solution: $x = x_0 + k\frac{n}{d}$

Special case $\gcd(a,n)=1$: unique solution $x \equiv a^{-1}b \pmod{n}$

Chinese Remainder Theorem

Statement

If $m_1, \ldots, m_k$ pairwise coprime, then $$x \equiv a_i \pmod{m_i}, \quad i=1,\ldots,k$$ has unique solution mod $M = m_1 m_2 \cdots m_k$

Construction

$x = \sum_{i=1}^{k} a_i M_i y_i$

$M_i = M/m_i$

$y_i \equiv M_i^{-1} \pmod{m_i}$

Isomorphism

$\mathbb{Z}_M \cong \mathbb{Z}_{m_1} \times \cdots \times \mathbb{Z}_{m_k}$

Generalizes to any system with pairwise coprime moduli

Fermat's Little Theorem

Statement

If $p$ prime and $\gcd(a,p)=1$:

$a^{p-1} \equiv 1 \pmod{p}$

Consequences

$a^p \equiv a \pmod{p}$ for all $a$

$a^{-1} \equiv a^{p-2} \pmod{p}$

Primality Testing

If $a^{n-1} \not\equiv 1 \pmod{n}$, then $n$ composite

Converse false: Carmichael numbers exist

Foundation for RSA cryptography

Euler's Theorem & φ Function

Euler Totient Function

$\phi(n) = \#\{k: 1 \le k \le n, \gcd(k,n)=1\}$

Computation

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

$\phi(p^k) = p^{k-1}(p-1)$

Multiplicative: $\gcd(m,n)=1 \Rightarrow \phi(mn)=\phi(m)\phi(n)$

Euler's Theorem

If $\gcd(a,n)=1$: $a^{\phi(n)} \equiv 1 \pmod{n}$

Generalizes Fermat; $\phi(p)=p-1$ for prime $p$

Primitive Roots

Definition

$g$ is a primitive root mod $n$ iff $\text{ord}_n(g) = \phi(n)$

Order: smallest $k > 0$ with $g^k \equiv 1 \pmod{n}$

Existence

Primitive roots mod $n$ exist iff $n \in \{1,2,4,p^k,2p^k\}$ with $p$ odd prime

Properties

If $g$ primitive root mod $n$: $g^i$ generates all $k$ with $\gcd(k,n)=1$

Number of primitive roots: $\phi(\phi(n))$

Useful for discrete logarithms, index calculus

Quadratic Residues

Definition

$a$ is a quadratic residue mod $p$ iff $\exists x: x^2 \equiv a \pmod{p}$

Legendre Symbol

$\left(\frac{a}{p}\right) = \begin{cases} 1 & \text{if } a \text{ is QR mod } p \\ -1 & \text{if } a \text{ is NQR mod } p \\ 0 & \text{if } p \mid a \end{cases}$

Computation

$\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p}$ (Euler)

$(p-1)/2$ quadratic residues mod $p$

Exactly half of $\{1,\ldots,p-1\}$ are QR

Quadratic Reciprocity

Main Law

For odd primes $p \ne q$:

$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}$

Supplements

$\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}$

$\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$

Computation

Use supplements + reciprocity to compute efficiently

Reduces to finite set of cases

"Law of reciprocity" in number theory

Continued Fractions

Definition

$x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots}}} = [a_0; a_1, a_2, \ldots]$

Convergents

$p_n = a_n p_{n-1} + p_{n-2}$

$q_n = a_n q_{n-1} + q_{n-2}$

$\frac{p_n}{q_n}$ converges to $x$

Key Property

$p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1}$

Best rational approximations, approximating irrationals

Pell's Equation

Standard Form

$x^2 - Dy^2 = 1$

where $D > 0$ is not a perfect square

Solutions

Fundamental solution $(x_1, y_1)$: smallest with $x, y > 0$

All solutions: $(x_n, y_n)$ from $(x_1 + y_1\sqrt{D})^n$

Connection to Cont. Fractions

Convergents of $\sqrt{D}$ give solutions

If CF period is $r$: fundamental sol. at convergent $p_{r-1}/q_{r-1}$ or $p_{2r-1}$

Solutions grow exponentially; can be found via CF

Diophantine Equations

Linear Form

$ax + by = c$

Has integer solutions iff $\gcd(a,b) \mid c$

Pythagorean Triples

$x^2 + y^2 = z^2$

Primitive: $\gcd(x,y,z)=1$

$x = m^2-n^2, y = 2mn, z = m^2+n^2$ for $\gcd(m,n)=1, m > n > 0$

Fermat's Last Thm

$x^n + y^n = z^n$ has no positive integer solutions for $n \ge 3$ (Wiles)

Linear DEs reduce to GCD; non-linear much harder

Arithmetic Functions

Divisor Functions

$\tau(n) = \#\{d: d \mid n\}$ (number of divisors)

$\sigma(n) = \sum_{d \mid n} d$ (sum of divisors)

Möbius Function

$\mu(n) = \begin{cases} 1 & n=1 \\ (-1)^k & n = p_1 \cdots p_k \\ 0 & \text{if } p^2 \mid n \end{cases}$

Möbius Inversion

If $g(n) = \sum_{d \mid n} f(d)$ then $f(n) = \sum_{d \mid n} \mu(d) g(n/d)$

Multiplicative functions: $\gcd(a,b)=1 \Rightarrow f(ab)=f(a)f(b)$

Perfect Numbers & Mersenne Primes

Perfect Numbers

$n$ is perfect iff $\sigma(n) = 2n$ (sum of proper divisors = $n$)

Even perfect numbers: $2^{p-1}(2^p-1)$ with $2^p-1$ prime

Known: 51 even perfect numbers; no odd ones found

Mersenne Primes

$M_p = 2^p - 1$ (prime)

If $2^p - 1$ prime, then $p$ must be prime

Only ~51 known; all correspond to perfect numbers

Examples

$6 = 2^1(2^2-1)$, $28 = 2^2(2^3-1)$, $496 = 2^4(2^5-1)$

1-to-1 correspondence: even perfects $\leftrightarrow$ Mersenne primes

Wilson's Theorem & Advanced

Wilson's Theorem

$(p-1)! \equiv -1 \pmod{p}$ iff $p$ prime

Primality Test

Characterization: $n$ prime $\iff (n-1)! \equiv -1 \pmod{n}$

Impractical for large $n$ (factorial too big)

Gauss's Generalization

For $n > 4$: $n$ composite $\Rightarrow \exists d: 1 < d < n, d \mid n!+1$

Theoretical importance > practical use due to factorial

RSA Cryptography

Key Generation

Choose large primes $p, q$; compute $n = pq$

$\phi(n) = (p-1)(q-1)$

Choose $e$ with $\gcd(e, \phi(n))=1$

Find $d \equiv e^{-1} \pmod{\phi(n)}$

Encryption/Decryption

Ciphertext: $c \equiv m^e \pmod{n}$

Plaintext: $m \equiv c^d \pmod{n}$

Security

Based on hardness of factoring $n$

Need $p, q$ large and distinct primes

Padding (OAEP) essential; raw RSA insecure

Quadratic Forms

Definition

$Q(x,y) = ax^2 + bxy + cy^2$

Discriminant

$\Delta = b^2 - 4ac$

Determines arithmetic properties

Representation

Number of representations of $n$ by $Q$ depends on form class

Class number: # inequivalent reduced forms

Generalizes quadratic residues; deep connections to algebraic number theory

Quick Reference

Key Facts

$\phi(n) = n\prod(1-1/p)$ for primes $p \mid n$

$\gcd(a,n)=1 \Rightarrow a^{\phi(n)} \equiv 1 \pmod{n}$

If $n$ is composite, it has a prime factor $p \le \sqrt{n}$

Testing & Factoring

Trial division: check primes up to $\sqrt{n}$

Pollard $\rho$: probabilistic, fast for moderate numbers

AKS test: deterministic primality test

Useful Bounds

$\pi(n) \approx \frac{n}{\ln n}$

$p_n \approx n \ln n$ (nth prime)

Study proofs; formulas alone won't build intuition

NUMBER THEORY Formula Sheet