Calculate the order of 3 modulo 257

Question

How on earth would you go about this? I would start with g is a primitive root then g^i congruent to 3 but then I get stuck thereafter.

Answer 1

The number $p=257$ is very special, because

• it is a prime, and
• $p-1=2^8$ is a power of a prime.

Lagrange's theorem then implies that the order of a non-zero coset modulo $p$ must also be a power of two. More precisely, the order is $2^k$ for some $k=0,1,2,\ldots,8$.

What this means is that all you need to do is repeated squaring. Calculate $3^2=9\pmod {257}$, $3^4=9^2=81\pmod{257}$, $3^8=81^2$ et cetera. If you haven't hit $1$ by the time you reach $3^{128}$ you know that the order is $256$.

---

If you have covered quadratic residues then you can take the further shortcut of observing that $3$ is not a quadratic residue modulo $257$. Therefore $3$ cannot be an even power of a primitive root $g$. Hence its order must be _____. You do need the law of quadratic reciprocity for this to go as smoothly as described.