Today I Learned

Some of the things I've learned every day since Oct 10, 2016

96: Euler’s Theorem (Number Theory)

Euler’s Theorem is a sort of extension of Fermat’s Little Theorem. One way of stating Fermat’s is that where $n$ is prime and $a$ is any integer,

$a^{p-1} \equiv 1 (\textrm{mod } n)$,

whereas Euler’s Theorem makes the more general statement that if $a, n$ are simply two coprime integers and $\varphi (n)$ is Euler’s totient function,

$a^{\varphi (n)} \equiv 1 (\textrm{mod } n)$.

The reason Fermat’s is a valid special case of Euler’s is because when $n$ is prime, $\varphi (n) = n - 1$.

[The congruence in the statement of Euler’s theorem is actually equivalent (‘if and only if’) to $a, n$ being coprime.]

65: Completely Multiplicative Functions

In number theory, a completely multiplicative function is a multiplicative function $f$ satisfying the stronger condition that $f(ab) = f(a)f(b)$ for any two $a, b \in \mathbb{N}$.