

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 the 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 puts 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) 733753, sect. IV and Appendix A.
W. Lang, First 15 rows and more


FORMULA

r(N,n) is smallest positive number with n^r congruent 1(mod N), n=1..N, if gcd(N,n)=1, else 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 congruent to 3 (mod 5), 3^2 congruent to 4 (mod 5), 3^3 congruent to 2 (mod 5), 3^4 congruent to 1 (mod 5). Hence F(5,3;a+4) congruent 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 (* JeanFrançois Alcover, Aug 19 2013 *)


PROG

(PARI) r(N, n)=if(N<2gcd(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: A049771 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



