This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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) 733-753, 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 (* 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: 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 20 01:17 EDT 2019. Contains 325168 sequences. (Running on oeis4.)