<s>[INST] How can i get the least $n $ such that $17^n \equiv 1 \mod(100$)? When I solve the problem:
$17^{2018}\equiv r \pmod{100} $
used Euler theorem since $\gcd (17,100)=1$ and so
$\phi(100)=40$ 
and so
$17^{40}\equiv 1 \pmod{100}$
But i also found that:  $17^{20}\equiv 1 \pmod{100}$
How can i get the least n such that $17^{n}=1\pmod{100} $?
Is there any theorm or generalization to this problem? 
Thanks for your help 
 [/INST] Euler's theorem says that if $\gcd(a,n)=1$ then $a^{\phi(n)} \equiv 1 \pmod n$ but Euler's theorem does not say $\phi(n)$ is the smallest such number.[1]
But we can easily verify the smallest such power (called the order of $a$) will have to be a factor of $\phi(n)$ [2]
So test $17^k$ where $k|40$.
The powers twos are easy to calculate through repeated squaring.
$17^2 \equiv 89\pmod {100}$ and $17^4 \equiv 89^2\equiv (-11)^2 \equiv 21 \pmod {100}$ and $17^8\equiv 21^2 \equiv 41\pmod {101}$.
The multiples of $5$ are harder but ... well, check this out.
$17^{20} \equiv 21^5 \equiv (20+1)^5 \equiv 20^5 + 5*20^4 + 10*20^3 + 10*20^2 + 5*20 + 1\equiv 0+0+0+0+100 + 1 \equiv 1 \pmod {100}$.
Similarly $17^{10} \equiv (-11)^5 \equiv -(11)^5 \equiv -(10^5 + 5*10^4 + 10*10^3 + 10*10^2 + 5*10 + 1) \equiv -51 \equiv 49\pmod {101}$
Which means the smallest such power is $20$[3]
====
[1] Obviously if $a \equiv b^{k}$ and $k|\phi(n)$ then $a^{\frac {\phi(n)}k} = b^{\phi(n)}\equiv 1 \pmod n$ so this simply can't be true
Taking this to extreme:  Obviously $\gcd(1,n) =$ and $1^1 \equiv 1 \pmod n$.
[2] If the order of $a$ is $k < \phi(n)$ and $k\not \mid \phi(n)$ then $\phi(n) = b*k + r$ for some $b$ and $0< r < k$.
So $1\equiv a^{\phi(n)}\equiv (a^{k})^ba^r \equiv 1^ba^r\equiv a^r\pmod n$.  But we said $k$ was the least such power so that is a contradiction.
So the order of $a$ must divide $\phi(n)$.
[3]Any factor of $40$ that is less than $20$ is either a power of two (which we've ruled out) or a multiple of $5$.    any smaller multiple of $5$ divides $10$.  If $17$ to such a smaller power were equivalent to $1$ then $17^{10}$ would also be and it isn't.
</s>