Some number theory properties I find interesting.
| Topic | Formula / Statement | Notes |
|---|---|---|
| Divisibility | $$a \mid b \iff b = ak$$ $$k \in \mathbb{Z}$$ | a divides b |
| Division Algorithm | $$a = bq + r$$ | Unique q, r |
| GCD (Euclidean) | $$\gcd(a,b) = \gcd(b,\; a \bmod b)$$ | Last nonzero remainder |
| Bézout’s Identity | $$\gcd(a,b) = sa + tb$$ $$s,t \in \mathbb{Z}$$ | Extended Euclidean algorithm |
| Fundamental Theorem of Arithmetic | $$n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$$ | Unique prime factorization |
| GCD via prime factors | $$\gcd(a,b) = \prod p_i^{\min(\alpha_i,\,\beta_i)}$$ | Take the minimum exponent of each prime |
| LCM via prime factors | $$\operatorname{lcm}(a,b) = \prod p_i^{\max(\alpha_i,\,\beta_i)}$$ | Take the maximum exponent of each prime |
| GCD–LCM Identity | $$a \cdot b = \gcd(a,b)\cdot\operatorname{lcm}(a,b)$$ $$\gcd(a,b)\cdot\operatorname{lcm}(a,b) = \prod p_i^{\alpha_i+\beta_i} = ab$$ | |
| Number of Divisors | $$\tau(n) = \prod{(e_i+1)}$$ | |
| Sum of Divisors | $$\sigma(n) = \prod \frac{p_i^{e_i+1}-1}{p_i-1}$$ | |
| Euler’s Totient Function | $$\phi(n) = n\prod(1-\frac{1}{p_i})$$ $$\phi(p^k) = p^k - p^{k-1}$$ $$\phi(p) = p-1$$ | Counts positive integers relatively prime to n |
| Congruence | $$a \equiv b \pmod{m} \iff m \mid (a-b)$$ | |
| Wilson’s Theorem | $$(p-1)! \equiv -1 \pmod{p}$$ | p prime |
| Sum of Squares | $$n = (a^2 + b^2) \iff p_i \equiv 3 \pmod{4}, e_i \equiv 0 \pmod{2}$$ | A number can be represented as sum of squares if every prime factor congruent to 3 mod 4 has an even power |
| Diophantus’ identity | $$(a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2 = (ac + bd)^2 + (ad - bc)^2$$ | Diophantus’ identiy says nm is sum-of-squares if both n and m are sum-of-squares |