I want to know whether it's possible that there would exist $1\lt k\lt\phi(n)$ s.t. $a^{\phi(n)}\equiv 1\pmod n$, for a given $a$ and $n$? I need to prove/disprove it. I need some hints. (For title I meant minimum mod n.)
OK, seems it may be too easy for my question but may I also ask that how to find the minimum even if I know that $(a,n)=1$? i.e. I have to know the $k$ s.t. $a^k\equiv 1\pmod n,$ given $(a,n)=1$.
On
Hint 1:
If $a^{\phi(n)}\equiv 1 \pmod n$ and $\phi(n)$ is composite and $k|\phi(n)$ then Let $b = a^k$.
Then $b^{\frac {\phi(n)}k} = (a^k)^{\frac {\phi(n)}k}=a^{\phi(n)} \equiv 1 \pmod n$.
Hint 2:
$(-1)^2 \equiv 1 \pmod n$. So if $\phi(n) \ne 2$....
Hint 3:
$a^3 \equiv 1 \pmod {a^3 -1}$. Can you find any $a^3 -1$ so that $\phi(a^3 -1) > 3$?
=====
Euler's Theorem was never actually meant to be a way of finding the order of an element, least not directly. The fact that $a^{\phi(n)} \equiv 1 \pmod n$ for $a$ relatively prime to $n$ in no way means that $\phi(n)$ is the smallest order that such is true. In general, it rarely is!
Indeed, as $(a^k)^{\frac {\phi(n)}k}=a^k$ and $\phi(n)$ is never prime for $\phi(n) > 2$ for every element where $\phi(n)$ is the smallest power there are $a^k; k|\phi(n)$ where it isnt.
One useful tidbit. If $a^k\equiv 1 \pmod n$ then $k|\phi(n)$. That is useful for finding an order.
$\phi(7)=6$ but $2^3\equiv 1$(mod$7$).
Edit: As I know there is no general algorithm to find the least integer $k$ such that $a^k\equiv 1$(mod$n$). Though a fact that can help is that this $k$ must divide $\phi(n)$. Even more than that, this $k$ divides every integer $m$ such that $a^m\equiv 1$(mod $m$). You can try to prove it, that's a pretty easy exercise. So for example, given that we know that $\phi(7)=6$ we know that the minimum cannot be $4$ or $5$. It must be an integer which divides $6$. So that gives us less options which makes it a bit easier.