# Primitive Roots

• Oct 15th 2008, 12:48 AM
Richmond
Primitive Roots
Find a primitive root modulo 89 and use the answer to find a number a so that the order of a modulo 89 is 8.

Does this mean

a^8=1 (mod 89)?
• Oct 15th 2008, 04:11 PM
Jhevon
Quote:

Originally Posted by Richmond
Find a primitive root modulo 89 and use the answer to find a number a so that the order of a modulo 89 is 8.

Does this mean

a^8=1 (mod 89)?

if you are talking multiplicative order, then yes
• Oct 15th 2008, 04:44 PM
ThePerfectHacker
Quote:

Originally Posted by Richmond
Find a primitive root modulo 89 and use the answer to find a number a so that the order of a modulo 89 is 8.

We use the result that the primes $\displaystyle p>3$ which have $\displaystyle 3$ as a quadradic residue are of the form $\displaystyle 12k\pm 1$. This result can be established using quadradic reciprocity. Since $\displaystyle 89$, a prime, does not have this form it means $\displaystyle (3/89) = -1$. Thus, $\displaystyle 3^{(89-1)/2}= 3^{44} \equiv -1 (\bmod 89)$ by Euler's criterion. Let $\displaystyle k$ be order of $\displaystyle 3$ then $\displaystyle k|(89-1) \implies k|88$. But if $\displaystyle k=2,4,8,11,22,44$ then $\displaystyle k|44$ and it would follow that $\displaystyle 3^{44}\equiv 1(\bmod 89)$ which is a contradiction. Therefore, $\displaystyle k=88$ and consequently $\displaystyle 3$ is a primitive root of $\displaystyle 89$.

It follows that $\displaystyle 3^{11} \equiv 37$ has order $\displaystyle 8$ mod $\displaystyle 89$.
• Oct 15th 2008, 06:58 PM
Richmond
thank you.