Today I Learned

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

Category Archives: number theory

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}.