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)?

Printable View

- Oct 15th 2008, 12:48 AMRichmondPrimitive 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 PMJhevon
- Oct 15th 2008, 04:44 PMThePerfectHacker
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 PMRichmond
thank you.