Primitive Roots

[akruppa]

Originally Posted by Numbers

By neutral element I take it you mean the identity element?

Yes

So that in Z/7*, ord(2) = 3, since 2^3 = 1(mod 7)?

Yes. Strictly speaking, you also need to state that 3 is the smallest positive integer k so that 2^k ≡ 1. I.e. 2^1 ≡ 2 !≡ 1, 2^2 ≡ 4 !≡ 1, 2^3 ≡ 8 ≡ 1, therefore ord(2) = 3.

Once you have proven Lagrange's theorem you have a much easier time proving that k is the smallest integer so that a^k ≡ 1, because you only need to check that the congruence does not hold for proper divisors of k, not all integers below it.

Alex

[Numbers]

Ok, I get it now. Thank you.

[akruppa]

In fact, you don't need Lagrange's theorem...

suppose a^[I]k[/I] ≡ a^[I]l[/I] ≡ 1, 0 < k < l.
Multiply both sides by a^-[I]k[/I], then a^{[I]l[/I]-[I]k[/I]} ≡ 1.
So we can set k'=k, l'=l-k (swapped if k'>l'), then repeat unless l'=k'.

If l'=k', then k' = gcd(l,k), the above is just Euclid's algorithm.

Thus, if n is the order of an element a, then for all k: a^[I]k[/I] ≡ 1 there exists a d so that d|n and d|k, but d cannot be smaller than n by definition of order, so d=n and n|k.

It is obvious that a^[I]kn[/I] ≡ 1 for all integers k.

Hence, a^[I]k[/I] ≡ 1 iff ord(a)|k.

Alex

[Numbers]

Originally Posted by akruppa

...there exists a d so that d|n and d|k, but d cannot be smaller than n by definition of order,

Alex, Don’t we have to be a bit more careful about how we define d?

For example, Z/7* = {3, 2, 6, 4, 5, 1}

Ord(3) = 6

So we start with k = 12, l = 18 or whatever and after a couple of iterations we get k’ = 6, l’ = 6

So if we simply say there exists a d so that d|n, d|k

what is there to stop d = 2 or 3?

[akruppa]

Let n be the order of a and let d>0 so that a^[I]d[/I] ≡ 1.
Now d must be at least n, because the order of a is smallest integer so that a^[I]n[/I] ≡ 1. From the gcd argument we know that d|n.
The only d where d≥n and d|n is d=n.

>what is there to stop d = 2 or 3?

A contradiction with the order of a: if d were 2 and a^d ≡ 1, then the order of a could not be 6.

Alex

[Numbers]

Originally Posted by akruppa

Let n be the order of a and let d>0 so that a^[I]d[/I] ≡ 1. Now d must be at least n,

Absolutely!
To be honest, I thought you had done it on purpose to see if I was paying attention :)

All we have to do now is say k = p-1 and we have an element of full order iff ord(a)|p-1.

Very neat Alex, thank you very much.