A139366 Table with the order r=r(N,n) of n modulo N, for given N and n, with gcd(N,n)=1.

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

Offset: 1

Author

Wolfdieter Lang, May 21 2008

Keywords

• nonn
• easy
• tabl
• look

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.

Examples

			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).
		

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.

Crossrefs

Cf. A036391 (row sums).

See A250211 for another version.

Programs

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

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 *)

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

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.