A123475 -id:A123475 - cp's OEIS frontend

A088144 Sum of primitive roots of n-th prime.

1, 2, 5, 8, 23, 26, 68, 57, 139, 174, 123, 222, 328, 257, 612, 636, 886, 488, 669, 1064, 876, 1105, 1744, 1780, 1552, 2020, 1853, 2890, 1962, 2712, 2413, 3536, 4384, 3335, 5364, 3322, 3768, 4564, 7683, 7266, 8235, 4344, 8021, 6176, 8274

Offset: 1

Ed Pegg Jr, Nov 03 2003

nonn

It is a result that goes back to Mirsky that the set of primes p for which p-1 is squarefree has density A, where A denotes the Artin constant (A = Product_{q prime} (1-1/(q*(q-1)))). Numerically A = 0.3739558136.. = A005596. More precisely, Sum_{p <= x} mu(p-1)^2 = Ax/log x + o(x/log x) as x tends to infinity. Conjecture: sum_{p <= x, mu(p-1)=1} 1 = (A/2)x/log x + o(x/log x) and sum_{p <= x, mu(p-1)=-1} 1 = (A/2)x/log x + o(x/log x). - Pieter Moree (moree(AT)mpim-bonn.mpg.de), Nov 03 2003
The number of the primitive roots is A008330(n). - R. K. Guy, Feb 25 2011
If prime(n)  == 1 (mod 4), then a(n) = prime(n)*A008330(n)/2. There are also primes of the form prime(n) == 3 (mod 4) where prime(n) | a(n), namely prime(n) = 19, 127, 151, 163, 199, 251,... The list of primes in both modulo-4 classes where prime(n)|a(n) is 5, 13, 17, 19, 29, 37, 41, 53, 61,... - R. K. Guy, Feb 25 2011
a(n) = A076410(n) at n = 1, 3, 7, 55,... (for p = 2, 5, 17, 257... and perhaps only for the Fermat primes). - R. K. Guy, Feb 25 2011

			For 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, the primitive roots are as follows: {{1}, {2}, {2, 3}, {3, 5}, {2, 6, 7, 8}, {2, 6, 7, 11}, {3, 5, 6, 7, 10, 11, 12, 14}, {2, 3, 10, 13, 14, 15}, {5, 7, 10, 11, 14, 15, 17, 19, 20, 21}, {2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27}}

C. F. Gauss, Disquisitiones Arithmeticae, Yale, 1965; see p. 52.

T. D. Noe, Table of n, a(n) for n=1..1000
Leon Mirsky, The Number of Representations of an Integer as the Sum of a Prime and a k-Free Integer, Amer. Math. Monthly 56 (1949), 17-19.

Row sums of A060749, A254309.

Cf. A088145, A121380, A123475, A222009.

PrimitiveRootQ[ a_Integer, p_Integer ] := Block[ {fac, res}, fac = FactorInteger[ p - 1 ]; res = Table[ PowerMod[ a, (p - 1)/fac[ [ i, 1 ] ], p ], {i, Length[ fac ]} ]; ! MemberQ[ res, 1 ] ] PrimitiveRoots[ p_Integer ] := Select[ Range[ p - 1 ], PrimitiveRootQ[ #, p ] & ]
Total /@ Table[PrimitiveRootList[Prime[k]], {k, 1, 45}] (* Updated for Mathematica 13 by Harlan J. Brothers, Feb 27 2023 *)

a(n)=local(r, p, pr, j); p=prime(n); r=vector(eulerphi(p-1)); pr=znprimroot(p); for(i=1, p-1, if(gcd(i, p-1)==1, r[j++]=lift(pr^i))); vecsum(r) \\ after Franklin T. Adams-Watters's code in A060749, Michel Marcus, Mar 16 2015

A088145 Let p = prime(n); then a(n) = (Sum(primitive roots of p) - moebius(p-1))/p.

Original entry on oeis.org

0, 1, 1, 1, 2, 2, 4, 3, 6, 6, 4, 6, 8, 6, 13, 12, 15, 8, 10, 15, 12, 14, 21, 20, 16, 20, 18, 27, 18, 24, 19, 27, 32, 24, 36, 22, 24, 28, 46, 42, 46, 24, 42, 32, 42, 35, 27, 34, 58, 36, 56, 53, 32, 52, 64, 71, 66, 39, 44, 48, 48, 72, 48, 66, 48, 78, 44, 48, 88, 56, 80

Offset: 1

Ed Pegg Jr, Nov 03 2003

nonn

Gauss proved that the sum of the primitive roots of p is congruent to moebius(p-1) modulo p, for all primes p. - Jonathan Sondow, Feb 09 2013

			The primitive roots of prime(4) = 7 are 3 and 5, and moebius(7-1) = A008683(6) = 1, so a(4) = (3+5-1)/7 = 7/7 = 1. - _Jonathan Sondow_, Feb 10 2013

Wikipedia, Primitive root

Cf. A008683, A060749, A123475, A222009.

PrimitiveRootQ[ a_Integer, p_Integer ] := Block[ {fac, res}, fac = FactorInteger[ p - 1 ]; res = Table[ PowerMod[ a, ( p - 1)/fac[ [ i, 1 ] ], p ], {i, Length[ fac ]} ]; ! MemberQ[ res, 1 ] ] PrimitiveRoots[ p_Integer ] := Select[ Range[ p - 1 ], PrimitiveRootQ[ #, p ] & ] Table[ (Total[ PrimitiveRoots[ Prime[ n ] ] ] - MoebiusMu[ Prime[ n ] - 1 ])/Prime[ n ], {n, 1, 100} ]
a[n_] := With[{p = Prime[n]}, Select[Range[p - 1], MultiplicativeOrder[#, p] == p - 1 &]]; Table[(Sum[a[n][[i]], {i, Length[a[n]]}] - MoebiusMu[Prime[n] - 1])/Prime[n], {n, 1,10}] (* Jonathan Sondow, Feb 09 2013 *)

Definition corrected by Jonathan Sondow, Feb 09 2013

A121380 Sums of primitive roots for n (or 0 if n has no primitive roots).

Original entry on oeis.org

0, 1, 2, 3, 5, 5, 8, 0, 7, 10, 23, 0, 26, 8, 0, 0, 68, 16, 57, 0, 0, 56, 139, 0, 100, 52, 75, 0, 174, 0, 123, 0, 0, 136, 0, 0, 222, 114, 0, 0, 328, 0, 257, 0, 0, 208, 612, 0, 300, 200, 0, 0, 636, 156, 0, 0, 0, 348, 886, 0, 488, 216, 0, 0, 0, 0, 669, 0, 0, 0

Offset: 1

Ed Pegg Jr, Jul 25 2006

In Article 81 of his Disquisitiones Arithmeticae (1801), Gauss proves that the sum of all primitive roots (A001918) of a prime p, mod p, equals MoebiusMu[p-1] (A008683). "The sum of all primitive roots is either = 0 (mod p) (when p-1 is divisible by a square), or = +-1 (mod p) (when p-1 is the product of unequal prime numbers; if the number of these is even the sign is positive but if the number is odd, the sign is negative)."

			The primitive roots of 13 are 2, 6, 7, 11. Their sum is 26, or 0 (mod 13). By Gauss, 13-1=12 is thus divisible by a square number.

J. C. F. Gauss, Disquisitiones Arithmeticae, 1801.

T. D. Noe, Table of n, a(n) for n = 1..10000
Eric Weisstein, Primitive Roots.

Cf. A001918, A008683, A046147 (primitive roots of n), A088144, A088145, A123475, A222009.

primitiveRoots[n_] := If[n == 1, {}, If[n == 2, {1}, Select[Range[2, n-1], MultiplicativeOrder[#, n] == EulerPhi[n] &]]]; Table[Total[primitiveRoots[n]], {n,100}]
(* From version 10 up: *)
Table[Total @ PrimitiveRootList[n], {n, 1, 100}] (* Jean-François Alcover, Oct 31 2016 *)

A222009 (Product(primitive roots of p) - 1)/p, where p = prime(n) and n > 2.

Original entry on oeis.org

1, 2, 61, 71, 684847, 8621, 4768743913, 192769238731, 31302497, 3624013907027, 3389284413733950439, 20347152500093, 73535243111830065216714893617, 579021662547635771462791245283, 38283945111344558723552263341142779661, 60296900399609972459, 271233083114844569997128597, 1382959355737627871079165208413804169

Offset: 3

Jonathan Sondow, Feb 09 2013

nonn

Gauss proved that the product of the primitive roots of p is congruent to 1 modulo p, for all primes p except p = 3.

			The primitive roots of prime(4) = 7 are 3 and 5, and (3*5 - 1)/7 = 14/7 = 2, so a(4) = 2.

C. F. Gauss, Disquisitiones Arithmeticae, Yale, 1965; see p. 52.

Wikipedia, Primitive root

Cf. A060749, A088145, A123475.

a[n_] := With[{p = Prime[n]}, Select[Range[p - 1], MultiplicativeOrder[#, p] == p - 1 &]]; Table[(Product[ a[n][[i]], {i, Length[a[n]]}] - 1)/Prime[n], {n, 3, 20}]

a(n) = (A123475(n) - 1)/A000040(n) for n > 2.

A382221 Products of primitive roots when n is 2, 4, p^k, or 2p^k (with p an odd prime), for all other n the value is defined to be 1.

Original entry on oeis.org

1, 1, 2, 3, 6, 5, 15, 1, 10, 21, 672, 1, 924, 15, 1, 1, 11642400, 55, 163800, 1, 1, 29393, 109681110000, 1, 64411776, 21945, 708400, 1, 5590307923200, 1, 970377408, 1, 1, 644812245, 1, 1, 134088514560000, 11756745, 1, 1, 138960660963091968000, 1

Offset: 1

Darío Clavijo, Mar 27 2025

nonn

Michael De Vlieger, Table of n, a(n) for n = 1..838
Wikipedia, Primitive root modulo n.

Cf. A033948, A121380, A123475, A180634.

Table[Times @@ PrimitiveRootList[n], {n, 42}] (* Michael De Vlieger, Apr 07 2025 *)

from sympy import gcd, primitive_root, totient
def a(n):
    try:
        g = primitive_root(n)
    except ValueError:
        return 1
    P = 1
    if g:
        phi = totient(n)
        for k in range(1, phi):
            if gcd(k, phi) == 1:
                P *= pow(g, k, n)
    return P
print([a(n) for n in range(1,43)])

a(n) = A123475(n) if n is prime.
a(A180634(n)) = 1.
a(n) > 1 if n in A033948.

A347946 Products of nonprimitive roots of n, or 0 if n = 2 or has no primitive roots.

Original entry on oeis.org

0, 0, 1, 2, 4, 24, 48, 0, 4032, 17280, 5400, 0, 518400, 415134720, 0, 0, 1797120, 6467044147200, 39086530560, 0, 0, 1738201006080000, 10247897088, 0, 9632530575360000, 706822057112371200000, 569299069913333760000, 0, 54538738974720000, 0

Offset: 1

Davide Rotondo, Sep 26 2021

nonn

If n is a prime p, a(n) == -1 (mod p) for n > 3; if n is a composite c, a(n) == 0 (mod c) for n > 4.

			a(11) = 5400 because the primitive roots of 11 are {2,6,7,8} and therefore the nonprimitive roots of 11 are {1,3,4,5,9,10} and 1*3*4*5*9*10 = 5400.

Cf. A123475, A219027, A219028.

a[n_] := If[n == 2 || (p = PrimitiveRootList[n]) == {}, 0, (n - 1)!/Times @@ p]; Array[a, 30] (* Amiram Eldar, Sep 26 2021 *)

cp's OEIS Frontend

A088144 Sum of primitive roots of n-th prime.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

A088145 Let p = prime(n); then a(n) = (Sum(primitive roots of p) - moebius(p-1))/p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A121380 Sums of primitive roots for n (or 0 if n has no primitive roots).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A222009 (Product(primitive roots of p) - 1)/p, where p = prime(n) and n > 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A382221 Products of primitive roots when n is 2, 4, p^k, or 2p^k (with p an odd prime), for all other n the value is defined to be 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Formula

A347946 Products of nonprimitive roots of n, or 0 if n = 2 or has no primitive roots.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica