A008330 -id:A008330 - cp's OEIS frontend

A060749 Triangle in which n-th row lists all primitive roots modulo the n-th prime.

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, 3, 11, 12, 13, 17, 21, 22, 24, 2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35, 6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35

Offset: 1

N. J. A. Sloane, Apr 23 2001

Row n has A008330(n) terms. - Alford Arnold, Aug 22 2004

			The triangle a(n,k) begins (second column pr(n) is here prime(n)):
n  pr(n)\k 1  2  3  4  5  6  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27...
1    2     1
2    3     2
3    5     2  3
4    7     3  5
5   11     2  6  7  8
6   13     2  6  7 11
7   17     3  5  6  7 10 11 12 14
8   19     2  3 10 13 14 15
9   23     5  7 10 11 14 15 17 19 20 21
10  29     2  3  8 10 11 14 15 18 19 21 26 27
11  31     3 11 12 13 17 21 22 24
12  37     2  5 13 15 17 18 19 20 22 24 32 35
13  41     6  7 11 12 13 15 17 19 22 24 26 28 29 30 34 35
14  43     3  5 12 18 19 20 26 28 29 30 33 34
15  47     5 10 11 13 15 19 20 22 23 26 29 30 31 33 35 38 39 40 41 43 44 45
16  53     2  3  5  8 12 14 18 19 20 21 22 26 27 31 32 33 34 35 39 41 45 48 50 51
17  59     2  6  8 10 11 13 14 18 23 24 30 31 32 33 34 37 38 39 40 42 43 44 47 50 52 54 55 56
18  61     2  6  7 10 17 18 26 30 31 35 43 44 51 54 55 59
19  67     2  7 11 12 13 18 20 28 31 32 34 41 44 46 48 50 51 57 61 63
20  71     7 11 13 21 22 28 31 33 35 42 44 47 52 53 55 56 59 61 62 63 65 67 68 69
---------------------------------------------------------------------------------
... reformatted and extended. - _Wolfdieter Lang_, May 18 2014

R. Osborn, Tables of All Primitive Roots of Odd Primes Less Than 1000, Univ. Texas Press, 1961.

T. D. Noe, Table of n, a(n) for n = 1..9076 (first 100 rows)
C. W. Curtis, Pioneers of Representation Theory, Amer. Math. Soc., 1999; see p. 3.

Diagonals give A001918, A071894.

Cf. A008330, A046147.

prQ[p_, a_] := Block[{d = Most@Divisors[p - 1]}, If[ GCD[p, a] == 1, FreeQ[ PowerMod[a, d, p], 1], False]]; f[n_] := Select[Range@n, prQ[n, # ] &]; Table[ f[Prime[n]], {n, 13}] // Flatten (* Robert G. Wilson v, Dec 17 2005 *)
primRoots[p_] := (g = PrimitiveRoot[p]; goodOddIntegers = Select[Range[1, p-1, 2], CoprimeQ[#, p-1]&]; allPrimRoots = PowerMod[g, #, p]& /@ goodOddIntegers; Sort[allPrimRoots]); primRoots /@ Prime[Range[50]] // Flatten (* Jean-François Alcover, Nov 12 2014, after Peter Luschny *)
roots[n_] := PrimitiveRootList[Prime[n]]; Array[roots, 50] // Flatten (* Jean-François Alcover, Feb 01 2016 *)

ar(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)));vecsort(r) \\ Franklin T. Adams-Watters, Jan 22 2012

def primroots(p):
    g = primitive_root(p)
    znorder = p - 1
    is_coprime = lambda x: gcd(x, znorder) == 1
    good_odd_integers = filter(is_coprime, [1..p-1, step=2])
    all_primroots = [power_mod(g, k, p) for k in good_odd_integers]
    all_primroots.sort()
    return all_primroots # Minh Van Nguyen, Functional Programming for Mathematicians, Tutorial at sagemath.org
for p in primes(1, 50) : print(primroots(p)) # Peter Luschny, Jun 08 2011

More terms from Alford Arnold, Aug 22 2004
More terms from Paul Stoeber (pstoeber(AT)uni-potsdam.de), Oct 08 2005
Terms 26, 28, 29, 30, 34, 35 added; completion of row n=13. - Wolfdieter Lang, May 18 2014

A046144 Number of primitive roots modulo n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 0, 2, 2, 4, 0, 4, 2, 0, 0, 8, 2, 6, 0, 0, 4, 10, 0, 8, 4, 6, 0, 12, 0, 8, 0, 0, 8, 0, 0, 12, 6, 0, 0, 16, 0, 12, 0, 0, 10, 22, 0, 12, 8, 0, 0, 24, 6, 0, 0, 0, 12, 28, 0, 16, 8, 0, 0, 0, 0, 20, 0, 0, 0, 24, 0, 24, 12, 0, 0, 0, 0, 24, 0, 18, 16, 40, 0, 0, 12, 0, 0, 40, 0, 0

Offset: 1

Eric W. Weisstein

nonn

T. D. Noe, Table of n, a(n) for n = 1..10000
S. R. Finch, Idempotents and Nilpotents Modulo n, arXiv:math/0605019 [math.NT], 2006-2017.
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A010554, A033949, A046145, A046146, A008330, A002233, A071894, A219027.

A046144 := proc(n)
    local a,eulphi,m;
    if n = 1 then
        return 1;
    end if;
    eulphi := numtheory[phi](n) ;
    a := 0 ;
    for m from 0 to n-1 do
        if numtheory[order](m,n) = eulphi then
            a := a + 1 ;
        end if;
    end do:
    a;
end proc: # R. J. Mathar, Jan 12 2016

Prepend[ Table[ If[ IntegerQ[ PrimitiveRoot[n]] , EulerPhi[ EulerPhi[n]], 0], {n, 2, 91}],1] (* Jean-François Alcover, Sep 13 2011 *)

for(i=1, 100, p=0; for(q=1, i, if(gcd(q,i)==1 && znorder(Mod(q,i)) == eulerphi(i), p++)); print1(p, ", ")) /* V. Raman, Nov 22 2012 */

a(n) = my(s=znstar(n)); if(#(s.cyc)>1, 0, eulerphi(s.no)) \\ Jeppe Stig Nielsen, Oct 18 2019

use ntheory ":all"; my @A = map { !defined znprimroot($) ? 0 : euler_phi(euler_phi($)); } 0..10000; say "$ $A[$]" for 1..$#A; # Dana Jacobsen, Apr 28 2017

a(n) is equal to A010554(n) unless n is a term of A033949, in which case a(n)=0.

A046145 Smallest primitive root modulo n, or 0 if no root exists.

Original entry on oeis.org

0, 0, 1, 2, 3, 2, 5, 3, 0, 2, 3, 2, 0, 2, 3, 0, 0, 3, 5, 2, 0, 0, 7, 5, 0, 2, 7, 2, 0, 2, 0, 3, 0, 0, 3, 0, 0, 2, 3, 0, 0, 6, 0, 3, 0, 0, 5, 5, 0, 3, 3, 0, 0, 2, 5, 0, 0, 0, 3, 2, 0, 2, 3, 0, 0, 0, 0, 2, 0, 0, 0, 7, 0, 5, 5, 0, 0, 0, 0, 3, 0, 2, 7, 2, 0, 0, 3, 0, 0, 3, 0, 0, 0, 0, 5, 0, 0, 5, 3, 0, 0

Offset: 0

Eric W. Weisstein

The value 0 at index 0 says 0 has no primitive roots, but the 0 at index 1 says 1 has a primitive root of 0, the only real 0 in the sequence.

a(n) is nonzero if and only if n is 2, 4, or of the form p^k, or 2*p^k where p is an odd prime and k>0. - Tom Edgar, Jun 02 2014

T. D. Noe, Table of n, a(n) for n = 0..10000
Pēteris K. Siliņš, Cross ratios for finite field geometries, Bachelor's Thesis, Univ. Groningen (Netherlands, 2024). See p. 17.
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A046144, A046146, A002233, A071894, A219027, A008330, A010554, A111076, A285512, A285513, A285514.

A046145 := proc(n)
  if n <=1 then
    0;
  else
    pr := numtheory[primroot](n) ;
    if pr = FAIL then
       return 0 ;
    else
       return pr ;
    end if;
  end if;
end proc:
seq(A046145(n),n=0..110) ;  # R. J. Mathar, Jul 08 2010

smallestPrimitiveRoot[n_ /; n <= 1] = 0; smallestPrimitiveRoot[n_] := Block[{pr = PrimitiveRoot[n], g}, If[! NumericQ[pr], g = 0, g = 1; While[g <= pr, If[ CoprimeQ[g, n] && MultiplicativeOrder[g, n] == EulerPhi[n], Break[]]; g++]]; g]; smallestPrimitiveRoot /@ Range[0, 100] (* Jean-François Alcover, Feb 15 2012 *)
f[n_] := Block[{pr = PrimitiveRootList[n]}, If[pr == {}, 0, pr[[1]]]]; Array[f, 105, 0] (* v10.0 Robert G. Wilson v, Nov 04 2014 *)

{ A046145(n) = for(q=1,n-1, if(gcd(q,n)==1 && znorder(Mod(q,n))==eulerphi(n), return(q);)); 0; } /* V. Raman, Nov 22 2012, edited by Max Alekseyev, Apr 20 2017 */

use ntheory ":all"; say "$ ", znprimroot($) || 0  for 0..100; # Dana Jacobsen, Mar 16 2017

Initial terms corrected by Harry J. Smith, Jan 27 2005

A046146 Largest primitive root modulo n, or 0 if no root exists.

Original entry on oeis.org

0, 0, 1, 2, 3, 3, 5, 5, 0, 5, 7, 8, 0, 11, 5, 0, 0, 14, 11, 15, 0, 0, 19, 21, 0, 23, 19, 23, 0, 27, 0, 24, 0, 0, 31, 0, 0, 35, 33, 0, 0, 35, 0, 34, 0, 0, 43, 45, 0, 47, 47, 0, 0, 51, 47, 0, 0, 0, 55, 56, 0, 59, 55, 0, 0, 0, 0, 63, 0, 0, 0, 69, 0, 68, 69, 0, 0, 0, 0, 77, 0, 77, 75, 80, 0, 0

Offset: 0

Eric W. Weisstein

nonn

The value 0 at index 0 says 0 has no primitive roots, but the 0 at index 1 says 1 has a primitive root of 0, the only real 0 in the sequence. - Initial terms corrected by Harry J. Smith, Jan 27 2005

a(n) is nonzero if and only if n is 2, 4, or of the form p^k, or 2*p^k where p is an odd prime and k>0. - Tom Edgar, Jun 02 2014

T. D. Noe, Table of n, a(n) for n = 0..10000
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A046144, A046145, A002233, A071894, A219027, A008330, A010554.

f[n_] := Block[{pr = PrimitiveRootList[n]}, If[pr == {}, 0, pr[[-1]]]]; Array[f, 86, 0] (* Robert G. Wilson v, Nov 03 2014 *)

for(i=0,100,p=0;for(q=1,i-1,if(gcd(q,i)==1&&znorder(Mod(q,i))==eulerphi(i),p=q));print1(p",")) /* V. Raman, Nov 22 2012 */

Initial terms corrected by Harry J. Smith, Jan 27 2005

A088144 Sum of primitive roots of n-th prime.

Original entry on oeis.org

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

A111725 Number of residues modulo n of the maximum order.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 3, 2, 2, 4, 3, 4, 2, 4, 4, 8, 2, 6, 4, 6, 4, 10, 7, 8, 4, 6, 6, 12, 4, 8, 8, 12, 8, 8, 6, 12, 6, 8, 8, 16, 6, 12, 12, 8, 10, 22, 8, 12, 8, 16, 8, 24, 6, 16, 14, 18, 12, 28, 8, 16, 8, 24, 16, 24, 12, 20, 16, 30, 8, 24, 14, 24, 12, 16, 18, 24, 8, 24, 24, 18, 16, 40, 14, 32, 12

Offset: 1

Max Alekseyev, Nov 18 2005

nonn

The maximum order modulo n is given by A002322(n).
a(n) is the number of primitive lambda-roots of n. - Michel Marcus, Mar 17 2016
A primitive lambda-root is an element of maximal order modulo n. - Joerg Arndt, Mar 19 2016
a(n) is odd if and only if n is a factor of 24, i.e., n is in A018253. - Jianing Song, Apr 27 2019

T. D. Noe, Table of n, a(n) for n = 1..10000
P. J. Cameron and D. A. Preece, Notes on primitive lambda-roots, 2009.
P. J. Cameron and D. A. Preece, Primitive lambda-roots, 2014.
R. D. Carmichael, Note on a new number theory function, Bull. Amer. Math. Soc. 16 (1909-10), 232-238.
S. R. Finch, Idempotents and Nilpotents Modulo n, arXiv:math/0605019 [math.NT], 2006-2017.
S. Li, On the number of elements with maximal order in the multiplicative group modulo n, Act. Arithm. 86 (2) (1998) 113, Theorem 2.1

Cf. A002322, A008330, A300064, A300065, A300079, A300080.

LiDelta := proc(q,n)
    local a,p,e,lam,v ;
    a := 0 ;
    lam := numtheory[lambda](n) ;
    for p in numtheory[factorset](n) do
        e := padic[ordp](n,p) ;
        if p =2 and e= 3 and q =2 and padic[ordp](lam,q) = 1 then
            return A083399(n) ;
        elif isprime(q) then
            v := padic[ordp](lam,q) ;
            if modp( numtheory[lambda](p^e),q^v) = 0 then
                a := a+1 ;
            end if;
        end if:
    end do:
    a ;
end proc:
A111725 := proc(n)
    local a,q ;
    a := 1;
    for q in numtheory[factorset](numtheory[lambda](n)) do
        a := a*(1-1/q^LiDelta(q,n)) ;
    end do:
    a*numtheory[phi](n) ;
end proc:
seq(A111725(n),n=1..30) ; # R. J. Mathar, Sep 29 2017

f[list_]:=Count[list,Max[list]];Map[f,Table[Table[MultiplicativeOrder[k,n],{k,Select[Range[n],GCD[#,n]==1&]}],{n,1,100}]]  (* Geoffrey Critzer, Jan 26 2013 *)

{ a(n) = my(r, c, r1); r=1; c=0; for(k=0, n-1, if(gcd(k, n)!=1, next); r1=znorder(Mod(k,n)); if(r1==r, c++); if(r1>r, r=r1; c=1) ); c; }

{ A111725(n) = if(n<3,return(1)); my(k,p); k=znstar(n)[2]; p=factor(k[1])[,1]; eulerphi(n) * prod(i=1,#p, (1-1/p[i]^vecsum(apply(x->valuation(k[1]\x,p[i])==0,k))) ); } \\ Max Alekseyev, Oct 23 2021

For prime n, a(n) = phi(phi(n)) = A010554(n) = phi(n-1). - Nick Hobson, Jan 09 2007
Decompose (Z/nZ)* as a product of cyclic groups C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j, then a(n) = Sum_{d divides psi(n)} (mu(psi(n)/d)*Product{i=1..m} gcd(d, k_i)). This is an immediate corollary from the fact that the number of elements in (Z/nZ)* such that x^d == 1 (mod n) is Product{i=1..m} gcd(d, k_i). Here (Z/nZ)* is the multiplicative group of integers modulo n, psi(n) = A002322(n) and mu(n) = A008683(n). - Jianing Song, Apr 27 2019
From Jianing Song, Oct 12 2021: (Start)
Decompose (Z/nZ)* as a product of cyclic groups C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j, then a(n) = phi(n) * Product_{p prime dividing phi(n)} (1 - 1/p^r(p)), where r(p) is the number of j such that v(k_j,p) = v(k_m,p), v(s,p) is the p-adic valuation of s.
Proof: let G = (Z/nZ)*, G_p be the Sylow p-subgroup of G, then G = Product_{p prime dividing phi(n)} G_p: every element x can be uniquely written as Product_{p prime dividing phi(n)} x_p for x_p in G_p. Let ord(x) be the order of x. Since ord(x_p, x_p') = 1 for distinct p and p', we have ord(x) = Product_{p prime dividing phi(n)} ord(x_p), hence x is of maximal order if and only if each x_p is of maximal order in G_p.
Each G_p is isomorphic to C_{p^(e_1)} x C_{p^(e_2)} x ... x C_{p^(e_m)} for e_1 <= e_2 <= ... <= e_m, e_m > 0. Write x_p = (x_{p,1}, x_{p,2}, ..., x_{p,m}). Suppose that e_m = e_{m-1} = ... = e_{m-r+1} > e_{m-r}, then x_p is of maximal order in G_p if and only of x_{p,j} is of order p^(e_m) for some m-r+1 <= j <= m, so the number of such x_p is p^(e_1) * p^(e_2) * ... * p^(e_{m-r}) * (p^(r*e_m) - p^(r*((e_m)-1))) = |G_p| * (1 - 1/p^r).
An example: n = 15903, then (Z/nZ)* = C_6 x C_18 x C_90. We can see that r(2) = 3, r(3) = 2 and r(5) = 1, so a(15903) = phi(15903) * (1 - 1/2^3) * (1 - 1/3^2) * (1 - 1/5^1) = 6048.
It should be clear that a(n) = phi(phi(n)) if and only if r(p) = 1 for every prime p dividing phi(n), or v(k_{m-1},p) < v(k_m,p) for every prime p dividing phi(n). Otherwise, a(n) > phi(phi(n)). (End)

A241194 Numerator of phi(p-1)/(p-1), where phi is Euler's totient function and p = prime(n).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 1, 5, 3, 4, 1, 2, 2, 11, 6, 14, 4, 10, 12, 1, 4, 20, 5, 1, 2, 16, 26, 1, 3, 2, 24, 8, 22, 18, 4, 4, 1, 41, 21, 44, 4, 36, 1, 3, 10, 8, 12, 56, 6, 14, 48, 4, 2, 1, 65, 33, 4, 22, 12, 46, 36, 16, 12, 4, 39, 8, 2, 86, 28, 5, 89, 20, 10, 2, 95

Offset: 1

T. D. Noe, Apr 17 2014

The denominators are in A241195. The new minima of phi(p-1)/(p-1) occur at primes listed in A241196. The numerator and denominator of those terms are in A241197 and A241198.

For primes p>2, the fraction phi(p - 1)/(p - 1) has the maximum value = 1/2 if and only if p is in A019434. - Geoffrey Critzer, Dec 30 2014

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, p. 117.

T. D. Noe, Table of n, a(n) for n = 1..10000
P. Erdős, On the density of some sequences of numbers, III., J. London Math. Soc. 13 (1938), pp. 119-127.
Imre Kátai, On distribution of arithmetical functions on the set prime plus one, Compositio Math. 19 (1968), pp. 278-289.
I. J. Schoenberg, Über die asymptotische Verteilung reeller Zahlen mod 1, Mathematische Zeitschrift 28:1 (1928), pp. 171-199.

Cf. A000010, A005596, A008330 (phi(prime(n)-1)), A065485, A241195, A241196, A241197, A241198.

Cf. A076512, A006093.

[Numerator(EulerPhi(NthPrime(n)-1)/(NthPrime(n)-1)): n in [1..80]]; // Vincenzo Librandi, Apr 06 2015

seq(numer(numtheory:-phi(ithprime(i)-1)/(ithprime(i)-1)), i=1..100); # Robert Israel, Jan 11 2015

Numerator[Table[EulerPhi[p - 1]/(p - 1), {p, Prime[Range[100]]}]]

lista(nn) = forprime(p=2, nn, print1(numerator(eulerphi(p-1)/(p-1)), ", ")); \\ Michel Marcus, Jan 03 2015

From Amiram Eldar, Jul 31 2020: (Start)
Asymptotic mean: lim_{m->oo} (1/m) * Sum_{n=1..m} a(n)/A241195(n) = 0.373955... (Artin's constant, A005596).
Asymptotic mean of inverse ratio: lim_{m->oo} (1/m) * Sum_{n=1..m} A241195(n)/a(n) = 2.826419... (Murata's constant, A065485). (End)
a(n) = A076512(A006093(n)). - Ridouane Oudra, Mar 24 2025

A103203 Primes which have more primitive roots than any smaller prime.

Original entry on oeis.org

2, 5, 11, 17, 23, 29, 41, 47, 53, 59, 83, 107, 137, 149, 167, 173, 179, 227, 257, 263, 269, 293, 317, 347, 359, 383, 389, 467, 479, 503, 509, 557, 563, 587, 653, 719, 773, 797, 809, 839, 857, 863, 887, 929, 977, 983, 1019, 1049, 1097, 1109, 1187, 1229

Offset: 1

Don Reble, Mar 19 2005

nonn

Jeppe Stig Nielsen, Table of n, a(n) for n = 1..100000

Cf. A103521, A121519, A008330.

my(record=0, r); forprime(p=2, 1500, r=eulerphi(p-1); if(r>record, record=r; print1(p,", "))) \\ Jeppe Stig Nielsen, Oct 18 2019

A219027 Number of non-primitive roots for n, less than n.

Original entry on oeis.org

0, 0, 1, 2, 2, 4, 4, 7, 6, 7, 6, 11, 8, 11, 14, 15, 8, 15, 12, 19, 20, 17, 12, 23, 16, 21, 20, 27, 16, 29, 22, 31, 32, 25, 34, 35, 24, 31, 38, 39, 24, 41, 30, 43, 44, 35, 24, 47, 36, 41, 50, 51, 28, 47, 54, 55, 56, 45, 30, 59, 44, 53, 62, 63, 64, 65, 46, 67, 68

Offset: 1

V. Raman, Nov 10 2012

nonn

a(n) will be the same as A219029(n) except when n is a member of A033949 or n = 1, i.e. n is not 2, 4, prime, power of a prime, twice a prime, or twice a prime power. In such cases, when n is a member of A033949, then a(n) = n-1.

Cf. A008330 (number of primitive roots for the n-th prime, less than n-th prime).
Cf. A046144 (number of primitive roots for n, less than n).
Cf. A010554 (value of phi(phi(n))).
Cf. A219029.

for(i=1,100,p=0;for(q=1,i-1,if(gcd(q,i)>1||znorder(Mod(q,i))!=eulerphi(i),p++));print1(p","))

n-1-A046144(n).

A241196 Primes p at which phi(p-1)/(p-1) reaches a new minimum, where phi is Euler's totient function.

Original entry on oeis.org

2, 3, 7, 31, 211, 2311, 43891, 78541, 120121, 870871, 1381381, 2282281, 4084081, 13123111, 82192111, 106696591, 300690391, 562582021, 892371481, 6915878971, 71166625531, 200560490131

Offset: 1

T. D. Noe, Apr 17 2014

For these p, the numerator and denominator of phi(p-1)/(p-1) are listed in A241197 and A241198. This sequence appears to be related to A073918, the smallest prime which is 1 more than a product of n distinct primes.
By Dirichlet's theorem on primes in arithmetic progressions, for any n there is a prime p such that p-1 is divisible by the primorial A002110(n).  Then phi(p-1)/(p-1) <= Product_{i=1..n} (1 - 1/prime(i)).  Since Sum_{i >= 1} prime(i) diverges, that goes to 0 as n -> infinity.  Thus there are primes with phi(p-1)/(p-1) arbitrarily close to 0. - Robert Israel, Jan 18 2016
5*10^12 < a(23) <= 12234189897931. - Giovanni Resta, Apr 14 2016

R. K. Guy, Unsolved Problems in Number Theory, A2.

Tamiru Jarso, Tim Trudgian, Quadratic residues that are not primitive roots, arXiv:1710.04320 [math.NT], 2017.
Eric Weisstein's World of Mathematics, Euclid Number

Cf. A002110, A008330 (phi(prime(n)-1)), A073918, A241194, A241195.

m:= infinity:
p:= 1:
count:= 0:
while count < 10 do
  p:= nextprime(p);
  r:= numtheory:-phi(p-1)/(p-1);
  if r < m then
     count:= count+1;
     A[count]:= p;
     m:= r;
  fi
od:
seq(A[i],i=1..count); # Robert Israel, Jan 18 2016

tMin = {{2, 1}}; Do[p = Prime[n]; tn = EulerPhi[p - 1]/(p - 1); If[tn < tMin[[-1, -1]], AppendTo[tMin, {p, tn}]], {n, 10^7}]; Transpose[tMin][[1]]

a(20) from Dimitri Papadopoulos, Jan 11 2016

a(21)-a(22) from Giovanni Resta, Apr 14 2016

cp's OEIS Frontend

A060749 Triangle in which n-th row lists all primitive roots modulo the n-th prime.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Extensions

A046144 Number of primitive roots modulo n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Perl

Formula

A046145 Smallest primitive root modulo n, or 0 if no root exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Perl

Extensions

A046146 Largest primitive root modulo n, or 0 if no root exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A088144 Sum of primitive roots of n-th prime.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

A111725 Number of residues modulo n of the maximum order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A241194 Numerator of phi(p-1)/(p-1), where phi is Euler's totient function and p = prime(n).

Views

Author