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
Keywords
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
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)
Comments