%I #33 Jul 01 2023 08:28:10
%S 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,
%T 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,
%U 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
%N Table with the order r=r(N,n) of n modulo N, for given N and n, with gcd(N,n)=1.
%C 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.
%C 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).
%C The period r is used for factoring integers in quantum computing. See e.g. the Ekert and Jozsa reference.
%H Reinhard Zumkeller, <a href="/A139366/b139366.txt">Rows n = 1..120 of triangle, flattened</a>
%H A. Ekert and R. Josza, <a href="http://phys.uni-sofia.bg/~svetivanov/FourierPapers/1996%20-%20(Th)%20Shor%20-%20Ekert%20-%20RevModPhys.pdf">Quantum computation and Shor's factoring algorithm</a>, Rev. Mod. Phys. 68 (1996) 733-753, sect. IV and Appendix A.
%H Wolfdieter Lang, <a href="/A139366/a139366.txt">First 15 rows and more</a>
%F 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.
%e Triangle begins:
%e [0];
%e [1,0];
%e [1,2,0];
%e [1,0,2,0];
%e [1,4,4,2,0];
%e ...
%e 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).
%t 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 *)
%o (PARI) r(N,n)=if(N<2||gcd(n,N)>1,0,znorder(Mod(n,N)))
%o for(N=1,9,for(n=1,N,print1(r(N,n)", "))) \\ _Charles R Greathouse IV_, Feb 18 2013
%o (Haskell)
%o a139366 1 1 = 0
%o a139366 n k | gcd n k > 1 = 0
%o | otherwise = head [r | r <- [1..], k ^ r `mod` n == 1]
%o a139366_row n = map (a139366 n) [1..n]
%o a139366_tabl = map a139366_row [1..]
%o -- _Reinhard Zumkeller_, May 01 2013
%Y Cf. A036391 (row sums).
%Y See A250211 for another version.
%K nonn,easy,tabl,look
%O 1,5
%A _Wolfdieter Lang_, May 21 2008
|