number theory October 28, 2026 on Chris Howey's blog

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