login
This site is supported by donations to The OEIS Foundation.

 

Logo


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.

License Agreements, Terms of Use, Privacy Policy. .

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