Online primitive root modulo n list or tool?

Question

Please does somebody know of an online list or tool (if possible server side, not a Java applet running in my computer) to calculate the primitive roots modulo n, for instance $n \in [1,1000]$ (apart from the Wikipedia list)?

I know this site (link) which is very good, but it just calculates the primivite roots modulo a prime number, and I would like to check it for other values (if I am not wrong $n = 4, p^k$ and $2p^k$ where p is an odd prime would also have primitive roots modulo n).

I have been searching in the old questions, but I did not find it. If this was already asked I will remove the question. Thank you!

UPDATE:

Thank you very much for the code in the answers! I have made also my own Python code, but I would like to know if there is an online list or tool, it could be helpful for somebody else. Here is my (very brute force) version:

from sympy import is_primitive_root
def prim_root_prod(value):
    prlist = []
    for i in range (1,value):
        if is_primitive_root(i,value):
            prlist.append(i)
    return prlist

You can say «primitiveroot 7919» to Wolfram Alpha, as in wolframalpha.com/input/?i=primitiveroot+7919 — Mariano Suárez-Álvarez, May 15, 2015 at 5:23
@MarianoSuárez-Alvarez thank you! but it just return the first one, not the complete list. — iadvd, May 15, 2015 at 5:26
I believe you need if gcd(i,value)==1 and is_primitive_root(i,value): otherwise it stops with an error. That function is also quite slow (about 700x slower than Perl for first 2000 integers). I had some hopes for _primitive_root_prime_iter(p) but it only works for primes. — DanaJ, May 15, 2015 at 16:23
@DanaJ yeah it is slow, but it worked for my test (I used it to multiply the primitive roots). The results here: math.stackexchange.com/questions/1283244/… — iadvd, May 15, 2015 at 23:36
For that question you only run over primes, so the sympy iterator should work. The nextprime/prevprime quickly start dominating the time for that question I believe. — DanaJ, May 16, 2015 at 1:46

DanaJ · Accepted Answer · 2015-05-15 07:27:20Z

2

I don't have an online tool, but what you want seems to be the example from OEIS A046147. You might be able to tweak the Mathematica example and send it through WolframAlpha.

I give an example in the documentation for perl/ntheory for constructing that table. There's no online way to run it (that I know of) but just in case you want it:

use ntheory qw/:all/;
foreach my $n (1..1000) {
  if (!znprimroot($n)) {
    say "$n -";
  } else {
    my $phi = euler_phi($n);
    my @r = grep { gcd($_,$n) == 1 && znorder($_,$n) == $phi } 1..$n-1;
    say "$n ", join(" ", @r);
  }
}

All these functions are available in Pari/GP so it should be easy to do something similar with it.

answered May 15, 2015 at 7:27

DanaJ

2,8591 gold badge16 silver badges19 bronze badges

$\begingroup$ also very appreciated, finally I did my own version in Python! but still interested in knowing of a list or online tool, just in case could be useful for other users! $\endgroup$
– iadvd
May 15, 2015 at 7:30
1

$\begingroup$ added the Python version to the question :) $\endgroup$
– iadvd
May 15, 2015 at 7:39

Add a comment |

Mariano Suárez-Álvarez · Accepted Answer · 2015-05-15 05:33:16Z

These are primitive roots for the numbers that have them in $[1,2000]$. This list is a list of pairs $(n,r)$ with $n$ a number and $r$ a primitive root, the smallest one.

I got this with the following Mathematica code:

Cases[{#, PrimitiveRoot[#]} & /@ Range[2, 2000], {_, _Integer}]

If you want more, give me your email and I'll send you a longer list. — Mariano Suárez-Álvarez, May 15, 2015 at 5:30
thank you very much! that was cool, but for instance for n=5 the primitive roots modulo 5 are 2 and 3. In the list only appears the first of them, which is 2, not all the primitive roots. I am looking for the complete list for each n, not only the first primitive root modulo n. — iadvd, May 15, 2015 at 5:38
If $r$ is a primitive root for $n$, then all the others are the numbers $r^i$ with $i$ coprime to $\phi(n)$. Just compute the powers... — Mariano Suárez-Álvarez, May 15, 2015 at 5:42
finally I did my own version (added to the question), but I hope to find an online tool, it could be helpful for somebody else. — iadvd, May 15, 2015 at 7:38
What would be useful to anyone is to learn tto write the 3 or 4 lines needed to compute this oneself, really... — Mariano Suárez-Álvarez, May 15, 2015 at 7:51

Stack Exchange Network

Online primitive root modulo n list or tool?

2 Answers 2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged
reference-request
primitive-roots
.

Linked

Hot Network Questions

Online primitive root modulo n list or tool?

2 Answers 2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged reference-requestprimitive-roots.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
reference-request
primitive-roots
.