Integer to Power of Multiple of Order/Corollary

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $a$ and $n$ be integers.

Let $a \perp n$, that is, let $a$ and $b$ be coprime.

Let $c \in \Z_{>0}$ be the multiplicative order of $a$ modulo $n$.


Then $\map \phi n$ is a multiple of $c$, where $\map \phi n$ is the Euler phi function of $n$.


Proof

From Euler's Theorem, we have $a^{\map \phi n} \equiv 1 \pmod n$.

Applying Integer to Power of Multiple of Order we see that $\map \phi n$ is a multiple of $c$.

$\blacksquare$