# Show that 3 is a primitive root mod 257

So we know the order of 3 must be 256 yet this is too big number to calculate by hand (or calculator) so we use the fact that there exists another primitive root, g, such that 3 is congruent to g^i mod 256.

Then we have 3^256 congruent to g^(i*256) mod 257 where i is between 1 and 255.

I am stuck on how to proceed from here, my notes say: "As 256 is a power of 2, order of 3 is 256 if and only if i is odd."

I don't get this statement; surely g^(i*256) is congruent to 1 mod 257 for any power that is divisible by the order of g so 256 therefore shouldn't i be able to take any value?

• $3$ is a quadratic non-residue of $257$ and that's enough in this case ($256$ is a power of $2$) to ensure that it's a primitive root. – Lord Shark the Unknown May 6 '17 at 19:43
• The point has nothing to do with $g^{i*256}$. It has to to do with $g^{i}$. If $i$ is even then $3^{128}=g^{128i}\equiv 1$, so $3$ can't have order $256$. – Thomas Andrews May 6 '17 at 19:43
• @ThomasAndrews if i was even (e.g. =2) then g^(128*i) would be g^256 which is 1 by defn? – MargaretM May 6 '17 at 20:12

As the comments indicate, $i$ must be odd since $257$ is prime, $257-1=256=2^8$, and the multiplicative order of any element must be a power of $2$. To find the order of $3$ is not so hard even by hand. You find that $3^{16}\equiv -8 \mod 257$, then $3^{64}\equiv -16\mod 257$ and you are practically done.