1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ 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$ (?) $\endgroup$ – meowmeowxw Sep 30 at 20:06
  • 2
    $\begingroup$ 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. $\endgroup$ – Arthur Sep 30 at 20:12
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.