Prime factors of binomials

[Gilictic]

Homework Statement

Is it true that for each $n\geq 2$ there are two primes $p, q \neq 1$ that divide every $\binom{n}{k}$ for $1\leq k\leq n-1$?


Examples:

For $n=6: \binom{6}{1}=6; \binom{6}{2}=15; \binom{6}{3}=20; \binom{6}{4}=15; \binom{6}{5}=6.$ So we can have $p=2$ and $q=3$.


For $n=3: \binom{3}{1}=3; \binom{3}{2}=3.$ So we can have $p=3$ and $q=17$ (or any other prime). We just have to show that each $\binom{n}{k}$ is divisible by at most two primes.

Homework Equations

$\binom{n}{k}=\frac{n!}{k!(n-k)!}$

The Attempt at a Solution

Proof by induction:
Base case: True for $2, 3$
Induction on $n$: Assume true for $n$. Prove for $n+1$:
$$\binom{n+1}{k}=\frac{(n+1)!}{k!(n-k+1)!}=\frac{n+1}{n-k+1}*\frac{n!}{k!(n-k)!}$$

Now what? Is it possible to say that since $\frac{n!}{k!(n-k)!}$ is divisible by primes (by assumption) that somehow $\frac{n+1}{n-k+1}*\frac{n!}{k!(n-k)!}$ is as well?

 

[ShayanJ]

$p|b \Rightarrow b=pk \Rightarrow ab=pak \Rightarrow ab=pk' \Rightarrow p|ab$.

 

[Gilictic]

Can you elaborate on your solution? I can't seem to understand it very well.

 

[haruspex]

$p|b \Rightarrow b=pk \Rightarrow ab=pak \Rightarrow ab=pk' \Rightarrow p|ab$.

That is not going to work. The new divisor (n-k+1) might remove the factor of interest.

Proof by induction:

It's not clear to me how induction is going to succeed. You are not trying to show the same two primes work for all n.

We just have to show that each (nk)\binom{n}{k} is divisible by at most two primes.

That's not what was originally stated. It reads more like 'at least two distinct primes'. But that is not true (as your n=3 example shows). So I guess the problem statement should have been:

Is it true that for each n≥2 there are at most two distinct primes p,q≠1 that divide every $\binom{n}{k}$ for 1≤k≤n−1?​

Please confirm.

 

[mfb]

The problem statement is a bit misleading. For every $n \choose k$, just either p or q has to be a factor?

A proof by induction... I'm not so convinced (unless you choose a very clever way of induction).
What happens if n is a prime or a prime power?

 

[haruspex]

The problem statement is a bit misleading. For every $n \choose k$, just either p or q has to be a factor?

Doesn't sound to me that it's supposed to be the same p and q for each n. Did you read my post #4?

 

[Gilictic]

Sorry. I don't know why I put the "at most" in there. I want to prove that two primes $p, q$ exist that can divide $\binom{n}{k}$. Sometimes only 1 prime is needed (i.e. when $n$ is prime). However, I want to prove that with only two primes, I can divide $\binom{n}{k}$.

Also, each $n$ will have different primes $p, q$.

Please ask if I am not clear anywhere else.

 

[haruspex]

Sometimes only 1 prime is needed

In what sense 'needed'?

I want to prove that with only two primes, I can divide $\binom{n}{k}$

I cannot guess what you mean by that.

 

[mfb]

Doesn't sound to me that it's supposed to be the same p and q for each n. Did you read my post #4?

After I posted, yes (was doing some checks before, didn't see your post earlier).

I think post 7 confirms my interpretation: "For a given n, there is a set {p,q} of two primes such that every $n \choose k$ (apart from k=0 and k=n) has p or q as a factor."

 

[Joffan]

$n$ prime is a simple case, as is $n-1$ prime.

You might be able to to run induction on multiples of each prime, perhaps; I haven't tried it though.

 

[PeroK]

It might be that if p / n and q / (n - 1) with p not = q then p and q suffice.

 

[Joffan]

It might be that if p / n and q / (n - 1) with p not = q then p and q suffice.

Your bonus this week, courtesy of number theory, is that you get p≠q thrown in free! :)

If I look at n=15, it depends how you choose {p,q}: {5,7} and {3,7} work, {5,2} and {3,2} don't.

 

[mfb]

At n=15, all numbers are divisible by 5 and 3. I think that is not a coincidence (tested up to 39, Excel gets troubles with large numbers afterwards)

 

[PeroK]

Your bonus this week, courtesy of number theory, is that you get p≠q thrown in free! :)

If I look at n=15, it depends how you choose {p,q}: {5,7} and {3,7} work, {5,2} and {3,2} don't.

That's because pq < n/2. Proof is slippery but if n fails then pq < n/2 where p and q are largest prime divisors of n and n-1.

Also, n can't have a repeated prime factor.

 

[mfb]

5 and 7 are the largest prime divisors of 15 and 14, but 5*7 is not smaller than 15/2.
Also, which proof?

 

[PeroK]

5 and 7 are the largest prime divisors of 15 and 14, but 5*7 is not smaller than 15/2.
Also, which proof?

I thought I was closing in on a proof but I'm not so sure now. If you could find n and n-1 where both are the product of distinct primes with pq < n/2 then I think the result might fail for that n.

The key point is cancelling factors. I think every binomial is divisible by p or q until k = pq. Where p and q are any prime factors of n and n-1. In particular if the result fails for n, then pq must be < n/2 when they are the largest prime factors.

There might be a counterexample but hard to find.

 

[haruspex]

Suppose prime p divides n, r times over. Characterise those k for which p is not a factor of $\binom n k$.

 

[mfb]

@PeroK: n and n-1 are always the product of distinct primes. Any shared factor would also be a factor of their difference, which is 1.

63 has 7 as largest prime factor, 64 has 2, and 7*2=14 < 64/2.
64 has 2 as largest prime factor, 65 has 13, and 2*13=26 < 65/2.

Those are the smallest examples. 80 and 81 is the next pair and does not have 2 as one of the primes. Those three are the only examples below 100 and I don't want to check more now. Hypothesis: there is an infinite number of examples.

 

[PeroK]

@PeroK: n and n-1 are always the product of distinct primes. Any shared factor would also be a factor of their difference, which is 1.

63 has 7 as largest prime factor, 64 has 2, and 7*2=14 < 64/2.
64 has 2 as largest prime factor, 65 has 13, and 2*13=26 < 65/2.

Those are the smallest examples. 80 and 81 is the next pair and does not have 2 as one of the primes.

Both n and n-1 must be products of distinct primes I.e no repeated factors. Repeated factors won't completely cancel.

You need something like:

n = 3.7.11...

n -1 = 2.5.13...

 

[haruspex]

Suppose prime p divides n, r times over. Characterise those k for which p is not a factor of $\binom n k$.

Hint 2: Lemma: k must be a multiple of p,.

 

[Joffan]

Up to 110, it's possible to find two prime factors of all non-prime-power n for which one or the other divide every C(n,k) in range. 110 doesn't work that way, although it is possible to find two other primes that work (109 being the easy choice). This might help set the direction of any attempted proof.

2 does not divide C(110,10) and C(110,44) (among others)
5 does not divide C(110,10) and C(110,55) (among others)
11 does not divide C(110,44) and C(110,55) (among others)

 

[PeroK]

Here's my idea for a counterexample:

Suppose you could find n such that:

$n = p_1p_2...p_r$
$n-1 = q_1q_2...q_s$

Where the product of any two of these primes is < n/2. Then, for any two of these primes, we have a k, such that neither prime divides $binom{n}{k}$

Any such n will be quite large: the largest primes $p_r$ and $q_s$ must be at least 20, so n/2 must be at least 400.

In any case, if you are going to prove the proposition, then I think you will have to show that no such n can exist.

My guess is that the proposition fails, although finding a countereaxmple will be hard.

PS I had a scout round online. There are a lot of consecutive squarefree integers, but I couldn't find anything relevant about the size of their prime factors.

 

[mfb]

I found a counterexample:
6761*6823*6827 = 314,931,578,581
2*37*827*5146109 = 314,931,578,582
6827*5146109 = 35,132,486,143

As you can guess from the first number, I just tested the product of three primes in that range to have a square-free number without a very large prime factor next to it. As I was successful after ~20 attempts, this is almost certainly not the smallest pair.

 

[haruspex]

Let $n = \Pi p_i^{r_i}$ and $f = \max \{p_i^{r_i}\}$. Similarly, let g be the largest prime power factor of $\{n-f, n-f+1, .. , n-1, n/f\}$. I believe n is a counterexample if and only if n > fg. Will attempt to test this.

 

[PeroK]

Let $n = \Pi p_i^{r_i}$ and $f = \max \{p_i^{r_i}\}$. Similarly, let g be the largest prime power factor of $\{n-f, n-f+1, .. , n-1, n/f\}$. I believe n is a counterexample if and only if n > fg. Will attempt to test this.

Yes, I forgot I was trying to find a solution using prime factors of n and n-1 only. So, my idea of a counterexample was only for that!

I can't see that there could be a counterexample with your constraint. There's bound to be a large prime factor somewhere in that list.

 

[haruspex]

There's bound to be a large prime factor somewhere in that list.

It only needs to be a power of a prime, but it's still not obvious there'll be one. E.g. for n = 2520, f = 9. Doesn't leave that many candidates for the contributor of g.

 

[haruspex]

Let $n = \Pi p_i^{r_i}$ and $f = \max \{p_i^{r_i}\}$. Similarly, let g be the largest prime power factor of $\{n-f, n-f+1, .. , n-1, n/f\}$. I believe n is a counterexample if and only if n > fg. Will attempt to test this.

I tried all n up to a million. The furthest I had to search through the sequence n-1, n-2, ... for the second prime power was 19 (n = 520260, f = 29, g = 520241).

 

[mfb]

I lost the connection of this f,g and n, n-1 thing to the original problem.

 

[PeroK]

The original problem was to find common prime factors of all the binomials. So, for n, we had to find two primes p & q, at least one of which divides each binomial $\binom{n}{k}$.

I tried to prove that picking the biggest prime factor of n and n-1 respectively would do. But, this didn't work, and you found a counterexample.

Certainly one prime must be a factor of n. But, you don't have to pick the second prime from n-1. If you choose f as the biggest prime factor of n (as defined above, including powers of the factor). Let's say $f = p^r$, then p will divide all the binomials up to but not including $k = p^r$.

So, you must choose your second prime factor from $n-1, n-2 ... n-p^r$

To find a counterexample, you need not two consecutive numbers with "small" prime factors but a larger set of consecutive numbers that all have exclusively small enough prime factors.

 

[PeroK]

Actually, this is not quite right. If the primes are picked from different integers, then their factorisation sequences are not in sync. E.g. if p = 5 is a factor of n and p = 7 is a factor of n-1, then they both cancel when k = 15 (not 35). And p = 25 and q = 49 would cancel at k = 50.

Very tricky!

 

[haruspex]

Actually, this is not quite right. If the primes are picked from different integers, then their factorisation sequences are not in sync. E.g. if p = 5 is a factor of n and p = 7 is a factor of n-1, then they both cancel when k = 15 (not 35). And p = 25 and q = 49 would cancel at k = 50.

Very tricky!

Yes, I worried I was missing something there, but didn't see it. So there's a penalty as you step down down the sequence from n. If the second factor, g, is from n-1 then the terms it won't divide occur in pairs, k=g, k=g+1; if from n-2 then they occur in triples, etc. Consequently, it might not be best to take the largest prime power factor from n that you can. Ouch.

 

[Joffan]

Actually, this is not quite right. If the primes are picked from different integers, then their factorisation sequences are not in sync. E.g. if p = 5 is a factor of n and p = 7 is a factor of n-1, then they both cancel when k = 15 (not 35). And p = 25 and q = 49 would cancel at k = 50.

Very tricky!

Yes indeed. For example, taking n=210, p=7 and q=103 (from 206), C(210,105) is not divisible by either p or q.

If you can reach a "pure" prime or prime power, though, you're safe , as is the case for 520260.

 

[PeroK]

If there is a countereaxmple using the "simple" method of looking for the largest prime factors, then that counterexample will be valid. This is because each pair of factors will cancel together before their product. So, looking at fg is a worst case. Also, f and g both have to cancel before (n+1)/2, as the binomials repeat for k after that.

A better algorithm would check each pair more precisely if their product is greater than (n+1)/2, as they may cancel before that. Joffan is correct, though, that you have to avoid primes. If you started with a list of primes, you could look for relatively large gaps.

There is a relationship between the required gaps in the primes and the size of prime factors. E.g.

If all prime factors are less than 10, then the maximum n is 8.9.5.7 = 2520. So, you need a gap of at least 10 numbers without primes.

If all prime factors are less than 20, then the maximum n is about 250 million. So, you need a gap of about 20. But, with a lot more choice of n. There are some gaps of about 250 at this range.

It seems plausible, therefore, that there is a counterexample. But hard to find.

 

[Joffan]

A better algorithm would check each pair more precisely if their product is greater than (n+1)/2, as they may cancel before that. Joffan is correct, though, that you have to avoid primes. If you started with a list of primes, you could look for relatively large gaps.

I did more-or-less this, out to 20 million, on Sunday. For cases where gap from the last prime-power is greater than the largest prime-power factor of a number (2378 cases), I looked at the preceding numbers and checked directly whether their largest prime-power factor gave the divisibility coverage required. Usually one of them did; in a few cases {31416, 46800, 195624, 2999568, 5504490, 7458780, 9968112, 12387600} none did, but then taking the second-largest prime-power factor of the original number always turned up a coverage pair.

The cases where I needed to go to the second factor of the initial number seemed to be getting less frequent as n increased.

Another interesting were a large number of cases where two relatively small factors did the job. For the most extreme example, for 18027009, 29 and 2 (for 512, from 18027008) covered divisibility of all coefficients. I'd love if someone else checked that...

Function NFacMDiv(ByVal NFac As Long, MDiv As Long) As Long
' return power of prime MDiv in nFac!
NFacMDiv = 0
Do While NFac > 0
    NFac = Int(NFac / MDiv)
    NFacMDiv = NFacMDiv + NFac
Loop

End Function
Function nCrMDiv(ByVal FromN As Long, ChooseK As Long, MDiv As Long) As Long
' return power of prime MDiv in C(FromN, ChooseK)
If ChooseK <= FromN Then
    nCrMDiv = NFacMDiv(FromN, MDiv) - NFacMDiv(ChooseK, MDiv) - NFacMDiv(FromN - ChooseK, MDiv)
Else
    nCrMDiv = -1
End If
End Function