The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Message from discussion Primitive Root Question

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Nov 6 1998, 3:00 am
Newsgroups: sci.math
From: benschop...@my-dejanews.com
Date: 1998/11/06
Subject: Re: Primitive Root Question
In article <71v0jc\$2c...@nnrp1.dejanews.com>,

benschop...@my-dejanews.com wrote:
> In article <71trtj\$4h...@nnrp1.dejanews.com>,
>   tull...@my-dejanews.com wrote:
> > Given a prime modulus p (e.g.,71) and a number x less than p (e.g.,7), is
> > there a method (short of solving for all the powers of x) to determine
> > whether x is a primitive root mod p?  In other words, is there a formula
> > for determining the order of x mod p?  Many thanks for any assistance.
> > -- M.Tullius

> This is the well known "primitive root" problem, unsolved AFAIK

> The structure of Z(.) mod p is a p-1 cyclic group G, adjoined to '0' ,
> essentially Fermat's Small Theorem (FST): n^p = n mod p (prime p, all n).

> Short of checking x^d = 1 mod p, for proper divisors d= (p-1)/q [prime q],
> (if true for some d then x is not primitive: it generates a subgroup x*
> of units group G, with |x*| dividing p-1) there is no shorter way to tell
> the primitivity of x.

> Ciao, Nico Benschop. -- http://www.iae.nl/users/benschop

Nota bene: the group of units G_k mod p^k (k>1) is _also_ cyclic,

and is of order (p-1)p^{k-1} --> hence is a product G_k = A_k.B_k.
with "core" subgroup |A_k|=p-1 (re: FST), and |B_k|= p^{k-1} = (p+1)*

A generator of G_2 will generate (if padded by msd zero's) also G_k
for every k>2. This is not always true for x* = G_1, where x may not
generate G_2.

Prime p=2 is the only prime for which G_k (k>1) is NOT cyclic,

but in fact a direct product: G_k = C2 x Cm,  where m= 2^{k-2}

with 2-cycle C2={-1,1}

and Cm={3*}: so 3 is a semi-primitive root of 1 mod 2^k (k>2).

see http://www.iae.nl/users/benschop/nfb0.dvi   (lem1.1)
"Triplets and symmetries of Arithmetic mod p^k"
(incl. proof of FLTcase1 via FST_extension)

So strangely: the only interesting prime, from a practical point
of view (computer hardware: binary code mod 2^k) is also the only
one for which the primitive root problem is solved (and simple;-)

Ciao, Nico benschop -- http://www.iae.nl/users/benschop

-----------== Posted via Deja News, The Discussion Network ==----------