## HW Help: prove an element is primitive.

**Moderators:** gmalivuk, Moderators General, Prelates

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

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

Grob FTW,

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

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

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

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

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

### 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]

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.

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

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

No, that was the kind of hint that I was looking for.mike-l wrote:There's a small-ish list of powers you actually need to check... do you know which ones they are?

- 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:Anything up to p-1?jaap wrote:If g were not primitive, what could its order be?

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

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

### 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?

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

### 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).

### 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?

### 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?

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?

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

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

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.

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

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

Also, Yakk, your signature rocks.

Also, Yakk, your signature rocks.

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.

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.

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

### Who is online

Users browsing this forum: No registered users and 10 guests