login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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 (nickh(AT)qbyte.org), 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

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

CROSSREFS

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

Sequence in context: A117910 A275435 A029267 * A302257 A324748 A320387

Adjacent sequences:  A111722 A111723 A111724 * A111726 A111727 A111728

KEYWORD

nonn

AUTHOR

Max Alekseyev, Nov 18 2005

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 29 21:18 EDT 2020. Contains 338074 sequences. (Running on oeis4.)