Loading ...
Sorry, an error occurred while loading the content.
 

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

Expand Messages
  • djbroadhurst
    ... 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 1 of 6 , Jan 7, 2013
      --- 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
    • David Cleaver
      ... 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 2 of 6 , Jan 7, 2013
        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.

        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 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.
      • djbroadhurst
        ... 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 3 of 6 , Jan 8, 2013
          --- In primenumbers@yahoogroups.com,
          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.