Q1. How to find primitive root and generators modulo $97$?
Q2. Is there anyway to find the generators modulo $97$ in an easy way?
Asked
Active
Viewed 796 times
1
-
For Q1, why not try the residue class $k = 2, \dots \frac{97 - 1}{2}$? If $k^{97 - 2} \ne 1 \bmod 97$, then $\operatorname{ord}_{\mathbb{Z}/(97 - 1)\mathbb{Z}} k = 97 - 1$, which is a primitive root / generator. – Alex Vong Nov 09 '17 at 09:53
-
https://math.stackexchange.com/questions/124408/finding-a-primitive-root-of-a-prime-number – lab bhattacharjee Nov 09 '17 at 09:54
-
@AlexVong That's not right. $2^{95}\neq 1$, but the [order of $2$ is $48$](http://www.wolframalpha.com/input/?i=order+of+2+modulo+97) (in fact, any element with an even order would satisfy $k^{97-2}\neq 1$). – Arthur Nov 09 '17 at 09:55
-
What is the difference between primitive roots and generators? – lhf Nov 09 '17 at 09:58
-
@Arthur You are right, we should instead find the factors of $97 - 1$, called them $a_i$, and check $k^{a_i} \ne 1$. – Alex Vong Nov 09 '17 at 10:06
-
@lhf I think they are just different names. – Alex Vong Nov 09 '17 at 10:10
-
hi sir i dont get it could u add a site Or book that should help me out in this i would be very thank ful – hassampir pir Nov 09 '17 at 10:12
-
1https://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots – Alex Vong Nov 09 '17 at 10:15
2 Answers
2
No efficient method is known for finding primitive roots, though typically there is a small one.
For $97$, the smallest primitive root is $5$. You need to test $2$ and $3$ but not $4$ since $2$ fails.
Once you find a primitive root mod $p$, call it $g$, then all other ones are $g^k$ with $k$ coprime with $p-1$.
lhf
- 212,426
- 15
- 227
- 538
0
HINT
First notice that $97$ is prime.
Now prove-or take for granted if you must-that $x\neq 0$ is a primitive element modulo $97$ iff $x^{32}\equiv 1\operatorname{mod} 97$ and $x^{48} \equiv 1\operatorname{mod}97.$
MathematicianByMistake
- 5,342
- 2
- 16
- 34