1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prime factors of binomials

  1. Dec 11, 2014 #1
    1. The problem statement, all variables and given/known data
    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.


    2. Relevant equations
    ##\binom{n}{k}=\frac{n!}{k!(n-k)!}##

    3. 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?
     
  2. jcsd
  3. Dec 11, 2014 #2

    ShayanJ

    User Avatar
    Gold Member

    [itex]p|b \Rightarrow b=pk \Rightarrow ab=pak \Rightarrow ab=pk' \Rightarrow p|ab [/itex].
     
  4. Dec 11, 2014 #3
    Can you elaborate on your solution? I can't seem to understand it very well.
     
  5. Dec 11, 2014 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    That is not going to work. The new divisor (n-k+1) might remove the factor of interest.
    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.
    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≤kn−1?​
    Please confirm.
     
  6. Dec 11, 2014 #5

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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?
     
  7. Dec 11, 2014 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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?
     
  8. Dec 11, 2014 #7
    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.
     
  9. Dec 11, 2014 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    In what sense 'needed'?
    I cannot guess what you mean by that.
     
  10. Dec 12, 2014 #9

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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."
     
  11. Dec 12, 2014 #10
    ##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.
     
  12. Dec 12, 2014 #11

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    It might be that if p / n and q / (n - 1) with p not = q then p and q suffice.
     
  13. Dec 12, 2014 #12
    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.
     
  14. Dec 12, 2014 #13

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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)
     
    Last edited: Dec 12, 2014
  15. Dec 12, 2014 #14

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  16. Dec 12, 2014 #15

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

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

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  18. Dec 12, 2014 #17

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Suppose prime p divides n, r times over. Characterise those k for which p is not a factor of ##\binom n k##.
     
  19. Dec 12, 2014 #18

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    @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.
     
    Last edited: Dec 12, 2014
  20. Dec 12, 2014 #19

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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...
     
  21. Dec 12, 2014 #20

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Hint 2: Lemma: k must be a multiple of p,.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Prime factors of binomials
Loading...