A219027 -id:A219027 - cp's OEIS frontend

A046144 Number of primitive roots modulo n.

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

A219029 a(n) = n - 1 - phi(phi(n)).

Original entry on oeis.org

-1, 0, 1, 2, 2, 4, 4, 5, 6, 7, 6, 9, 8, 11, 10, 11, 8, 15, 12, 15, 16, 17, 12, 19, 16, 21, 20, 23, 16, 25, 22, 23, 24, 25, 26, 31, 24, 31, 30, 31, 24, 37, 30, 35, 36, 35, 24, 39, 36, 41, 34, 43, 28, 47, 38, 47, 44, 45, 30, 51, 44, 53, 50, 47, 48, 57, 46, 51, 48

Offset: 1

V. Raman, Nov 10 2012

sign

There are exactly n - 1 - phi(phi(n)) non-primitive roots for n, less than n, if n is prime.

a(n) will be the same as A219027(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.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

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

[(n - 1 - EulerPhi(EulerPhi(n))): n in [1..70] ]; // Vincenzo Librandi, Jan 26 2013

Table[n - (EulerPhi[EulerPhi[n]] + 1), {n, 75}] (* Alonso del Arte, Nov 17 2012 *)

for(n=1,100,print1(n-1-eulerphi(eulerphi(n))","))

a(n) = n - 1 - A010554(n). - V. Raman, Nov 22 2012

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

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

A219029 a(n) = n - 1 - phi(phi(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

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