Find primitive roots.

**simpleas123** · May 6th 2010, 07:07 AM

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.

**Dinkydoe** · May 6th 2010, 07:24 AM

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

**simpleas123** · May 6th 2010, 07:41 AM

Originally Posted by Dinkydoe

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

What did you use there, like theorem wise?
Thanks for your help, im still struggling to understand this.

**Dinkydoe** · May 6th 2010, 07:59 AM

since p=251 we have that $\mathbb{F}_p^*$ is a cyclic group of order $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 $a$ is a primitive root, $a^{-1}$ must also be a primitive root.

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

In this case $6^{249}$

**undefined** · May 6th 2010, 08:05 AM

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

**simpleas123** · May 6th 2010, 08:09 AM

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 $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

**undefined** · May 6th 2010, 08:26 AM

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:

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

Current binary string: 1

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

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

Current binary string: 01

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

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

Current binary string: 001

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

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

Current binary string: 1001

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

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

Current binary string: 11001

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

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

Current binary string: 111001

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

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

Current binary string: 1111001

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

$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

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

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

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

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

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

**undefined** · May 6th 2010, 08:32 AM

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.

Thread: Find primitive roots.

LinkBack

Thread Tools

Display

Find primitive roots.

Similar Math Help Forum Discussions

Primitive Roots

primitive roots

find primitive roots for mod

Primitive Roots

Primitive roots

Search Tags