login
A111725
Number of residues modulo n of the maximum order.
10
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,5
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
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.
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)
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Max Alekseyev, Nov 18 2005
STATUS
approved