2
$\begingroup$

The above identity holds for any integer $a$. Since my solution(?) does seem neither elegant nor rigorous enough, I want to get some advice to improve it.

My solution: If $(a,m)=1$, this identity is obvious from Euler's Theorem. So, assume that $(a,m)\neq 1$.

Let $g=(a,m)$, and then $\exists k, n\in\mathbb{Z}\:s.t. (k,n)=1$, $a=gk$ and $m=gn$. So the identity can be rewritten as the following:

$$(gk)^m\equiv (gk)^{m-\phi(m)} \pmod{gn}$$ Dividing the both sides by $k$, we obtain: $$g^{m}k^{gn-1}\equiv g^{m-\phi(m)}k^{gn-\phi(gn)-1} \pmod{n}$$ $$g^{m}\equiv g^{m-\phi(m)}k^{-\phi(g)\phi(n)}\equiv g^{m-\phi(m)}\pmod{n}...(*)$$

Thus, we can reduce the identity to the identity (*), and as we continue this process for finite times, we will eventually reach at Euler's identity with $(a,m)=1$.

$\endgroup$
2
$\begingroup$

Hint Let $m=p_1^{\alpha_1}....p_k^{\alpha_k}$.

It suffices to prove that

$$ a^m\equiv a^{m-\phi(m)} \pmod{p_i^{\alpha_i}}$$

Now split the problem in two cases: $p_i |a$ and $p_i \nmid a$. The second case is almost identical with your first case...

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