## HW Help: prove an element is primitive.

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

the tree
Posts: 801
Joined: Mon Apr 02, 2007 6:23 pm UTC
Location: Behind you

### HW Help: prove an element is primitive.

If I'm told that that [imath]g[/imath] is a primitive element of [imath]\mathbf{Z}_p[/imath] where [imath]p[/imath] is 1. a prime, 2. pretty big - what can I do to show that [imath]g[/imath] really is a primitive element? Short of a fuck off spreadsheet (the numbers quickly get too big for excel to handle), is there a relevant theorem I should be looking up that will verify this? All the reading that I've done only seems to tell me that there's no way to find a primitive element, beyond trial and error, and I can't find a method for checking that an element is primitive beyond brute force.

OverBored
Posts: 284
Joined: Mon Dec 10, 2007 7:39 pm UTC

### Re: HW Help: prove an element is primitive.

Can I just check, that by [imath]\mathbf{Z}_p[/imath] you mean integers modulo p correct?
G4!!

Grob FTW,

Hello. Smithers. You're. Quite good. At. Turning. Me. On.

the tree
Posts: 801
Joined: Mon Apr 02, 2007 6:23 pm UTC
Location: Behind you

### Re: HW Help: prove an element is primitive.

Yes. \mathbb didn't seem to be working so I went for the next best thing.

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: HW Help: prove an element is primitive.

If g were not primitive, what could its order be?

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: HW Help: prove an element is primitive.

There's a small-ish list of powers you actually need to check... do you know which ones they are?

You can keep your numbers small in excel by successively squaring and reducing mod p, then multiplying the appropriate [imath]g^{2^i}[/imath] values (eg [imath]g^{1000} = g^{512}g^{256}g^{128}g^{64}g^{32}g^8[/imath]
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

the tree
Posts: 801
Joined: Mon Apr 02, 2007 6:23 pm UTC
Location: Behind you

### Re: HW Help: prove an element is primitive.

jaap wrote:If g were not primitive, what could its order be?
Anything up to p-1?
mike-l wrote:There's a small-ish list of powers you actually need to check... do you know which ones they are?
No, that was the kind of hint that I was looking for.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: HW Help: prove an element is primitive.

the tree wrote:
jaap wrote:If g were not primitive, what could its order be?
Anything up to p-1?

What do you know about the order of an element and the order of a group?
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

the tree
Posts: 801
Joined: Mon Apr 02, 2007 6:23 pm UTC
Location: Behind you

### Re: HW Help: prove an element is primitive.

Okay I feel the answer is trying to bite me on the nose but I'm not just seeing it. Beyond what those terms mean, not much. g is primitive if it has order p-1, because then it has the same amount of distinct powers as there are elements in the group - so if it's not primitive then it has order less than p-1?

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: HW Help: prove an element is primitive.

Yes, that's true. But can they be ANY order, or only particular ones? Maybe try a few examples... check the order of all the elements in [imath]\mathbf Z_{11}[/imath]. Do you notice anything?
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

the tree
Posts: 801
Joined: Mon Apr 02, 2007 6:23 pm UTC
Location: Behind you

### Re: HW Help: prove an element is primitive.

2,6 or 10 apparently. 10 being the primitive elements. I'm afraid I still can't see where the 2 and 6 come from. (I'm tempted to say things like 2*6=1 mod 11 but that feels like shooting in the dark).

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: HW Help: prove an element is primitive.

the tree wrote:2,6 or 10 apparently. 10 being the primitive elements. I'm afraid I still can't see where the 2 and 6 come from. (I'm tempted to say things like 2*6=1 mod 11 but that feels like shooting in the dark).

Are you sure about the 6?

the tree
Posts: 801
Joined: Mon Apr 02, 2007 6:23 pm UTC
Location: Behind you

### Re: HW Help: prove an element is primitive.

Make that five. Apparently all this mathsing it ruining my ability to count.

So okay, a penny has dropped, but possibly in the entirely wrong place - is it something to do with the elements can only have orders that are divisors of p-1? If so, does that urm... have a name I can look up or something?

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: HW Help: prove an element is primitive.

the tree wrote:Make that five. Apparently all this mathsing it ruining my ability to count.

So okay, a penny has dropped, but possibly in the entirely wrong place - is it something to do with the elements can only have orders that are divisors of p-1? If so, does that urm... have a name I can look up or something?

Lagrange's Theorem: If you have a subgroup of a group, then the order of a subgroup of divides the order of the group.
Here you have a group of order p-1 (the non-zero elements of Zp form a group under multiplication). Any element g generates a cyclic group of order o(g), which therefore must divide p-1.

the tree
Posts: 801
Joined: Mon Apr 02, 2007 6:23 pm UTC
Location: Behind you

### Re: HW Help: prove an element is primitive.

THANKYOU

Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: HW Help: prove an element is primitive.

How to do it on paper.

Factor (p-1) into primes and powers of primes.

Build a table of g^1, g^2 mod p, (g^2)^2 mod p, ((g^2)^2)^2 mod p, etc, until (...(((2)^2)^2)...)^2 is greater than (p-1). (this takes log_2 steps).

Examine all of the factors of (p-1). Take the product of the above powers-of-g that "adds up" to that particular factor of (p-1). Is it 1?

...

Now can we do better than the above? Well, the factors of (p-1) have structure, so we could try using that structure to do less multiplication (ie, if p-1 is 20, we can do 2, 4 and 5, and then take 4*5 to get 10). I don't think this is significant, but it might be in pathological cases?

How big can the number of factors of p-1 get? Hmm. I'd intuitively guess "logarithmic", but I cannot think of a proof off of the top of my head. Anyone?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: HW Help: prove an element is primitive.

You can also restrict yourself to checking (p-1)/q where q is a prime dividing (p-1), since any order must divide one of those. The number of primes dividing p-1 is certainly logarithmic at most... I don't feel like chugging through the PNT to figure out how much better it is than logarithmic.

Last edited by mike-l on Fri Nov 12, 2010 8:47 pm UTC, edited 2 times in total.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: HW Help: prove an element is primitive.

Ah, good point. D'oh.

And the number of primes q such that q | n is ... roughly the inverse of product of the first n primes.
2*3*5*7*11*13*17*19*...
and that is going to grow somewhat faster than n!, let alone e^n.

Regardless, by this point the expensive part is going to be factoring p-1.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.