- It's funny you should ask this. I was just researching this exact same

question. The numbers you are looking at are called primitive roots. Pari/GP

has a function called znprimroot() that will let you know what the primitive

root is for any number. However, at least in my old version of 2.4.2, it can

sometimes give "a primitive root" for numbers that don't have one. In any

event, I had to research this because I needed to implement my own primitive

root finder in C. You can find information in the usual places:

http://mathworld.wolfram.com/PrimitiveRoot.html

http://en.wikipedia.org/wiki/Primitive_root_modulo_n

You missed one class of primitive roots in your definition. Numbers that have a

primitive root are 2, 4, and p^k like you said, but also 2*p^k has a primitive

root, where p is an odd prime and k >= 1.

-David C.

On 1/6/2013 8:30 PM, WarrenS wrote:

> (Quite likely this is already well known.)

> Suppose we consider the integers mod M

> (for some modulus M>1) that are relatively prime to M.

> The total cardinality of this set is EulerTotient(M).

>

> It is well known (proved by Galois) that if M is prime,

> then EulerTotient(M)=M-1 and these M-1 integers form, under

> multiplication mod M, a cyclic group.

>

> It is less well known that if M is an odd-prime POWER, then we still get

> a cyclic multiplicative group. For example

> the 6 integers mod 9 that are relatively prime to 9, are generated by

> the powers of 5:

> 5=(-4), 5^2=(-2), 5^3=(-1), 5^4=4, 5^5=2, 5^6=1.

>

> But this is not the case for even prime powers M>=8:

> The 4 odd integers mod 8 are NOT a cyclic group because x^2=1

> for every odd x (mod 8) so there can be no generator x modulo

> any M that is a power of 2 greater than 4,

> since every power of x is either x or 1 (mod 8).

>

> Despite this, they still form a non-cyclic group.

>

> As a result, the EulerTotient(M) residues mod M that are relatively prime to M

> (for any M>1) always form a multiplicative abelian group.

>

> My question is: for which M is that group cyclic?

> I claim the answer is:

> Exactly when M is a power of an odd prime, or M=2, or M=4. - --- In primenumbers@yahoogroups.com,

David Cleaver wrote:

> You can find information in the usual places

for example: CCANT Theorem 1.4.1.

David - --- In primenumbers@yahoogroups.com,

David Cleaver wrote:

> Pari/GP has a function called znprimroot()

Which works perfectly, with

> GP/PARI CALCULATOR Version 2.5.0 (released)

if you will read the friendly manual:

> znprimroot(n): returns a primitive root of n when it exists.

Here I write a simple routine to determine if (Z/nZ)* is cyclic,

call znprimroot if it is and check that the order is correct:

{iscycl(n)=local(f=factor(n),nf=#f[,1],t=n>0&&nf<3);

if(t&&nf==2&&(f[1,1]>2||f[1,2]>1),t=0);

if(t&&nf==1&&f[1,1]==2&&f[1,2]>2,t=0);t;}

{c=0;w=0;for(n=1,10^6,if(iscycl(n),c++;

w+=znorder(znprimroot(n))!=eulerphi(n)));

print(w"/"c" failures");}

0/120424 failures

David - On 1/7/2013 8:38 AM, djbroadhurst wrote:
>

I have just downloaded version 2.5.3, which also says:

> David Cleaver wrote:

>

> > Pari/GP has a function called znprimroot()

>

> Which works perfectly, with

> > GP/PARI CALCULATOR Version 2.5.0 (released)

> if you will read the friendly manual:

> > znprimroot(n): returns a primitive root of n when it exists.

znprimroot(n): returns a primitive root of n when it exists.

What I was trying to convey is that Pari/GP can also return what looks like a

valid answer, even though the input does not have a primitive root, ie:

? znprimroot(15)

%1 = Mod(2, 15)

? znprimroot(30)

%2 = Mod(17, 30)

? znprimroot(33)

%3 = Mod(5, 33)

? znprimroot(91)

%4 = Mod(2, 91)

I have read the fine/friendly manual, ie ?znprimroot. However, this says

nothing about what happens when the primitive root does not exist. I have found

several places online that do discuss that the result in those situations will

be "undefined", like here:

http://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html

However, I believe we are in complete agreement that when you want a primitive

root of numbers that have (at least) one, then you can use the znprimroot()

function in Pari/GP to find it.

-David C. - --- In primenumbers@yahoogroups.com,

David Cleaver wrote:

> What I was trying to convey is that Pari/GP can also

I imagine that GP returns an element of maximum order.

> return what looks like a valid answer, even though the

> input does not have a primitive root

Iff the group is cyclic this is a primitive root,

with order eulerphi(n). All of this is perfectly

consistent with the rubric:

znprimroot(n): returns a primitive root of n when it exists.

as we both agree.

David