# Find the maximum integer, $m$ which is $a^m \equiv 3^{24} \pmod {961}$

$$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.

• I think your answer is correct because $\phi(31^2)=930\Rightarrow 3^{930}\equiv 1\bmod 31^2$ we can rewrite: $3^{906}\equiv 1\bmod 31^2$ and $3^{24}\equiv 1\bmod 31^2$, the multiplication of these two gives $3^{930}\equiv 1\bmod 31^2$ , so maximum of m can be $906$. Commented Jul 22, 2022 at 16:47
• @sirous, Thanks for comment. But Since $3$ is the primitive root, I think "$3^{24} \equiv 1 \pmod {961}$" does not hold. Considering the definition of the primitive roots, Order of the $3$ should be $930$ not the any divisor of the $24$. Commented Jul 22, 2022 at 23:18
• You can't say $k$ has a multiplicative inverse in $\Bbb Z_{961}$ unless $(k,961)=1$. Commented Jul 23, 2022 at 2:15
• Why does $m\equiv 6k\pmod{930}?$ Commented Jul 23, 2022 at 2:29
• @Cpc, noob that was typo. My intent was $\mathbb{Z}_{930}$. Sorry. Second if we get the discrete log for $a$ , we can get the $m\equiv 6k$ Commented Jul 23, 2022 at 3:18

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}$$.
• Why does $a^m$ has order $465$? Following your comment, I think the order of it have to be $40$. Commented Jul 23, 2022 at 0:16
• O.K. As you can see the question requires the "$m$" provided that $a^{928} \equiv 3^{24}$ Commented Jul 23, 2022 at 0:32
• Oops, $(930,24)=6$. Commented Jul 23, 2022 at 0:44
• So, $a^m$ has order $155$. Sorry. Commented Jul 23, 2022 at 0:47
• $$3^{930}\equiv 1\bmod 31^2$$ Multiplying both sides by $3^{24}$ we get: $$3^{954}\equiv 3^{24}\bmod 31^2$$ $954=924+30\Rightarrow 954\equiv 924\bmod 30$, so we may write: $$3^{924}\equiv3^{954}\equiv 3^{24}\bmod 31^2$$ Commented Jul 23, 2022 at 5:43