= Exponent reduction for units
{title2=$a^k\equiv a^{k\bmod\varphi(n)}\pmod n$}
For a <unit modulo n> $a$ and a <nonnegative integer> $k$, <division with remainder> writes $k=q\varphi(n)+r$ with $0\leq r<\varphi(n)$. <Euler's theorem> then gives
$$
a^k=(a^{\varphi(n)})^q a^r\equiv a^r\pmod n.
$$
This replaces a potentially enormous <exponent> by a small <remainder>. The <exponent> itself is reduced modulo <Euler's totient function>, while the powers are reduced modulo $n$: these are different <integer moduli>.
For a worked modulo-fifteen calculation, seven is <coprime> to fifteen and $\varphi(15)=8$. Therefore
$$
2029=253\cdot8+5,\qquad 7^{2029}\equiv7^5\pmod{15}.
$$
Use <exponentiation by squaring> on the remaining <exponent> $5=(101)_2$, reducing after each <multiplication>:
$$
7^2\equiv49\equiv4,\qquad
7^4\equiv4^2\equiv1,\qquad
7^5\equiv1\cdot7\equiv7\pmod{15}.
$$
Thus \b[$7^{2029}\bmod15=7$]. <Modular exponentiation> supplies the computation; <Euler's theorem> supplies the optional shortening of its <exponent>. <Exponentiation by squaring> also works for <nonunit> bases, without using this shortening.
The guaranteed <exponent> $\varphi(n)$ is a common return <exponent> and an upper bound on the shortest period; it need not be that period. The <multiplicative order> $d=\operatorname{ord}_n(a)$ is the least positive return <exponent> for the chosen <unit>. The <Carmichael function> $\lambda(n)$ is the least positive return <exponent> that works for every <unit>. Their precise relation is
$$
\operatorname{ord}_n(a)\mid\lambda(n)\mid\varphi(n).
$$
Either smaller return <exponent> can replace $\varphi(n)$ in <exponent reduction for units>. Modulo fifteen, $\operatorname{ord}_{15}(7)=\lambda(15)=4<8=\varphi(15)$, so $2029=507\cdot4+1$ gives $7^{2029}\equiv7$ immediately. For base four the <multiplicative order> is only two, smaller even than $\lambda(15)$. A return at <exponent> eight alone does not prove that the <multiplicative order> is eight.<Orders of Units in Modular Arithmetic by Keith Conrad>[pp. 1–3, Definition 1.3, the warning on p. 2, Theorem 2.1, Corollary 2.2 and Theorem 2.4]{ref}
\Image[/euler-unit-powers-and-exponent-periods.png]
{title=Actual power periods, <Carmichael function> exponents and Euler return exponents}
{description=Each row lists powers from exponent zero through eight. Highlighted first returns identify <multiplicative orders>; the accompanying labels distinguish a chosen base's shortest period, the common exponent for all <units>, and <Euler's totient function>. Powers of the <nonunit> three modulo fifteen repeat after an initial term but never return to one at a positive exponent. The final calculation compares reduction of $2029$ modulo eight and modulo four.}
If the reduced <exponent> is zero, the rule gives $a^k\equiv a^0=1$, and still requires a <unit>. Applying it to the <nonunit> three would falsely predict $3^8\equiv3^0=1\pmod{15}$; the actual residue is six. For negative <exponents>, first interpret the power using a <modular multiplicative inverse>, as in <modular exponentiation>.
Back to article page
