<s>[INST] What is $\operatorname{ord}_{22}(5^6)$? 
Find $\operatorname{ord}_{22}(5^6)$.

So, basically we want to find:$$\operatorname*{arg\,min}_k 5^{6k} \equiv 1\pmod {22}$$
I found that $5^5 \equiv 1\pmod {22}$ so I know that for $k=5$ we have $5^{6k} \equiv 1 \pmod {22}$. Therefore, $\text{ord}(5^6) \le 5$.
I guess that I could proceed with the somewhat tedious checking:


*

*$k=4$: $(5^6)^4 \equiv (5^4)^6 \equiv 5^4 \equiv 9 \pmod {22}$

*$k=3$  $(5^6)^3 \equiv (5^3)^6 \equiv 5^3 \equiv 15 \pmod {22}$

*$k=2$  $(5^6)^2 \equiv (5^2)^6 \equiv 5^2 \equiv 3 \pmod {22}$

*$k=1$  $(5^6)^1 \equiv (5^1)^6 \equiv 5 \pmod {22}$


So $\text{ord}_{22}(5^6) = 5$.
Questions:


*

*Is that what I'm expected to do? Or is there a simpler way? (I had to use a calculator or to tediously calculate it myself)

*Why can we get rid of the exponent when we do modular arithmetic? (I actually used it along the proof) i.e. $$x \equiv a \pmod m \iff x^b \equiv a \pmod m$$ 

 [/INST] You have found that $5^5 \equiv 1 \pmod {22}$. So as $5^6 \equiv 5 \pmod {22}$. Then we must have $\text{ord}(5^6) = \text{ord}(5)$. But from the first equation we have that $\text{ord}(5) \mid 5$ and as $5$ is prime and $5^1 \not \equiv 1 \pmod {22}$ we must have that $\text{ord}(5^6) = \text{ord}(5) = 5$

Note that we used the fact that if $a^{k} \equiv 1\pmod {p}$, then $\text{ord}_p(a) \mid k$. This can be easily proven by the Division Algorithm. Let $k = \text{ord}_p(a)\cdot m + r$, where $0 \le r < \text{ord}_p(a)$. Then:
$$1 \equiv a^k \equiv (a^{\text{ord}_p(a)})^m \cdot a^r \equiv a^r \pmod {p} $$
So $r=0$, as $\text{ord}_p(a)$ is the smallest positive integer $t$ s.t. $a^t \equiv 1 \pmod {p}$ by definition
</s>