3
$\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$
  • 1
    $\begingroup$ You can say «primitiveroot 7919» to Wolfram Alpha, as in wolframalpha.com/input/?i=primitiveroot+7919 $\endgroup$ – Mariano Suárez-Álvarez May 15 '15 at 5:23
  • $\begingroup$ @MarianoSuárez-Alvarez thank you! but it just return the first one, not the complete list. $\endgroup$ – iadvd May 15 '15 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 '15 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 '15 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 '15 at 1:46
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$
  • $\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 '15 at 7:30
  • 1
    $\begingroup$ added the Python version to the question :) $\endgroup$ – iadvd May 15 '15 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$
  • $\begingroup$ If you want more, give me your email and I'll send you a longer list. $\endgroup$ – Mariano Suárez-Álvarez May 15 '15 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 '15 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$ – Mariano Suárez-Álvarez May 15 '15 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 '15 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$ – Mariano Suárez-Álvarez May 15 '15 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.