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