$3$ is the primitive root for $mod$ $961$. Let $a^m \equiv 3^{24} \pmod {961}$ for primitive root, $a(\neq 3)$ for $mod$ $961$. Find the maximum integer $m$ satisfying $0\leq m <930$. (Here $961=31^2$).
Since $a$ is primitive root, $\exists$ $k$ $s.t.$ $a^k \equiv 3 \pmod {961} $ and $gcd(k,930)=1$. Clearly $gcd(k,930)=1$, There is a inverse of $k$ in ring $\mathbb{Z}_{930}$. So we can derive $m\equiv 24k \pmod{930}$ from $a^{m} = 3^{24} \equiv a^{24k} \pmod {961} $. More simplify this $m\equiv 6k \pmod{930} $. From here, my question starts. The answer sheet suggested $924$ is the maximum value. I can't agree that because $960 = 6\cdot 160$ and $1 \neq (160,930)$. Considering $930$ case $k$ would be $160$. But As I formerly said, $k$ must be coprime with the $930$. But $160$ isn't. So my answer is $906 (= 6\cdot 151)$. Is my answer right?
Best regards
p.s.) The reason for the "$m\equiv 6k \pmod{930} $".
Considering the index(discrete log), $ind_a$
$a^{m} = 3^{24} \equiv a^{24k} \pmod {961} \Rightarrow m\equiv24k\pmod {930}$. So the $m\in\langle 24\rangle \subset \mathbb{Z}_{930}$. Plus Since the $gcd(24,930)=6$, $\langle 24\rangle = \langle 6\rangle$. Therefore $m\in\langle 6\rangle \subset \mathbb{Z}_{930}$. That is $m\equiv6k \pmod {930}$.Plus from the $(k,930)=1$, Able to get my conclusion.
Best Answer
If $a$ is primitive and $a^m$ has order $465=930/(24,930)=930/6=155$, then $(m,930)=6$.
The biggest multiple of $6$ not divisible by $31$ or $5$, and $\lt930$, is $924$.
There will be a primitive $a$ for which $a^{924}\equiv 3^{24}\pmod{961}$.