A060749 -id:A060749 - cp's OEIS frontend

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

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

A138326 Numbers not representable as p+g, where p is a prime and g is a primitive root of p.

Original entry on oeis.org

1, 2, 4, 6, 9, 11, 14, 16, 25, 26, 35, 36, 41, 45, 49, 51, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1024, 1089, 1156, 1225, 1296, 1369, 1444, 1521, 1600, 1681, 1764, 1849, 1936, 2025

Offset: 1

T. D. Noe, Mar 14 2008

nonn

This sequence appears to contain all the positive squares (A000290) and a few other numbers (A138327).

Amiram Eldar, Table of n, a(n) for n = 1..375

Cf. A000290, A060749 (primitive roots), A138327.

seq[m_] := Module[{p = Select[Range[m], PrimeQ]}, Complement[Range[m], p + PrimitiveRootList[p] // Flatten]]; seq[2000] (* Amiram Eldar, Oct 09 2021 *)

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.

A225184 Primes p with a primitive root that divides p+1.

Original entry on oeis.org

2, 3, 5, 11, 13, 17, 19, 29, 37, 41, 53, 59, 61, 67, 83, 89, 97, 101, 107, 109, 113, 131, 137, 139, 149, 163, 173, 179, 181, 197, 211, 227, 229, 233, 251, 257, 269, 281, 293, 307, 317, 347, 349, 353, 373, 379, 389, 401, 419, 421, 433, 443, 449, 461, 467, 491, 499, 509, 521, 523, 541, 547, 557, 563, 569, 587, 593, 601

Offset: 1

N. J. A. Sloane, May 04 2013

nonn

			The primitive roots modulo 97 are 5, 7, 10, 13, 14, 15, 17, 21, 23, 26, 29, 37, 38, 39, ..., and 7 divides 98, so 97 is a member of this sequence.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Arto Lepistö, Francesco Pappalardi and Kalle Saari, Transposition Invariant Words, Theoret. Comput. Sci., Vol. 380, No. 3 (2007), pp. 377-387.

Cf. A060749, A225185 (complement). A001122 is a subsequence.

[p: p in PrimesUpTo(700) | exists{r: r in [1..p-1] | IsPrimitive(r,p) and IsZero((p+1) mod r)}]; // Bruno Berselli, May 10 2013

forprime(p=2,1000, i=0; fordiv(p+1,X, if(znorder(Mod(X,p))==eulerphi(p), i=1)); if(i==1,print1(p", "))) \\ V. Raman, May 04 2013

More terms from V. Raman, May 04 2013

A254309 Irregular triangular array read by rows: T(n,k) is the least positive primitive root of the n-th prime p=prime(n) raised to successive powers of k (mod p) where 1<=k<=p-1 and gcd(k,p-1)=1.

Original entry on oeis.org

1, 2, 2, 3, 3, 5, 2, 8, 7, 6, 2, 6, 11, 7, 3, 10, 5, 11, 14, 7, 12, 6, 2, 13, 14, 15, 3, 10, 5, 10, 20, 17, 11, 21, 19, 15, 7, 14, 2, 8, 3, 19, 18, 14, 27, 21, 26, 10, 11, 15, 3, 17, 13, 24, 22, 12, 11, 21, 2, 32, 17, 13, 15, 18, 35, 5, 20, 24, 22, 19

Offset: 1

Geoffrey Critzer, May 03 2015

Each row is a complete set of incongruent primitive roots.
Each row is a permutation of the corresponding row in A060749.
Row lengths are A008330.
T(n,1) = A001918(n).

			1;
2;
2,  3;
3,  5;
2,  8,  7,  6;
2,  6, 11,  7;
3, 10,  5, 11, 14,  7, 12,  6;
2, 13, 14, 15,  3, 10;
5, 10, 20, 17, 11, 21, 19, 15,  7, 14;
2,  8,  3, 19, 18, 14, 27, 21, 26, 10, 11, 15;
Row 6 contains 2,6,11,7 because 13 is the 6th prime number. 2 is the least positive primitive root of 13. The integers relatively prime to 13-1=12 are {1,5,7,11}. So we have: 2^1==2, 2^5==6, 2^7==11, and 2^11==7 (mod 13).

Alois P. Heinz, Rows n = 1..120, flattened

Cf. A001918, A008330, A060749.
Last elements of rows give A255367.
Row sums give A088144.

with(numtheory):
T:= n-> (p-> seq(primroot(p)&^k mod p, k=select(
         h-> igcd(h, p-1)=1, [$1..p-1])))(ithprime(n)):
seq(T(n), n=1..15);  # Alois P. Heinz, May 03 2015

Table[nn = p;Table[Mod[PrimitiveRoot[nn]^k, nn], {k,Select[Range[nn - 1], CoprimeQ[#, nn - 1] &]}], {p,Prime[Range[12]]}] // Grid

A128895 Least positive primitive root that all of the first n primes share.

Original entry on oeis.org

1, 5, 17, 17, 17, 227, 227, 5297, 5297, 5297, 226817, 1227497, 2270483, 5967617, 8617187, 27311693, 39928787, 39928787, 345664343, 345664343

Offset: 1

Martin Raab, Apr 20 2007

nonn

			A primitive root of 2 must be == 1 (mod 2); for 3, it must be == 2 (mod 3), and for 5 it must be == 2 or 3 (mod 5). The smallest such number is 17, so a(3)=17.

Don Reble, Table of n, a(n) for n = 1..37

Cf. A001918, A060749.

A138304 Number of prime primitive roots of prime(n).

Original entry on oeis.org

0, 1, 2, 2, 2, 3, 4, 3, 5, 4, 4, 5, 6, 4, 9, 6, 8, 6, 7, 9, 8, 8, 11, 12, 11, 12, 7, 12, 9, 16, 11, 11, 17, 9, 18, 6, 11, 17, 23, 18, 20, 13, 20, 16, 19, 13, 12, 15, 24, 20, 28, 24, 17, 23, 28, 32, 29, 15, 24, 23, 13, 31, 20, 32, 23, 28, 15, 21, 32, 22, 28, 42, 27, 29, 21, 43, 40, 27

Offset: 1

T. D. Noe, Mar 14 2008

nonn

			a(5)=2 because the primitive roots of 11 are 2, 6, 7 and 8, two of which are prime.

T. D. Noe, Table of n, a(n) for n=1..10000

Cf. A060749 (primitive roots), A138304 (prime primitive roots).

Table[p=Prime[n]; g=Select[Prime[Range[n-1]], MultiplicativeOrder[ #,p]==p-1&]; Length[g], {n,100}]

A138325 Least prime p such that n = p + g, where g is a primitive root of p, or 0 if there is no such prime p.

Original entry on oeis.org

0, 0, 2, 0, 3, 0, 5, 5, 0, 7, 0, 7, 11, 0, 13, 0, 11, 11, 11, 13, 19, 17, 17, 13, 0, 0, 17, 17, 17, 23, 17, 19, 19, 19, 0, 0, 23, 23, 29, 23, 0, 23, 23, 23, 0, 43, 29, 29, 0, 29, 0, 31, 31, 37, 29, 29, 37, 41, 37, 41, 37, 43, 41, 0, 41, 47, 41, 61, 37, 41, 41, 37, 43, 53, 41, 41, 43, 47

Offset: 1

T. D. Noe, Mar 14 2008

nonn

Sequence A138128 gives the number of representations for each n and sequence A138326 lists the values of n that are not represented.

T. D. Noe, Table of n, a(n) for n=1..1000

Cf. A060749 (primitive roots).

A190105 a(n) = (3*A002145(n) - 1)/4.

Original entry on oeis.org

2, 5, 8, 14, 17, 23, 32, 35, 44, 50, 53, 59, 62, 77, 80, 95, 98, 104, 113, 122, 125, 134, 143, 149, 158, 167, 170, 179, 188, 197, 203, 212, 230, 233, 248, 260, 269, 275, 284, 287, 314, 323, 329, 332, 347, 350, 359, 365, 368, 374, 377, 392, 410, 422, 428, 440

Offset: 1

J. M. Bergot, May 04 2011

For primes p of the form 4n+3, in the order of A002145, let us seek solutions for prime p|(a^x + b^y) or p|(a^y + b^x) subject to the conditions p = a+b = x+y and 0 < a,b,x,y < p. The larger of the two exponents x and y is inserted into the sequence.

If either of (a,b) is a primitive root of p, there is a unique solution, either p|(a^x + b^y) or p|(a^y + b^x). If neither is a primitive root (see A060749), there are multiple solutions and p|(a^x + b^y) or p|(a^y + b^x) will always be one of them for some of the given exponents (x,y) contributing to the sequence.

			For p=43=A002145(7), (x,y)=(11,32) because 43-(43+1)/4=32; hence x=43-32.  With (a,b)=(12,31) the unique solution is 43|(12^11 + 31^32) because 12 is a primitive root of 43. The larger of 11 and 32 is a(7)=32 in the sequence. For 43 multiple solutions occur when neither of the pairs (a,b) is a primitive root of 43: p divides each of 11^4 + 32^39, 11^18 + 32^25, 11^32 + 32^11; note that the exponents (11,32) occur in the last entry.

G. C. Greubel, Table of n, a(n) for n = 1..10000

Cf. A005099 is the list of x in (x,y).

for n from 1 to 200 do p:=4*n-1: if(isprime(p))then printf("%d, ", (3*p-1)/4); fi: od: # Nathaniel Johnston, May 18 2011

A002145 := Select[4 Range[300] - 1, PrimeQ]; Table[(3*A002145[[n]] - 1)/4, {n, 1, 60}] (* G. C. Greubel, Nov 07 2018 *)

A225185 Primes p which do not have a primitive root that divides p+1.

Original entry on oeis.org

7, 23, 31, 43, 47, 71, 73, 79, 103, 127, 151, 157, 167, 191, 193, 199, 223, 239, 241, 263, 271, 277, 283, 311, 313, 331, 337, 359, 367, 383, 397, 409, 431, 439, 457, 463, 479, 487, 503, 571, 577, 599, 607, 631, 647, 673, 691, 719, 727, 733, 739, 743, 751, 811, 823, 839, 863, 887, 911, 919, 967, 983, 991, 997

Offset: 1

N. J. A. Sloane, May 04 2013

nonn

			The primitive roots modulo 97 are 5, 7, 10, 13, 14, 15, 17, 21, 23, 26, 29, 37, 38, 39, ..., and 7 divides 98, so 97 is not a term of this sequence.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Arto Lepistö, Francesco Pappalardi and Kalle Saari, Transposition Invariant Words, Theoret. Comput. Sci., Vol. 380, No. 3 (2007), pp. 377-387.

Cf. A060749, A225184 (complement), A001122.

[p: p in PrimesUpTo(1000) | not exists{r: r in [1..p-1] | IsPrimitive(r,p) and IsZero((p+1) mod r)}]; // Bruno Berselli, May 10 2013

q[n_] := PrimeQ[n] && AllTrue[PrimitiveRootList[n], ! Divisible[n + 1, #] &]; Select[Range[1000], q] (* Amiram Eldar, Oct 07 2021 *)
Select[Prime[Range[200]],NoneTrue[(#+1)/PrimitiveRootList[#],IntegerQ]&] (* Harvey P. Dale, Sep 08 2024 *)

forprime(p=2,1000, i=0;fordiv(p+1,X, if(znorder(Mod(X,p))==eulerphi(p), i=1)); if(i==0,print1(p", "))) \\ V. Raman, May 04 2012

More terms from V. Raman, May 04 2013

cp's OEIS Frontend

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

A138326 Numbers not representable as p+g, where p is a prime and g is a primitive root of p.

Views

Author

Keywords

Comments

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

A225184 Primes p with a primitive root that divides p+1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

PARI

Extensions

A254309 Irregular triangular array read by rows: T(n,k) is the least positive primitive root of the n-th prime p=prime(n) raised to successive powers of k (mod p) where 1<=k<=p-1 and gcd(k,p-1)=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A128895 Least positive primitive root that all of the first n primes share.

Views

Author

Keywords

Examples

Links

Crossrefs

A138304 Number of prime primitive roots of prime(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A138325 Least prime p such that n = p + g, where g is a primitive root of p, or 0 if there is no such prime p.

Views

Author

Keywords

Comments

Links

Crossrefs

A190105 a(n) = (3*A002145(n) - 1)/4.

Views