If 6 is a primitive root in F_251 then is also a primitive root. With some modulo-calculations it shouldn't be too hard to find
Hey all im stuck on this question, been attempting it for ages and i have no clue how to tackle it because the mod is so high.
"You are given 6 is a primitive root in F_251. Find Another"
My attempt was firstly to find how many primitive roots thier are in 251.
I found this to be 100.
But testing all the numbers would be far too long for a 5 mark question [Past exam paper], so i was wondering how i would tackle this problem.
Cheers people
David.
since p=251 we have that is a cyclic group of order
Hence a primitive root in this group has order p-1.
And it's easy to show that a group element has the same order as his inverse. Thus if is a primitive root, must also be a primitive root.
and
In this case
From Wikipedia article, "Gauss proved that for any prime number p (with the sole exception of 3) the product of its primitive roots is ≡ 1 (mod p)."
251 is prime.
As for finding , it can be done on paper using the binary representation of 249. The method is mentioned here, but it's kind of hard to follow, I remember a site that has lots of examples but am having a hard time with Google search at the moment.
I think I bookmarked that site I mentioned and it's now a dead link... since I can't find a comparable site, I'll just write an explanation.
First to get the binary representation of 249. On paper you can proceed as follows:
Current binary string: 1
Current binary string: 01
Current binary string: 001
Current binary string: 1001
Current binary string: 11001
Current binary string: 111001
Current binary string: 1111001
Current binary string: 11111001
You can verify that this is the correct binary representation.
The reason we want this is because we can now write
Here's where it all comes together.
You can see where this is going. There aren't so many steps left, and then you'll have your final answer.
It might also interest you to know that modular inverses can be found via the extended Euclidean algorithm. See here. It's basically the same way you solve linear Diophantines, if you've ever done that.
Edit: I meant linear Diophantines in two variables, just for clarity.