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
Triangle begins:
[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
AUTHOR
Wolfdieter Lang, May 21 2008
STATUS
approved