login
The OEIS is supported by the many generous donors 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

%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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 10:55 EDT 2024. Contains 371241 sequences. (Running on oeis4.)