A053200 Binomial coefficients C(n,k) reduced modulo n, read by rows; T(0,0)=0 by convention.

0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 2, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 3, 2, 3, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 4, 0, 6, 0, 4, 0, 1, 1, 0, 0, 3, 0, 0, 3, 0, 0, 1, 1, 0, 5, 0, 0, 2, 0, 0, 5, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 6, 4, 3, 0, 0, 0, 3, 4, 6, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 0

Author

Asher Auel, Dec 12 1999

Keywords

• nonn
• tabl
• nice

Comments

Pascal's triangle read by rows, where row n is read mod n.

A number n is a prime if and only if (1+x)^n == 1+x^n (mod n), i.e., if and only if the n-th row is 1,0,0,...,0,1. This result underlies the proof of Agrawal, Kayal and Saxena that there is a polynomial-time algorithm for primality testing. - N. J. A. Sloane, Feb 20 2004

A020475(n) = number of zeros in n-th row, for n > 0. - Reinhard Zumkeller, Jan 01 2013

Examples

			Row 4 = 1 mod 4, 4 mod 4, 6 mod 4, 4 mod 4, 1 mod 4 = 1, 0, 2, 0, 1.
Triangle begins:
  0;
  0,0;
  1,0,1;
  1,0,0,1;
  1,0,2,0,1;
  1,0,0,0,0,1;
  1,0,3,2,3,0,1;
  1,0,0,0,0,0,0,1;
  1,0,4,0,6,0,4,0,1;
  1,0,0,3,0,0,3,0,0,1;
  1,0,5,0,0,2,0,0,5,0,1;
  1,0,0,0,0,0,0,0,0,0,0,1;
  1,0,6,4,3,0,0,0,3,4,6,0,1;
  1,0,0,0,0,0,0,0,0,0,0,0,0,1;
		

Links

• T. D. Noe, Rows n = 0..100 of triangle, flattened
• M. Agrawal, N. Kayal & N. Saxena, PRIMES is in P, Annals of Maths., 160:2 (2004), pp. 781-793. [alternate link]
• Index entries for triangles and arrays related to Pascal's triangle

Crossrefs

Row sums give A053204. Cf. A053201, A053202, A053203, A007318 (Pascal's triangle).

Cf. also A092241.

Cf. A053214 (central terms, apart from initial 1).

Programs

Haskell

a053200 n k = a053200_tabl !! n !! k
a053200_row n = a053200_tabl !! n
a053200_tabl = [0] : zipWith (map . flip mod) [1..] (tail a007318_tabl)
-- Reinhard Zumkeller, Jul 10 2015, Jan 01 2013

Maple

f := n -> seriestolist( series( expand( (1+x)^n ) mod n, x, n+1)); # N. J. A. Sloane

Mathematica

Flatten[Join[{0},Table[Mod[Binomial[n,Range[0,n]],n],{n,20}]]] (* Harvey P. Dale, Apr 29 2013 *)

PARI

T(n,k)=if(n, binomial(n,k)%n, 0) \\ Charles R Greathouse IV, Feb 07 2017

Extensions

Corrected by T. D. Noe, Feb 08 2008

Edited by N. J. A. Sloane, Aug 29 2008 at the suggestion of R. J. Mathar