A111725 -id:A111725 - cp's OEIS frontend

A216327 Irregular triangle of multiplicative orders mod n for the elements of the smallest positive reduced residue system mod n.

1, 1, 1, 2, 1, 2, 1, 4, 4, 2, 1, 2, 1, 3, 6, 3, 6, 2, 1, 2, 2, 2, 1, 6, 3, 6, 3, 2, 1, 4, 4, 2, 1, 10, 5, 5, 5, 10, 10, 10, 5, 2, 1, 2, 2, 2, 1, 12, 3, 6, 4, 12, 12, 4, 3, 6, 12, 2, 1, 6, 6, 3, 3, 2, 1, 4, 2, 4, 4, 2, 4, 2, 1, 4, 4, 2, 2, 4, 4, 2

Offset: 1

Wolfdieter Lang, Sep 28 2012

The sequence of the row lengths is phi(n) = A000010 (Euler's totient).
For the notion 'reduced residue system mod n' which has, as a set, order phi(n) = A000010(n), see e.g., the Apostol reference p. 113. Here such a system with the smallest positive numbers is used. (In the Apostol reference 'order of a modulo n' is called 'exponent of a modulo n'. See the definition on p. 204.)
See A038566 where the reduced residue system mod n appears in row n.
In the chosen smallest reduced residue system mod n one can replace each element by any congruent mod n one, and the given order modulo n list will, of course, be the same. E.g., n=5, {6, -3, 13, -16} also has the orders modulo 5:  1  4  4  2, respectively.
Each order modulo n divides phi(n). See the Niven et al. reference, Corollary 2.32, p. 98.
The maximal order modulo n is given in A002322(n).
For the analog table of orders Modd n see A216320.

			This irregular triangle begins:
n\k 1  2  3  4  5  6  7  8  9  10 11 12  13 14  15 16 17 18
1:  1
2:  1
3:  1  2
4:  1  2
5:  1  4  4  2
6:  1  2
7:  1  3  6  3  6  2
8:  1  2  2  2
9:  1  6  3  6  3  2
10: 1  4  4  2
11: 1 10  5  5  5 10 10 10  5   2
12: 1  2  2  2
13: 1 12  3  6  4 12 12  4  3   6 12  2
14: 1  6  6  3  3  2
15: 1  4  2  4  4  2  4  2
16: 1  4  4  2  2  4  4  2
17: 1  8 16  4 16 16 16  8  8  16 16 16   4 16   8  2
18: 1  6  3  6  3  2
19: 1 18 18  9  9  9  3  6  9  18  3  6  18 18  18  9  9  2
20: 1  4  4  2  2  4  4  2
...
a(3,2) = 2 because A038566(3,2) = 2 and 2^1 == 2 (mod 3), 2^2 = 4 == 1 (mod 3).
a(7,3) = 6 because A038566(7,3) = 3 and 3^1 == 3 (mod 7), 3^2 = 9 == 2 (mod 7), 3^3 = 2*3 == 6 (mod 7),  3^4 == 6*3 == 4 (mod 7), 3^5 == 4*3 == 5 (mod 7) and  3^6 == 5*3 == 1 (mod 7). The notation == means 'congruent'.
The maximal order modulo 7 is 6 = A002322(7) = phi(7), and it appears twice: A111725(7) = 2.
The maximal order modulo 14 is 6 = A002322(14) = 1*6.

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976.
I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to the Theory of Numbers, Fifth edition, Wiley, 1991.

Michael De Vlieger, Table of n, a(n) for n = 1..12232 (rows n = 1..200, flattened.)

Cf. A038566, A002322 (maximal order), A111725 (multiplicity of max order), A216320 (Modd n analog).

Cf. A086145

Table[Table[MultiplicativeOrder[k,n],{k,Select[Range[n],GCD[#,n]==1&]}],{n,1,13}]//Grid  (* Geoffrey Critzer, Jan 26 2013 *)

rowa(n) = select(x->gcd(n, x)==1, [1..n]); \\ A038566
row(n) = apply(znorder, apply(x->Mod(x, n), rowa(n))); \\ Michel Marcus, Sep 12 2023

a(n,k) = order A038566(n,k) modulo n, n >= 1, k=1, 2, ..., phi(n) = A000010(n). This is the order modulo n of the k-th element of the smallest reduced residue system mod n (when their elements are listed increasingly).

A300064 Numbers k such that there are exactly phi(phi(k)) residues modulo k of the maximum order.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 25, 26, 27, 29, 30, 31, 32, 34, 35, 37, 38, 39, 40, 41, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 58, 59, 60, 61, 62, 64, 67, 68, 70, 71, 73, 74, 75, 78, 79, 81, 82, 83, 85, 86, 87, 89, 90, 94, 95, 96, 97, 98, 100, 101, 102, 103, 104, 105, 106, 107, 109, 110

Offset: 1

Max Alekseyev, Feb 23 2018

nonn

Numbers k such that A111725(k) = A010554(k).
Contains subsequences of the primes (A000040) and the prime powers (A000961) except 2^3 = 8.
The ratio a(n)/n tends to infinity as n grows (Müller and Schlage-Puchta, 2004).
Decompose (Z/kZ)* 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 k is a term if and only if m <= 1, or v(k_{m-1},p) < v(k_m,p) holds for all primes p dividing k_m = psi(k), where v(s,p) is the p-adic valuation of s. Otherwise, there are more than phi(phi(k)) residues modulo k of the maximum order. See my Oct 12 2021 formula for A111725 for a proof. - Jianing Song, Oct 20 2021

Amiram Eldar, Table of n, a(n) for n = 1..10000
Peter J. Cameron and D. A. Preece, Primitive lambda-roots, 2014.
T. W. Müller and J.-C. Schlage-Puchta, On the number of primitive lambda-roots, Acta Arithmetica, Vol. 115 (2004), pp. 217-223.

Complement of A300065.
Set union of A300079 and A000040.
Set union of A300080 and A000961 \ {8}.
Cf. A000010, A002322, A010554, A111725.

q[n_] := Count[(t = Table[MultiplicativeOrder[k, n], {k, Select[Range[n], CoprimeQ[n, #] &]}]), Max[t]] == EulerPhi[EulerPhi[n]]; Select[Range[100], q] (* Amiram Eldar, Oct 12 2021 *)

isA300064(n) = my(v=znstar(n)[2], l=#v); if(l<2, return(1), my(U=v[1], L=v[2], d=factor(U), w=omega(U)); for(i=1, w, if(valuation(L,d[i,1]) == d[i,2], return(0))); return(1)) \\ Jianing Song, Oct 20 2021

A300065 Numbers k such that the number of residues modulo k of the maximum order is different from phi(phi(k)).

Original entry on oeis.org

8, 12, 21, 24, 28, 33, 36, 42, 44, 56, 57, 63, 65, 66, 69, 72, 76, 77, 80, 84, 88, 91, 92, 93, 99, 108, 114, 117, 124, 126, 129, 130, 132, 133, 138, 141, 145, 147, 152, 154, 161, 168, 171, 172, 177, 182, 184, 185, 186, 188, 189, 195, 196, 198, 201, 207, 208, 209, 213, 216, 217, 228, 231, 234, 236, 237, 240, 248, 249, 252, 253, 258, 260, 264, 265, 266, 268, 273, 275, 276, 279, 282

Offset: 1

Max Alekseyev, Feb 23 2018

nonn

Numbers k such that A111725(k) is not equal to A010554(k).

The ratio a(n)/n tends to 1 as n grows.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Peter J. Cameron and D. A. Preece, Primitive lambda-roots, 2014.
T. W. Müller and J.-C. Schlage-Puchta, On the number of primitive lambda-roots, Acta Arithmetica, Vol. 115 (2004), pp. 217-223.

Complement of A300064.
Union of {8} and set difference of A024619 and A300080.
Cf. A000010, A002322, A010554, A111725, A300079.

q[n_] := Count[(t = Table[MultiplicativeOrder[k, n], {k, Select[Range[n], CoprimeQ[n, #] &]}]), Max[t]] != EulerPhi[EulerPhi[n]]; Select[Range[300], q] (* Amiram Eldar, Oct 12 2021 *)

A300079 Composite numbers k such that there are exactly phi(phi(k)) residues modulo k of the maximum order.

Original entry on oeis.org

4, 6, 9, 10, 14, 15, 16, 18, 20, 22, 25, 26, 27, 30, 32, 34, 35, 38, 39, 40, 45, 46, 48, 49, 50, 51, 52, 54, 55, 58, 60, 62, 64, 68, 70, 74, 75, 78, 81, 82, 85, 86, 87, 90, 94, 95, 96, 98, 100, 102, 104, 105, 106, 110, 111, 112, 115, 116, 118, 119, 120, 121, 122, 123, 125, 128, 134, 135, 136, 140, 142, 143, 144, 146, 148, 150, 153

Offset: 1

Max Alekseyev, Feb 24 2018

nonn

Composite numbers k such that A111725(k) = A010554(k).

Contains as a subsequence the nontrivial prime powers (A246547) except 2^3 = 8.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Subsequence of A300064.
Set difference of A002808 and A300065.
Contains A300080 as a subsequence.
Cf. A000010, A002322, A010554, A111725, A246547.

q[n_] := Count[(t = Table[MultiplicativeOrder[k, n], {k, Select[Range[n], CoprimeQ[n, #] &]}]), Max[t]] == EulerPhi[EulerPhi[n]]; Select[Range[150], CompositeQ[#] && q[#] &] (* Amiram Eldar, Oct 12 2021 *)

A300080 Numbers k that are not prime powers, and have exactly phi(phi(k)) residues modulo k of the maximum order.

Original entry on oeis.org

6, 10, 14, 15, 18, 20, 22, 26, 30, 34, 35, 38, 39, 40, 45, 46, 48, 50, 51, 52, 54, 55, 58, 60, 62, 68, 70, 74, 75, 78, 82, 85, 86, 87, 90, 94, 95, 96, 98, 100, 102, 104, 105, 106, 110, 111, 112, 115, 116, 118, 119, 120, 122, 123, 134, 135, 136, 140, 142, 143, 144, 146, 148, 150, 153, 155, 156, 158, 159, 160, 162, 164, 165, 166

Offset: 1

Max Alekseyev, Feb 24 2018

nonn

Numbers k with at least two distinct prime factors (A024619) such that A111725(k) = A010554(k).

Amiram Eldar, Table of n, a(n) for n = 1..10000

Set difference of: A300064 and A000961, A300079 and A246547, A024619 and A300065.

Cf. A000010, A002322, A010554, A111725.

q[n_] := Count[(t = Table[MultiplicativeOrder[k, n], {k, Select[Range[n], CoprimeQ[n, #] &]}]), Max[t]] == EulerPhi[EulerPhi[n]]; Select[Range[200], PrimeNu[#] > 1 && q[#] &] (* Amiram Eldar, Oct 12 2021 *)

A270562 a(n) is the largest number m satisfying lambda(m)=n, or zero if there is no solution, where lambda(m) is Carmichael's lambda function A002322(m).

Original entry on oeis.org

2, 24, 0, 240, 0, 504, 0, 480, 0, 264, 0, 65520, 0, 0, 0, 16320, 0, 28728, 0, 13200, 0, 552, 0, 131040, 0, 0, 0, 6960, 0, 171864, 0, 32640, 0, 0, 0, 138181680, 0, 0, 0, 1082400, 0, 151704, 0, 5520, 0, 1128, 0, 4455360, 0, 0, 0, 12720, 0, 86184, 0, 13920, 0, 1416, 0, 6814407600, 0, 0, 0, 65280

Offset: 1

Joerg Arndt, Mar 19 2016

nonn

a(n) is the largest modulus m such that the largest order of any element in the multiplicative group modulo m is n; a(n) is zero if there is no such group with largest order n.
Omitting the zeros gives A143407.
a(n) = 0 if n is not a term of A002174.

Gheorghe Coserea, Table of n, a(n) for n = 1..50005
R. D. Carmichael, Note on a new number theory function, Bull. Amer. Math. Soc. 16 (1910), 232-238.

Cf. A002322, A002174, A051222, A143407, A270564, A111725.

A247176 Largest number of maximal order mod n.

Original entry on oeis.org

0, 1, 2, 3, 3, 5, 5, 7, 5, 7, 8, 11, 11, 5, 13, 13, 14, 11, 15, 17, 19, 19, 21, 23, 23, 19, 23, 23, 27, 23, 24, 29, 29, 31, 33, 31, 35, 33, 37, 37, 35, 31, 34, 41, 43, 43, 45, 43, 47, 47, 46, 45, 51, 47, 53, 53, 53, 55, 56, 53, 59, 55, 61, 61, 63, 61, 63, 65, 67, 67, 69, 67

Offset: 1

Eric Chen, Nov 29 2014

			a(18) = 11 because the largest possible order mod 18 is 6, and because 16, 15, 14, and 12 are not coprime to 18, and the orders of 17 and 13 to mod 18 are 2 and 3, not the largest possible order, and the order of 11 to mod 18 is 6, so a(18) = 11.

Eric Chen, Table of n, a(n) for n = 1..1000

Cf. A002322 (orders), same as A046146 for n with primitive roots, A071894 (for primes).

Cf. A111076, A111725, A046145, A046144, A001918, A008330.

prms={}; f[n_] = Block[If[MultiplicativeOrder[p, n]=CarmichaelLambda[n], Join[prms, p]]; prms[-1]]; Array[f, 128]

carmichaellambda(n)=lcm(znstar(n)[2]);
for(i=1, 128, p=0; for(q=1, i-1, if(gcd(q, i)==1&&znorder(Mod(q, i))==carmichaellambda(i), p=q)); print1(p", "))

a(68) corrected by Eric Chen, Jun 01 2015

A250211 Square array read by antidiagonals: A(m,n) = multiplicative order of m mod n, or 0 if m and n are not coprime.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 0, 0, 0, 1, 1, 1, 1, 2, 4, 1, 1, 0, 2, 0, 4, 0, 1, 1, 1, 0, 1, 2, 0, 3, 1, 1, 0, 1, 0, 0, 0, 6, 0, 1, 1, 1, 2, 2, 1, 2, 3, 2, 6, 1, 1, 0, 0, 0, 4, 0, 6, 0, 0, 0, 1, 1, 1, 1, 1, 4, 1, 2, 2, 3, 4, 10, 1, 1, 0, 2, 0, 2, 0, 0, 0, 6, 0, 5, 0, 1, 1, 1, 0, 2, 0, 0, 1, 2, 0, 0, 5, 0, 12, 1

Offset: 1

Eric Chen, Dec 29 2014

Read by antidiagonals:
m\n   1    2    3    4    5    6    7    8    9    10    11    12    13
1     1    1    1    1    1    1    1    1    1     1     1     1     1
2     1    0    2    0    4    0    3    0    6     0    10     0    12
3     1    1    0    2    4    0    6    2    0     4     5     0     3
4     1    0    1    0    2    0    3    0    3     0     5     0     6
5     1    1    2    1    0    2    6    2    6     0     5     2     4
6     1    0    0    0    1    0    2    0    0     0    10     0    12
7     1    1    1    2    4    1    0    2    3     4    10     2    12
8     1    0    2    0    4    0    1    0    2     0    10     0     4
9     1    1    0    1    2    0    3    1    0     2     5     0     3
10    1    0    1    0    0    0    6    0    1     0     2     0     6
11    1    1    2    2    1    2    3    2    6     1     0     2    12
12    1    0    0    0    4    0    6    0    0     0     1     0     2
13    1    1    1    1    4    1    2    2    3     4    10     1     0
etc.
A(m,n) = Least k>0 such that m^k=1 (mod n), or 0 if no such k exists.
It is easy to prove that column n has period n.
A(1,n) = 1, A(m,1) =1.
If A(m,n) differs from 0, it is period length of 1/n in base m.
The maximum number in column n is psi(n) (A002322(n)), and all numbers in column n (except 0) divide psi(n), and all factors of psi(n) are in column n.
Except the first row, every row contains all natural numbers.

			A(3,7) = 6 because:
3^0 = 1 (mod 7)
3^1 = 3 (mod 7)
3^2 = 2 (mod 7)
3^3 = 6 (mod 7)
3^4 = 4 (mod 7)
3^5 = 5 (mod 7)
3^6 = 1 (mod 7)
...
And the period is 6, so A(3,7) = 6.

Cf. A002322, A111076, A111725, A001918, A008330, A007733, A002326, A007732, A051626, A066799.

See A139366 for another version.

f:= proc(m,n)
  if igcd(m,n) <> 1 then 0
  elif n=1 then 1
  else numtheory:-order(m,n)
  fi
end proc:
seq(seq(f(t-j,j),j=1..t-1),t=2..65); # Robert Israel, Dec 30 2014

a250211[m_, n_] = If[GCD[m, n] == 1, MultiplicativeOrder[m, n], 0]
Table[a250211[t-j, j], {t, 2, 65}, {j, 1, t-1}]

A251865 Irregular triangle read by rows in which row n lists the maximal-order elements (

Original entry on oeis.org

0, 1, 2, 3, 2, 3, 5, 3, 5, 3, 5, 7, 2, 5, 3, 7, 2, 6, 7, 8, 5, 7, 11, 2, 6, 7, 11, 3, 5, 2, 7, 8, 13, 3, 5, 11, 13, 3, 5, 6, 7, 10, 11, 12, 14, 5, 11, 2, 3, 10, 13, 14, 15, 3, 7, 13, 17, 2, 5, 10, 11, 17, 19, 7, 13, 17, 19, 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 5, 7, 11, 13, 17, 19, 23, 2, 3, 8, 12, 13, 17, 22, 23

Offset: 1

Eric Chen, May 20 2015

Conjecture: Triangle contains all nonsquare numbers infinitely many times.
The orders of the numbers in n-th row mod n are equal to A002322(n).
First and last terms of the n-th row are A111076(n) and A247176(n).
Length of the n-th row is A111725(n).
The n-th row is the same as A046147 for n with primitive roots.

			Read by rows:
n     maximal-order elements (<n) mod n
1     0
2     1
3     2
4     3
5     2, 3
6     5
7     3, 5
8     3, 5, 7
9     2, 5
10    3, 7
11    2, 6, 7, 8
12    5, 7, 11
13    2, 6, 7, 11
14    3, 5
15    2, 7, 8, 13
16    3, 5, 11, 13
17    3, 5, 6, 7, 10, 11, 12, 14
18    5, 11
19    2, 3, 10, 13, 14, 15
20    3, 7, 13, 17
etc.

Eric Chen, First 160 rows of triangle, flattened
Eric Chen, First 1000 rows of triangle

Cf. A111076, A247176, A111725, A046147, A046145, A046146, A046144, A060749, A001918, A071894, A008330.

a[n_] := Select[Range[0, n-1], GCD[#, n] == 1 && MultiplicativeOrder[#, n] == CarmichaelLambda[n]& ]; Table[a[n], {n, 1, 36}]

c(n)=lcm((znstar(n))[2])
a(n)=for(k=0,n-1,if(gcd(k, n)==1 && znorder(Mod(k,n))==c(n), print1(k, ",")))
n=1; while(n<37, a(n); n++)

cp's OEIS Frontend

A216327 Irregular triangle of multiplicative orders mod n for the elements of the smallest positive reduced residue system mod n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A300064 Numbers k such that there are exactly phi(phi(k)) residues modulo k of the maximum order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A300065 Numbers k such that the number of residues modulo k of the maximum order is different from phi(phi(k)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A300079 Composite numbers k such that there are exactly phi(phi(k)) residues modulo k of the maximum order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A300080 Numbers k that are not prime powers, and have exactly phi(phi(k)) residues modulo k of the maximum order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A270562 a(n) is the largest number m satisfying lambda(m)=n, or zero if there is no solution, where lambda(m) is Carmichael's lambda function A002322(m).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A247176 Largest number of maximal order mod n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A250211 Square array read by antidiagonals: A(m,n) = multiplicative order of m mod n, or 0 if m and n are not coprime.

Views

Author

Keywords

Comments

Examples

Crossrefs