cp's OEIS Frontend

A111725 Number of residues modulo n of the maximum order.

%I A111725 #50 Feb 12 2024 08:39:54
%S A111725 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,
%T A111725 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,
%U A111725 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
%N A111725 Number of residues modulo n of the maximum order.
%C A111725 The maximum order modulo n is given by A002322(n).
%C A111725 a(n) is the number of primitive lambda-roots of n. - _Michel Marcus_, Mar 17 2016
%C A111725 A primitive lambda-root is an element of maximal order modulo n. - _Joerg Arndt_, Mar 19 2016
%C A111725 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
%H A111725 T. D. Noe, <a href="/A111725/b111725.txt">Table of n, a(n) for n = 1..10000</a>
%H A111725 P. J. Cameron and D. A. Preece, <a href="http://www.maths.qmul.ac.uk/~pjc/csgnotes/lambda.pdf">Notes on primitive lambda-roots</a>, 2009.
%H A111725 P. J. Cameron and D. A. Preece, <a href="https://cameroncounts.files.wordpress.com/2014/01/plr1.pdf">Primitive lambda-roots</a>, 2014.
%H A111725 R. D. Carmichael, <a href="http://dx.doi.org/10.1090/S0002-9904-1910-01892-9">Note on a new number theory function</a>, Bull. Amer. Math. Soc. 16 (1909-10), 232-238.
%H A111725 S. R. Finch, <a href="https://arxiv.org/abs/math/0605019">Idempotents and Nilpotents Modulo n</a>, arXiv:math/0605019 [math.NT], 2006-2017.
%H A111725 S. Li, <a href="http://pldml.icm.edu.pl/pldml/element/bwmeta1.element.bwnjournal-article-aav86i2p113bwm">On the number of elements with maximal order in the multiplicative group modulo n</a>, Act. Arithm. 86 (2) (1998) 113, Theorem 2.1
%F A111725 For prime n, a(n) = phi(phi(n)) = A010554(n) = phi(n-1). - _Nick Hobson_, Jan 09 2007
%F A111725 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
%F A111725 From _Jianing Song_, Oct 12 2021: (Start)
%F A111725 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.
%F A111725 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.
%F A111725 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).
%F A111725 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.
%F A111725 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)
%p A111725 LiDelta := proc(q,n)
%p A111725     local a,p,e,lam,v ;
%p A111725     a := 0 ;
%p A111725     lam := numtheory[lambda](n) ;
%p A111725     for p in numtheory[factorset](n) do
%p A111725         e := padic[ordp](n,p) ;
%p A111725         if p =2 and e= 3 and q =2 and padic[ordp](lam,q) = 1 then
%p A111725             return A083399(n) ;
%p A111725         elif isprime(q) then
%p A111725             v := padic[ordp](lam,q) ;
%p A111725             if modp( numtheory[lambda](p^e),q^v) = 0 then
%p A111725                 a := a+1 ;
%p A111725             end if;
%p A111725         end if:
%p A111725     end do:
%p A111725     a ;
%p A111725 end proc:
%p A111725 A111725 := proc(n)
%p A111725     local a,q ;
%p A111725     a := 1;
%p A111725     for q in numtheory[factorset](numtheory[lambda](n)) do
%p A111725         a := a*(1-1/q^LiDelta(q,n)) ;
%p A111725     end do:
%p A111725     a*numtheory[phi](n) ;
%p A111725 end proc:
%p A111725 seq(A111725(n),n=1..30) ; # _R. J. Mathar_, Sep 29 2017
%t A111725 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 *)
%o A111725 (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; }
%o A111725 (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
%Y A111725 Cf. A002322, A008330, A300064, A300065, A300079, A300080.
%K A111725 nonn
%O A111725 1,5
%A A111725 _Max Alekseyev_, Nov 18 2005