Number Theory Formulas

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

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

Euclidean algorithm

$a \mid b$

means $b=ka$ for some integer $k$

$a\equiv b \pmod{n}$

means $n \mid (a-b)$

$(a+b)\bmod n=[(a\bmod n)+(b\bmod n)]\bmod n$

$(a\cdot b)\bmod n=[(a\bmod n)\cdot(b\bmod n)]\bmod n$

$n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$

fundamental theorem of arithmetic — prime factorization

$d(n)=(e_1+1)(e_2+1)\cdots(e_k+1)$

number of positive divisors of $n$

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

Euler's totient function

$a^{\varphi(n)}\equiv 1\pmod n$

Euler's theorem — $\gcd(a,n)=1$

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

$p$ is prime

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

$p$ is prime, $\gcd(a,p)=1$