|
| |
|
|
A139366
|
|
Table with the order r=r(N,n) of n modulo N, for given N and n, with gcd(N,n)=1.
|
|
4
|
|
|
|
0, 1, 0, 1, 2, 0, 1, 0, 2, 0, 1, 4, 4, 2, 0, 1, 0, 0, 0, 2, 0, 1, 3, 6, 3, 6, 2, 0, 1, 0, 2, 0, 2, 0, 2, 0, 1, 6, 0, 3, 6, 0, 3, 2, 0, 1, 0, 4, 0, 0, 0, 4, 0, 2, 0, 1, 10, 5, 5, 5, 10, 10, 10, 5, 2, 0, 1, 0, 0, 0, 2, 0, 2, 0, 0, 0, 2, 0, 1, 12, 3, 6, 4, 12, 12, 4, 3, 6, 12, 2, 0, 1, 0, 6, 0, 6, 0, 0, 0, 3, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
In the table a 0 appears for 1 <= n <= N if gcd(N,n) is not 1. In particular, this is the case for the main diagonal with N > 1. Also for N=n=1 one sets r=0 because 1^m congruent to 0 (mod 1) for all m.
For given N and n with gcd(N,n)=1 the function F(N,n;a):=n^a (mod N) has period r=r(N,n): F(N,n;a+r) congruent F(N,n;a) (mod N).
The period r is used for factoring integers in quantum computing. See e.g. the Ekert and Jozsa reference.
|
|
|
LINKS
|
Reinhard Zumkeller, Rows n = 1..120 of triangle, flattened
A. Ekert and R. Josza, Quantum computation and Shor's factoring algorithm, Rev. Mod. Phys. 68 (1996) 733-753, sect. IV and Appendix A.
Wolfdieter Lang, First 15 rows and more
|
|
|
FORMULA
|
r(N,n) is the smallest positive number with n^r == 1 (mod N), n=1..N, if gcd(N,n)=1, otherwise 0. This r is called the order of n (mod N) if gcd(N,n)=1.
|
|
|
EXAMPLE
|
[0]; [1,0]; [1,2,0]; [1,0,2,0]; [1,4,4,2,0]; ...
For N=5, the order r of 3 (mod 5) is 4 because 3^1 == 3 (mod 5), 3^2 == 4 (mod 5), 3^3 == 2 (mod 5), 3^4 == 1 (mod 5). Hence F(5,3;a+4) == F(5,3;a) (mod 5).
|
|
|
MATHEMATICA
|
r[n_, k_] := If[ CoprimeQ[k, n], MultiplicativeOrder[k, n], 0]; Table[r[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Aug 19 2013 *)
|
|
|
PROG
|
(PARI) r(N, n)=if(N<2||gcd(n, N)>1, 0, znorder(Mod(n, N)))
for(N=1, 9, for(n=1, N, print1(r(N, n)", "))) \\ Charles R Greathouse IV, Feb 18 2013
(Haskell)
a139366 1 1 = 0
a139366 n k | gcd n k > 1 = 0
| otherwise = head [r | r <- [1..], k ^ r `mod` n == 1]
a139366_row n = map (a139366 n) [1..n]
a139366_tabl = map a139366_row [1..]
-- Reinhard Zumkeller, May 01 2013
|
|
|
CROSSREFS
|
Cf. A036391 (row sums).
See A250211 for another version.
Sequence in context: A352514 A158944 A156663 * A049767 A286351 A091394
Adjacent sequences: A139363 A139364 A139365 * A139367 A139368 A139369
|
|
|
KEYWORD
|
nonn,easy,tabl,look
|
|
|
AUTHOR
|
Wolfdieter Lang May 21 2008, Oct 06 2008
|
|
|
STATUS
|
approved
|
| |
|
|
