A111725 Number of residues modulo n of the maximum order.

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

Author

Max Alekseyev, Nov 18 2005

Keywords

• nonn

Comments

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

Links

• 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

Crossrefs

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

Programs

Maple

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

Mathematica

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

PARI

{ 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; }

PARI

{ 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

Formula

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)