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

Author

Eric W. Weisstein

Keywords

• nonn

Links

• 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.

Crossrefs

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

Programs

Maple

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

Mathematica

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

PARI

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 */

PARI

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

Perl

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

Formula

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