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,4

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.

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

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

Example

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.

Mathematica

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

Prog

(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

Crossrefs

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

Cf. A086145

Sequence in context: A002852 A266081 A188440 * A099875 A079499 A166235

Adjacent sequences: A216324 A216325 A216326 * A216328 A216329 A216330

Keyword

nonn,tabf

Author

Wolfdieter Lang, Sep 28 2012

Status

approved