# Proof that if $\gcd(a,n) = 1$, then $a^k \equiv a^{k \pmod{\phi(n)}} \pmod n$

From Euler's theorem I know that $$a^{\phi(n)} \equiv 1 \pmod n$$ if $$\gcd(a,n) = 1$$. However I can't find any proof/explaination of the proof in the title.

Hint: Consider that the the only thing that changes from $$a^k$$ to $$a^{k\!\pmod{\phi(n)}}$$ is that the exponents differ by a multiple of $$\phi(n)$$.

• Since $\Z_n^*$ is a finite set, than we can define a number $y$ such that $a^y \equiv 1 \pmod n$, from euler's theorem we know that $y = \phi(n)$, and this also means that $a^{k \pmod{\phi(n)}} \equiv a^k \pmod n$ for a generic $k$ , since $\phi(n) \mid k$ (?) – meowmeowxw Sep 30 at 20:06
• Not quite. And a bit more complicated than I was thinking. We do not know that $y=\phi(n)$. We know that setting $y=\phi(n)$ makes $a^y\equiv 1$, but the converse doesn't hold (for instance, if $a=1$, then any $y$ will work). However, note that if we set $y=\phi(n)$, then elementary exponent properties give us that $a^k=(a^y)^j\cdot a^{k\!\pmod{\phi(n)}}$ for some integer $j$. Applying modulo $\phi(n)$ to this equality and using Euler's theorem gives you your result. – Arthur Sep 30 at 20:12

The key idea is to use modular order reduction on exponents as in the Theorem below. We can find small exponents $$\,e\,$$ such that $$\,a^{\large \color{#c00}e}\equiv 1\,$$ either by Euler's totient or Fermat's little theorem (or by Carmichael's lambda generalization), along with obvious roots of $$\,1\,$$ such as $$\,(-1)^2\equiv 1.$$

Theorem $$\ \$$ Suppose that: $$\,\ \color{#c00}{a^{\large e}\equiv\, 1}\,\pmod{\! m}\$$ and $$\, e>0,\ n,k\ge 0\,$$ are integers. Then

$$\qquad\ \ \ \ n\equiv k\pmod{\! \color{#c00}e}\,\Longrightarrow\,a^{\large n}\equiv a^{\large k}\pmod{\!m}.\:$$ The converse holds if $$\:\color{#c00}e = {\rm ord}\,a,\,$$ i.e.

$$\qquad\ \ \ \ n\equiv k\pmod{\! \color{#c00}e}\,\Longleftarrow\,a^{\large n}\equiv a^{\large k}\pmod{\!m}\$$ and $$\, a\,$$ has order $$\,\color{#c00}e\,$$ mod $$\,m$$

Proof $$\$$ Wlog $$\,n\ge k\,$$ so $$\,a^{\large n-k} \color{#0a0}{a^{\large k}}\equiv \color{#0a0}{a^{\large k}}\!\iff a^{\large n-k}\equiv 1\iff n\equiv k\pmod{\!e}\,$$ by this Corollary, where we cancelled $$\,\color{#0a0}{a^{\large k}}\,$$ using $$\,a^{\large e}\equiv 1\,\Rightarrow\, a\,$$ is invertible so cancellable (cf. below Remark).

Corollary $$\ \ \bbox[7px,border:1px solid #c00]{\!\bmod m\!:\,\ \color{#c00}{a^{\large e}\equiv 1}\,\Rightarrow\, a^{\large n}\equiv a^{\large n\bmod \color{#c00}e}}\,\$$ by $$\ n\equiv n\bmod e\,\pmod{\!\color{#c00}e}$$

Remark  If you are familiar with modular inverses then it is not necessary to restrict to nonnegative powers of $$\,a\,$$ above since $$\,a^{\large e}\equiv 1,\ e> 0\,\Rightarrow\,$$ $$a$$ is invertible by $$\,a a^{\large e-1}\equiv 1\,$$ so $$\,a^{\large -1}\equiv a^{\large e-1}$$.