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

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