1. ## Find primitive roots.

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.

2. If 6 is a primitive root in F_251 then $\displaystyle 6^{-1}\equiv 6^{249}$ is also a primitive root. With some modulo-calculations it shouldn't be too hard to find $\displaystyle 6^{249} (\text{mod}) 251$

3. Originally Posted by Dinkydoe
If 6 is a primitive root in F_251 then $\displaystyle 6^{-1}\equiv 6^{249}$ is also a primitive root. With some modulo-calculations it shouldn't be too hard to find $\displaystyle 6^{249} (\text{mod}) 251$
What did you use there, like theorem wise?
Thanks for your help, im still struggling to understand this.

4. since p=251 we have that $\displaystyle \mathbb{F}_p^*$ is a cyclic group of order $\displaystyle p-1$

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 $\displaystyle a$ is a primitive root, $\displaystyle a^{-1}$ must also be a primitive root.

and $\displaystyle a^{-1}= a^{-1}a^{p-1}= a^{p-2}$

In this case $\displaystyle 6^{249}$

5. Originally Posted by simpleas123
What did you use there, like theorem wise?
Thanks for your help, im still struggling to understand this.
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 $\displaystyle 6^{249}\ (\text{mod}\ 251)$, 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.

6. Originally Posted by undefined
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 $\displaystyle 6^{249}\ (\text{mod}\ 251)$, 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.
Thanks for your help guys, ill re-attempt it as soon as ive finished dinner

7. Originally Posted by simpleas123
Thanks for your help guys, ill re-attempt it as soon as ive finished dinner
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:

$\displaystyle 249 \equiv 1\ (\text{mod}\ 2)$

Current binary string: 1

$\displaystyle \bigg\lfloor\frac{249}{2}\bigg\rfloor = 124$

$\displaystyle 124 \equiv 0\ (\text{mod}\ 2)$

Current binary string: 01

$\displaystyle \bigg\lfloor\frac{124}{2}\bigg\rfloor = 62$

$\displaystyle 62 \equiv 0\ (\text{mod}\ 2)$

Current binary string: 001

$\displaystyle \bigg\lfloor\frac{62}{2}\bigg\rfloor = 31$

$\displaystyle 31 \equiv 1\ (\text{mod}\ 2)$

Current binary string: 1001

$\displaystyle \bigg\lfloor\frac{31}{2}\bigg\rfloor = 15$

$\displaystyle 15 \equiv 1\ (\text{mod}\ 2)$

Current binary string: 11001

$\displaystyle \bigg\lfloor\frac{15}{2}\bigg\rfloor = 7$

$\displaystyle 7 \equiv 1\ (\text{mod}\ 2)$

Current binary string: 111001

$\displaystyle \bigg\lfloor\frac{7}{2}\bigg\rfloor = 3$

$\displaystyle 3 \equiv 1\ (\text{mod}\ 2)$

Current binary string: 1111001

$\displaystyle \bigg\lfloor\frac{3}{2}\bigg\rfloor = 1$

$\displaystyle 1 \equiv 1\ (\text{mod}\ 2)$

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

$\displaystyle 6^{249} = 6^{(1+8+16+32+64+128)} = 6^1\cdot 6^8\cdot 6^{16}\cdot 6^{32}\cdot 6^{64}\cdot 6^{128}$

Here's where it all comes together.

$\displaystyle 6^1 \equiv 6\ (\text{mod}\ 251)$

$\displaystyle 6^2 \equiv 6\cdot6 \equiv 36\ (\text{mod}\ 251)$

$\displaystyle 6^4 \equiv 36\cdot36 \equiv 1296 \equiv 41\ (\text{mod}\ 251)$

$\displaystyle 6^8 \equiv 41\cdot41 \equiv 1681 \equiv 175\ (\text{mod}\ 251)$

You can see where this is going. There aren't so many steps left, and then you'll have your final answer.

8. 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.