What is $\operatorname{ord}_{22}(5^6)$?

Question

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:

1. $k=4$: $(5^6)^4 \equiv (5^4)^6 \equiv 5^4 \equiv 9 \pmod {22}$
2. $k=3$ $(5^6)^3 \equiv (5^3)^6 \equiv 5^3 \equiv 15 \pmod {22}$
3. $k=2$ $(5^6)^2 \equiv (5^2)^6 \equiv 5^2 \equiv 3 \pmod {22}$
4. $k=1$ $(5^6)^1 \equiv (5^1)^6 \equiv 5 \pmod {22}$

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

Questions:

1. 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)
2. 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$$

Answer 1

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

Answer 2

First observe that \begin{eqnarray*} 5^6 \equiv 5 \pmod{22}. \end{eqnarray*} So we only need to calculate powers of $5$ modulo $22$, they are $5,3,15,9,1$ (by tedious calculation), the minimal value of $k$ is $\color{red}{5}$.

Answer 3

By the Chinese remainder theorem, it is enough to find the order of $5^6$ $\!\!\pmod{2}$ (which is obviously $1$) and the order of $5^6\equiv5$ $\!\!\pmod{11}$. Since $5$ is a quadratic residue $\!\!\pmod{11}$, due to $$\left(\frac{5}{11}\right)=\left(\frac{11}{5}\right)=\left(\frac{1}{5}\right)=1$$ the order of $5\pmod{11}$ is five and that is also the order of $5^6\pmod{22}$.