|
| |
|
|
A216327
|
|
Irregular triangle of multiplicative orders mod n for the elements of the smallest positive reduced residue system mod n.
|
|
4
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
