Euler theorem's inverse proposition in number theory

$\begingroup$

The Euler theorem

$\mathbf (a,n)=1 \Rightarrow a ^\phi$ = $ 1(mod n)$ ($ \phi $ means $ \phi(n)$)

Inverse of the above proposition that

$\mathbf a ^\phi $ = 1(mod n) $\Rightarrow $ (a,n)=1

I'm tried to find the counterexamples of the inverse of Euler theorem is not true.

But Every example what I've take like unit group $U_n = \{\ n \vert \ (a,n)=1 \}\ $ where n=5,7,... I failed.

please give me some hints.

Plus If the inverse of Euler proposition is true, How Could I prove that?

$\endgroup$ 1

1 Answer

$\begingroup$

If $ a^{\phi(n)} \equiv 1 \mod n \\ $,

by definition of modular arithmetic, there exists $ k \in \mathbb Z $ such that $a^{\phi(n)}= 1+ n k \\$,

hence if $c$ is any positive common divisor of $a^\phi(n)$ and $n$,

then $c$ divides $a^{\phi(n)}- n k$, which is $1$,

hence $c=1$,

hence $a$ and $n$ are relatively prime.

$\endgroup$ 1