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

Author

Wolfdieter Lang, Sep 28 2012

Keywords

• nonn
• tabf

Comments

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.

Examples

			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.
		

References

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

Links

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

Crossrefs

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

Cf. A086145

Programs

Mathematica

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

PARI

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

Formula

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