Binom eng dvi

Amazing properties of binomial coefficients - 2

“The official theoretical source” for this set of problems is Vinberg’s article [1]. Particularly the following theorems are considered to be known.

1. 
   Wilson’s theorem. For any prime p (and for primes only) the equivalence holds (p − 1)! ≡ −1 (mod p).
   
2. 
   Lukas’ theorem. Write the numbers n and k in base p:
   

d 1 0 1 0d−1 d d−1
n = n p^d + n p^d−1 + . . . + n p + n , k = k p^d + k p^d−1 + . . . + k p + k . (1)

k
Then ⁿ
_≡ n_d k_d
ⁿd−1 ^kd−1

· . . . · ⁿ¹

k₁

ⁿ⁰ (mod p) .

3. 
   
   k
   
   k₀
   ^{Kummer’s theorem. The exponent ord}p n ^{is equal to the number of “carries” when we add k and £ = n − k in}
   

base p.

4. 
   
   p
   Wolstenholme’s theorem. If p 5 then ^2p
   

≡ 2 (mod p³), or, that is the same, ^2p−1

k
p−1
≡ 1 (mod p³).

0
Remind that ⁰

= 1, ⁿ

= 0 for k > n and for k < 0 by definition.

^{We denote by p a prime number. For any natural n denote by (n!)}p ^{the product of all integers from 1 to n not divisible by p. If a number p is given the symbols n}i^{, m}i ^{etc. denote the digits of numbers n, m etc. in base p.}
* * *

2. Arithmetical triangle and divisibility

1. 
   
   2
   a) Prove that the first 3^k rows of 3-arithmetical Pascal triangle contain ¹(6^k + 4^k) residues “1” and
   

2
¹ (6^k − 4^k) residues “2”.

2. 
   Find the number of zero elements in the first 5^k rows of 5-arithmetical Pascal triangle.
   
3. 
   Find the number of non-zero elements in the first p^k rows of p-arithmetical Pascal triangle.
   

2. 
   Prove that the number of 1’s in the first m rows of 2-arithmetical Pascal triangle equals
   

n_L−1
i=0
m_i · 2
n−1 _{m i}

k=i+1 ^k _{· 3 .}

If m = 2^α1 + 2^α2 + . . . + 2^αr , where α₁ > α₂ > . . . > α_r, then we can rewrite the last expression in the form

3^α1 + 2 · 3^α2 + 2² · 3^α3 + . . . + 2^r−1 · 3^αr .

3. 
   Consider n-th row of Pascal triangle modulo 2 as binary expansion of some integer P_n. Prove that
   

P_n = F_i1 · . . . · F_is ,


₁ F = 2 + 1_{s i}
where i , . . . , i are numbers of positions where 1’s occur in the binary expansion of n, and ²i is

i-th Fermat number.

4. 
   Prove that the number of non-zero elements in n-th row of p-arithmetical Pascal triangle equals
   

d

(n_i + 1).

i=0

5. 
   a) All the binomial coefficients
   

ⁿ , where 0 < k < n, are divisible by p if and only if n is a power of p.

b) All the binomial coefficients

^k


k
ⁿ , where 0 � k � n, are not divisible by p if and only if n + 1 is

divisible by p^d, in other words, all the digits of n, except the leftmost, in base p are equal to p − 1.

6. 
   Let 0 < k < n + 1. Prove that if ^{n . p} and ^{n . p}, then ^{n+1 . p}, except the case, when n + 1 is
   

divisible by p.

k−1 ^. k ^. k ^.

3. Generalization of Wilson’s and Lukas’ theorems

1. 
   
   p
   Prove that ord (n!) = ^{n − (nd + . . . + n1 + n0)} .
   

p − 1

2. 
   Prove the following generalizations of Wilson’s theorem. a) (−1)^[n/p](n!)_p ≡ n₀! (mod p);
   

2. 
   
   
   Prove that for p 3
   

(p^q!)_p ≡ −1 (mod p^q) ,

and for p = 2, q 3 (p^q!)_p ≡ 1 (mod p^q).

2. 
   
   _pµ
   
   0
   
   1
   
   d
   
   p
   ^n! ≡ ⁽−^1)µn ^!n ^! . . . n ^{! (mod} p⁾, where µ ^{= ord (}n^!)
   

f = ord_p(
_n

3. 
   
   k
   Generalized Lukas’ theorem. Let r = n − k, ). Then
   

(

1 n n₀!

)( _n1! )

( _nd! )

p k

≡ (−1)

k !r !

k !r !

. . .


k !r !

(mod p)

0 0 1 1 d d

4. 
   a) Prove that (1 + x)^pd ≡ 1 + x^pd (mod p) for all x = 0, 1, . . . , p − 1.
   

b) Prove Laukas’ theorem algebraically.

5. 
   a) Let m, n, k be nonnegative inte ger s, and (n, k) = 1. Prove that C^k
   

≡ 0 (mod n).

b) Prove that if n . p^k

, m . p, then

mn


m
ⁿ . p^k.

6. 
   
   

^{n n a d}

Let f_n,a =

( _{k k}=0

) . Prove that f_n,a ≡
i=0

f_ni,a (mod p).

3. Variations on Wolstenholme’s theorem

4.1. Prove that ^{1 + 1 +} . . . ^{+ 1} ≡ ^{0 (mod} p²⁾.

1 2 p − 1

2. 
   Let p = 4k + 3 be a prime number. Find ¹
   

0² + 1

1

^{+ 12 + 1}

1

^{+ . . . + (}p − ^{1)2 + 1}

(mod p).

2. 
   a) Let k be a nonnegative integer such that for any prime divisor p of the number m k is not
   

1 1 1


−
divisible by (p − 1). Prove that _1k + 2_k + . . . + (_{p 1)k} ≡ 0 (mod m) (summation over all fractions whose

denominators are coprime to m).

b) Let k be odd and (k + 1) ^. (p − 1). Prove that ^{1 + 1 +} . . . + ¹ ≡ 0 (mod p²).

^. ₁k ₂k

(p − 1)^k

2. 
   Prove that the equivalence (12) from Vinberg’s article holds in fact modulo p⁴.
   
3. 
   Prove that the following properties are equivalent 1) ^2p−1 ≡ 1 (mod p⁴);
   

1 1 1

₁ p−1 ₁

3

2
2) +

1 2

+ . . . +

p − 1

≡ 0 (mod p ); 3)

1 12 + 22

+ . . . +

(p − 1)²

≡ 0 (mod p ).

2. 
   a) Prove algebraically that for any prime p and arbitrary k and n ( ^pk − ^{k .}
   

². (In Vinberg’s

article this fact is proven combinatorially.

pm m

) _{. p}

<sub>pk

k .</sub>

b) Prove the statement (9) form Vinberg’s article: for any prime p 5 and arbitrary k and n ( _pm −

2. 
   Let p 5. Prove that a) ^p2 ≡ ^p (mod p⁵); b) ^ps+1 ≡ p^s (mod p^2s+3).
   

_m ) _{. p}³.

p 1 p

2. 
   
   _p2
   
   p
   Prove that ^p3 ≡ ^p2 (mod p⁸).
   

Amazing properties of binomial coefficients - 3

Additional problems to previous topics

7. 
   Prove that ^pn⁻¹ ≡ (−1)^Sk (mod p), where S
   

is the sum of digits of k in base p.

k

7. 
   Prove that if the binomial coefficient (1), then
   

k


k
ⁿ is odd i.e. k_i � n_i for all i = 0, 1, . . . , d in the notations of

<sub>n d

k</sub> ≡

i=1

(−1)^{ki−1ni+kini−1} (mod 4).

7. 
   Prove that if there are no two consecutive 1’s in the binary expansion of n then all the odd entries in n-th row ≡ 1 (mod 4), otherwise the number of entries ≡ 1 (mod 4) equals the number of entries ≡ −1 (mod 4).
   
8. 
   Prove that the number of 5’s in each row of 8-arithmetical Pascal triangle is a power of 2. Prove the same for 1’s, 3’s and 7’s.
   
9. 
   Prove that if we consider all the elements of the two sets
   

2ⁿ − 1 2ⁿ − 1 2ⁿ −

_{2n − 1}

1

, ,

1 3 5

, . . . ,

2ⁿ − 1

and {1, 3, 5, . . . , 2ⁿ − 1}

as a reminders modulo 2ⁿ, then these sets coincide.

7. 
   Prove that elements of a row of Pascal triangle are not coprime in the following sence. For any ε > 0
   

there exists N , such that for all integer n > N and k₁, k₂, . . . , k₁₀₀ < ε^√n the numbers

have a common divisor.

2n

,

n + k₁

2n n + k₂

, . . . ,

2n

n + k₁₀₀

7. 
   a) The non negative numbers m > 1, n, k are given. Prove that at least one of the numbers ⁿ
   

n+1 k
, . . . ,
n+k k
is not divisible by m.
<sub>n

k</sub> ,

n+1

k
b) Prove that for each k there exist infinite set of numbers n, such that all the numbers ,


k
^n+k−1 are divisible by m.

_k , . . . ,

9. 
   Prove that for n > 1 ²n+1 − ²n is divisible by 2²ⁿ⁺².
   

₂n ₂n−1

p−1 ^p−1

p−1 3

9. 
   
   ≡
   Prove that for p 5 (−1) ²
   

p−1 ⁴

2

(mod p ).