Sum of Generators in p (1 Viewer)

[KeypadSDM]

Ok, I really, really, really, have no idea bout solving this one.

I've been doing it by hand for a while now, which is pretty bloody stupid of me when I could just use Excell. Anyway, I want to know if anyone knows how to prove this:

(Sum of Generators in p)(Mod p) = 0, 1 or -1

(Note p is a prime)

It's worked for the first 30 primes or so, but does anyone know how to prove it?

 

[KeypadSDM]

And no one is going to help me?

A generator is a number k such that:

(1,2,3,...,p-1)(Mod p) = (n^1,n^2,n^3,...,n^(p-1))(Mod P)

But not necissarily in that order.

For example in (Mod 7), 3 is a generator:

(1,2,3,4,5,6)

(3^1,3^2,3^3,3^4,3^5,3^6)
=(3, 2, 6, 4, 5, 1)

The same elements, just not in the same order.

 

[flyin']

It's only been about a day... =p

 

[KeypadSDM]

Originally posted by flyin'
It's only been about a day... =p

Yeah, but no one even posted a:

"What the hell are you talking about?"
Or an
"That's easy dude, you're an idiot"

 

[BlackJack]

Hmmm.... if I can find number theory book I should be able to help...

*phone-on-hold music*

Note: of course, by *help* I'm using a very limited definition, namely, not much at all.

 

[xiao1985]

uhm... y the words lyk prime.... generators appear familar to me... yet i haf no idea... wut they r....

 

[BlackJack]

hmmm... *brainstorm*
if we find one generator, we can find them all.
Suppose this generator is g. I know a g exists in every prime mod p, and I have no idea what proof it was.

for a series:
g, g^2, g^3,... , g^(p-2), g^(p-1)

g^(p-1)=1
observe that g^(p-2) is also a generator, and it is...
-----
Hey, wait, do you observe that all non-squares in certain/all prime mod p, other than p-1 if it is non-square, become generators?

note: squares, are any number in mod p that has a valid square root.

Well, forget I said that, its up until a point I think...

 

[Giant Lobster]

"What the hell are you talking about?"

this aint 4u right?

and this mod() function, ive seen it in programming, its to find remainders right? never seen it in 4u but.

 

[KeypadSDM]

I've noticed that onece you've found 1 generator, you've found them all. All the positions in the series (n^1, n^2, n^3, ..., n^(p-1)) which are co-prime with p-1 are the locations of generators.

That might help, but I'm still lost as to how the hell the sum of these numbers is always 0, 1 or -1.

 

[J0n]

I thought a generator was a number which would generate the numbers of the group if added to itself repeatedly. e.g 3 is a generator in Z₇ because:

3 mod 7 = 3
(3 + 3) mod 7 = 6
(3 + 3 + 3) mod 7 = 2
(3 + 3 + 3 + 3) mod 7 = 5
(3 + 3 + 3 +3 + 3) mod 7 = 1
(3 + 3 + 3 + 3 + 3 + 3) mod 7 = 4
(3 + 3 + 3 + 3 + 3 + 3 + 3) mod 7 = 0

Which gives you (3,6,2,5,1,4,0) - the elements of the group, in a different order.
.'. the generators of Z_p where p is a prime, would be all the numbers except 0.
.'. the sum of the generators would be equal to 1 + 2 + 3 + ... + (p-1) = p(p-1)/2
Since 2 is the only even prime number, the sum of its generators mod 2 = 1, for all the other primes it equals 0.

Are you talking about primitive roots?

 

[BlackJack]

...Yes, primitive roots is the other name.

We can say for certain, though, that for each generator found, it's multiplicative inverse is also a generator (and vice versa).

Also, generators must be non-square.

Hence, I think we can get a (very) limited proof.

We know that for p>=5, the sum of all the squares and the sum of the non-squares are both multiples of p.

Then, if all the non-squares bar -1 are generators, then the sum of the generators will be 1 mod p. Or, 0 mod p if -1 is a square (eg. if p = 5 or 17)
(and we stop here, until further discoveries.)

btw, if you want proofs of stuff I assumed I'll try post them.

 

[KeypadSDM]

Originally posted by BlackJack
generators must be non-square.

Yeah, I proved that as well. The proof is so elegant.

 

[BlackJack]

btw, is this an actual theorem/lemma/fact? i.e. has someone proved this...?

That being said, what's the largest prime you've tried?

I was piqued by mod 19, the non-generator/non-sq. pair 8 & -7 (12). Haven't gone on excel yet, so just using the notes I had last week.

 

[turtle_2468]

Been away for a while.. and usually by the time I get to a post someone else has got a proof for it... gah.
Hmm... didn't work. I don't think it's going to be easy...
I'll figure out something.

 

[turtle_2468]

For p congruent to 1 mod 4, k being a generator means that -k is a generator. Hence the result.
Yet to figure out for 3 mod 4, but it's getting late, more later...

 

[BlackJack]

lol. It's actually much easier to get sidetracked into other relations between addition and multiplicative properties of these fields.

(e.g.)
I *think*, numbers in each ord_p(n) sum to a multiple of p (or maybe, just maybe, within 1), but I'm not conclusive on that yet.

Of course, this has prob. been seen by Keypad already, and I have no way of proving it.

 

[turtle_2468]

Just in case there are those who didn't follow my comment above, note that generators k have property of k^((p-1)/2) cong to -1 mod p

 

[KeypadSDM]

Originally posted by turtle_2468
Just in case there are those who didn't follow my comment above, note that generators k have property of k^((p-1)/2) cong to -1 mod p

It has to, there's no other way or squaring k^((p-1)/2) will give you the required answer of 1 without repeating a number

But remember just because k^((p-1)/2) = -1 doesn't mean k's a generator.

 

[AK Gumbi]

riiiiiiiiiiiiiiigggggghhhhhhhttt....

 

[ND]

Originally posted by AK Gumbi
riiiiiiiiiiiiiiigggggghhhhhhhttt....

Exactly what i was thinking... the only generator i know anything about involves a stator and a rotor...