4
$\begingroup$

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
$\endgroup$
5
  • 1
    $\begingroup$ You can say «primitiveroot 7919» to Wolfram Alpha, as in wolframalpha.com/input/?i=primitiveroot+7919 $\endgroup$ May 15, 2015 at 5:23
  • $\begingroup$ @MarianoSuárez-Alvarez thank you! but it just return the first one, not the complete list. $\endgroup$
    – iadvd
    May 15, 2015 at 5:26
  • $\begingroup$ 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. $\endgroup$
    – DanaJ
    May 15, 2015 at 16:23
  • $\begingroup$ @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/… $\endgroup$
    – iadvd
    May 15, 2015 at 23:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – DanaJ
    May 16, 2015 at 1:46

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
  • $\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
2
$\begingroup$

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.

2      1
3      2
4      3
5      2
6      5
7      3
9      2
10     7
11     2
13     2
14     3
17     3
18     11
19     2
22     13
23     5
25     2
26     15
27     2
29     2
31     3
34     3
37     2
38     21
41     6
43     3
46     5
47     5
49     3
50     27
53     2
54     29
58     31
59     2
61     2
62     3
67     2
71     7
73     5
74     39
79     3
81     2
82     47
83     2
86     3
89     3
94     5
97     5
98     3
101    2
103    5
106    55
107    2
109    6
113    3
118    61
121    2
122    63
125    2
127    3
131    2
134    69
137    3
139    2
142    7
146    5
149    2
151    6
157    5
158    3
162    83
163    2
166    85
167    5
169    2
173    2
178    3
179    2
181    2
191    19
193    5
194    5
197    2
199    3
202    103
206    5
211    2
214    109
218    115
223    3
226    3
227    2
229    6
233    3
239    7
241    7
242    123
243    2
250    127
251    6
254    3
257    3
262    133
263    5
269    2
271    6
274    3
277    5
278    141
281    3
283    3
289    3
293    2
298    151
302    157
307    5
311    17
313    10
314    5
317    2
326    165
331    3
334    5
337    10
338    171
343    3
346    175
347    2
349    2
353    3
358    181
359    7
361    2
362    183
367    6
373    2
379    2
382    19
383    5
386    5
389    2
394    199
397    5
398    3
401    3
409    21
419    2
421    2
422    213
431    7
433    5
439    15
443    2
446    3
449    3
454    229
457    13
458    235
461    2
463    3
466    3
467    2
478    7
479    13
482    7
486    245
487    3
491    2
499    7
502    257
503    5
509    2
514    3
521    3
523    2
526    5
529    5
538    271
541    2
542    277
547    2
554    5
557    2
562    3
563    2
566    3
569    3
571    3
577    5
578    3
586    295
587    2
593    3
599    7
601    7
607    3
613    2
614    5
617    3
619    2
622    17
625    2
626    323
631    3
634    319
641    3
643    11
647    5
653    2
659    2
661    2
662    3
673    5
674    347
677    2
683    5
686    3
691    3
694    349
698    351
701    2
706    3
709    2
718    7
719    11
722    363
727    5
729    2
733    6
734    373
739    3
743    5
746    375
751    3
757    2
758    381
761    6
766    5
769    11
773    2
778    391
787    2
794    5
797    2
802    3
809    3
811    3
818    21
821    2
823    3
827    2
829    2
838    421
839    11
841    2
842    423
853    2
857    3
859    2
862    7
863    5
866    5
877    2
878    15
881    3
883    2
886    445
887    5
898    3
907    2
911    17
914    13
919    7
922    463
926    3
929    3
934    469
937    5
941    2
947    2
953    3
958    13
961    3
967    5
971    6
974    3
977    3
982    493
983    5
991    6
997    7
998    7
1006   5
1009   11
1013   3
1018   511
1019   2
1021   10
1031   14
1033   5
1039   3
1042   3
1046   525
1049   3
1051   7
1058   5
1061   2
1063   3
1069   6
1082   543
1087   3
1091   2
1093   5
1094   549
1097   3
1103   5
1109   2
1114   559
1117   2
1123   2
1126   565
1129   11
1138   3
1142   3
1151   17
1153   5
1154   5
1163   5
1171   2
1174   589
1181   7
1186   3
1187   2
1193   3
1198   7
1201   11
1202   7
1213   2
1214   3
1217   3
1223   5
1226   615
1229   2
1231   3
1234   3
1237   2
1238   621
1249   7
1250   627
1259   2
1262   3
1277   2
1279   3
1282   3
1283   2
1286   11
1289   6
1291   2
1294   5
1297   10
1301   2
1303   6
1306   655
1307   2
1318   661
1319   13
1321   13
1322   663
1327   3
1331   2
1346   5
1354   679
1361   3
1366   5
1367   5
1369   2
1373   2
1381   2
1382   3
1399   13
1402   703
1409   3
1418   711
1423   3
1427   2
1429   6
1433   3
1438   11
1439   7
1447   3
1451   2
1453   2
1454   5
1458   731
1459   3
1466   739
1471   6
1478   3
1481   3
1483   2
1486   5
1487   5
1489   14
1493   2
1499   2
1502   3
1511   11
1514   759
1522   767
1523   2
1531   2
1538   11
1543   5
1546   775
1549   2
1553   3
1559   19
1567   3
1571   2
1574   789
1579   3
1583   5
1594   799
1597   11
1601   3
1607   5
1609   7
1613   3
1618   3
1619   2
1621   2
1622   3
1627   3
1637   2
1642   823
1646   3
1654   829
1657   11
1658   831
1663   3
1667   2
1669   2
1678   11
1681   6
1682   843
1693   2
1697   3
1699   3
1706   855
1709   3
1714   3
1718   861
1721   3
1723   3
1726   5
1733   2
1741   2
1747   2
1753   7
1754   879
1759   6
1762   3
1766   885
1774   5
1777   5
1783   10
1787   2
1789   6
1801   11
1811   6
1814   909
1822   17
1823   5
1831   3
1838   7
1847   5
1849   3
1858   3
1861   2
1867   2
1871   14
1873   10
1874   5
1877   2
1879   6
1882   943
1889   3
1894   949
1901   2
1906   3
1907   2
1913   3
1922   3
1931   2
1933   5
1934   5
1942   977
1949   2
1951   3
1954   3
1966   5
1973   2
1979   2
1982   997
1987   2
1993   5
1994   7
1997   2
1999   3

I got this with the following Mathematica code:

Cases[{#, PrimitiveRoot[#]} & /@ Range[2, 2000], {_, _Integer}]
$\endgroup$
6
  • $\begingroup$ If you want more, give me your email and I'll send you a longer list. $\endgroup$ May 15, 2015 at 5:30
  • $\begingroup$ 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. $\endgroup$
    – iadvd
    May 15, 2015 at 5:38
  • $\begingroup$ 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... $\endgroup$ May 15, 2015 at 5:42
  • $\begingroup$ 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. $\endgroup$
    – iadvd
    May 15, 2015 at 7:38
  • $\begingroup$ What would be useful to anyone is to learn tto write the 3 or 4 lines needed to compute this oneself, really... $\endgroup$ May 15, 2015 at 7:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .