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?
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.