an open problem

LaTeX4Web 1.4 OUTPUT In this section and other sections of this page we will analyze an open problem in number theory regarding binomial coefficients. We examine the following condition:
Condition 1. For a positive integer n, there exist prime p and r such that if 1 £ k £ n-1 then the binomial coefficient C(n,k) is divisible by at least one of p or r.
Then a very natural question follows: does Condition 1 hold for all integers n?
LaTeX4Web 1.4 OUTPUT We can visualize Condition 1 using Pascal¢s Triangle. We fix some n and then we look at the nth row of Pascal¢s Triangle. We want to see if it is true that we can find two primes p and r such that if we paint the multiples of p in the nth row with one color and the multiples of r in the nth row with another color, then all the numbers in the nth row are painted either with one of the colors, the other, or both (ommiting the ones in the edges). The following picture illustrates this explanation with n=14, p=2 (blue) and r=7 (pink).
LaTeX4Web 1.4 OUTPUT In this page we will talk about some cases in which we can prove that n satisfies Condition 1. In the section "Fixing one prime" we provide code and information for when we fix p or r to be a certain prime. In the section "All possible pairs" we evalute given n how many pairs of primes make n satisfy Condition 1. In the section "Multinomials" we study the generalization of Condition 1 for the multinomials. Finally, in the section "OEIS sequences" we give code and explanations for proofs in which certain n satisfy Condition 1, in which we find two sequences that the On-line Encyclopedia of Integer Sequences has published.
LaTeX4Web 1.4 OUTPUT First of all, Lucas¢ Theorem is a very useful theorem regarding the divisibility of binomial coefficients. It states the following:
Theorem. (Lucas) Let m and n be positive integers and let m = mkpk + mk-1pk-1 + ... + m1p + m0 and n=nkpk + nk-1pk-1 + ... + n1p + n0 be the base p expansions of m and n respectively. Then, C(m,n) º Õi=0k C(mi,ni) mod p.
It is important to notice that by convention C(m,n) = 0 if m < n. Now we can prove the following statement:
Proposition. A positive integer n satisfies the 1-variation of Condition 1 with p if n=pa for some a>0.
Proof: The base p representation of n is equal to 10¼0 with a zeroes. Any k such that 1 £ k £ n-1 has at most a -1 zeroes in base p. Therefore, at least one of the digits of the base p representation of k is bigger than the corresponding digit of n in base p. It then follows from Lucas¢ Theorem that C(n,k) is divisible by p. Otherwise if n is not a prime power and hence some digit of n in base p is not zero we can find at least one k such that C(n,k) is not divisible by p.
LaTeX4Web 1.4 OUTPUT From the previous proposition we can derive the following corollary:
Corollary. If n=pa + 1, then p and any prime factor of n satisfy Condition 1.
Proof: The proof relies on the fact that C(n,k)+(n,k+1) = C(n+1,k+1) for all positive integers n and k. If n is a power of a prime p, then it follows from the last proposition that C(n+1,k) is divisible by p if 2 £ k £ n-1. When k=1 or k=n, we have that C(n+1,k) = n+1, so any prime factor of n+1 divides it.
LaTeX4Web 1.4 OUTPUT We can also prove the following proposition:
Proposition. If a positive integer n is equal to the product of two prime powers p1a and p2b , then n satisfies Condition 1 with p1 and p2.
Proof: Observe that lcm(p1a ,p2b ) = n. The base p1 representation of n ends in a zeroes and the base p2 representation of n ends in b zeroes. Because any positive k smaller than n cannot be divisible by both p1a and p2b , we can apply Lucas¢ Theorem modulo the prime p1 if p1a does not divide k or modulo the prime p2 if p2b does not divide k.