## Re: [PrimeNumbers] multiplicative group mod M: I claim cyclic iff M=odd prime power or M<6.

Expand Messages
• 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
Message 1 of 6 , Jan 7, 2013
• 0 Attachment
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.
• ... for example: CCANT Theorem 1.4.1. David
Message 2 of 6 , Jan 7, 2013
• 0 Attachment
David Cleaver wrote:

> You can find information in the usual places

for example: CCANT Theorem 1.4.1.

David
• ... Which works perfectly, with ... Here I write a simple routine to determine if (Z/nZ)* is cyclic, call znprimroot if it is and check that the order is
Message 3 of 6 , Jan 7, 2013
• 0 Attachment
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
• ... I have just downloaded version 2.5.3, which also says: znprimroot(n): returns a primitive root of n when it exists. What I was trying to convey is that
Message 4 of 6 , Jan 7, 2013
• 0 Attachment
On 1/7/2013 8:38 AM, djbroadhurst wrote:
>
> 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.
• ... I imagine that GP returns an element of maximum order. Iff the group is cyclic this is a primitive root, with order eulerphi(n). All of this is perfectly
Message 5 of 6 , Jan 8, 2013
• 0 Attachment
David Cleaver wrote:

> 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

I imagine that GP returns an element of maximum order.
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
Your message has been successfully submitted and would be delivered to recipients shortly.