Given positive integer $k$, prove that there exists a positive integer $N$ depending only on $k$ such that for any integer $n\geq N$, $\binom{n}{k}$ has at least $k$ different prime divisors.
Problem
Source:
Tags: number theory, p-adic
14.09.2010 02:52
Using Kobayashi's Theorem Given an unbounded sequence of positive integers $(a_n)_{n\geq 1}$ for which the set of primes dividing some term of the sequence is finite, then for any translate $(a_n + t)_{n\geq 1}$ with a not null integer $t$, the set of primes dividing some term of this translated sequence is infinite. one can easily prove that given any finite set of primes $P$ and a positive integer $m$, the number of pairs $(n,n+m)$, with $n$ varying over the positive integers, such that both $n$ and $n+m$ have only prime factors from $P$, is finite. Take $P$ to be the set of all the primes less or equal to $k$. Then for $n$ large enough, and for $0 \leq i < j \leq k-1$, at least one number of the pair $(n-i,n-j)$ must have a prime factor outside $P$. Set this number aside, and repeat the argument for another pair, until only one number is left. In this way, we associate to $k-1$ of the $k$ numbers $n-i$, where $0 \leq i \leq k-1$, some prime $p_i \not \in P$. Therefore these primes are distinct, since the difference between the least and the largest of the numbers considered is $n - (n-(k-1)) = k-1 < k$, and also they do not disappear after division by $k!$, for the same reason. The only number $n-j$ for which no such prime may have been associated will be large enough (for $n>k!$) not to cancel at division by $k!$, and so it will itself have some prime factor $p_j$ (maybe from $P$), but distinct from all the other $p_i$'s. We have therefore proved the existence of at least $k$ distinct prime factors for $\binom {n} {k}$, with the proviso $n$ is large enough so as to simultaneously satisfy the requirements from the prologue of the argument. A related topic is Grimm's Conjecture; see [R.K. Guy - Unsolved Problems in Number Theory], B32. In fact we have proved here that for fixed $k$, each of $k$ consecutive positive integers have a distinct prime factor, provided the sequence starts far enough.
26.01.2013 12:08
mavropnevma wrote: one can easily prove that given any finite set of primes $P$ and a positive integer $m$, the number of pairs $(n,n+m)$, with $n$ varying over the positive integers, such that both $n$ and $n+m$ have only prime factors from $P$, is finite. Can you explain more how to prove this please?
14.03.2014 12:03
k=1 is trival ,for k>1,n>k if C(n,k)=n(n-1)……(n-k+1)/k! have at most k-1's prime divisor,let them be p[1],p[2],……,p[k-1] we assume n-i+1=ab,here b is the maximum disivior of n-i+1 which divide k! then any prime divisor of a is one of p assume p[1]^u[1],p[2]^u[2],……p[k-1]^u[k-1] all exactly divide a,it's easy to prove,there exits such a prime power not less than a^(1/(k-1))≥((n-k)/k!)^(1/(k-1)) because m[1],m[2],……,m[k] is power of at most k-1 distrinct prime,there exist m and m[j] to be the power of same prime,wlog j≥i obviously (m,m[j])=min{m,m[j]}≥((n-k)/k!)^(1/(k-1)) hence k>k-i≥j-i≥(n-j+1,j-i)=(n-j+1,n-i+1)≥(m[j],m) ≥((n-k)/k!)^(1/(k-1)) and we get (n-k)/k!<k^(k-1),n-k<k!*k^(k-1),n<k+k!*k^(k-1) we choose N=k+k!*k^(k-1) and we are done
01.03.2018 00:17
I have a solution without Kobayashi's Theorem, and I would be glad if someone checked if it is correct. I will investigate the number ${n + k \choose k}$ instead of ${n \choose k}$ for simplicity. The point is to prove that the equation $(n+1)(n+2)\ldots (n+k) = k!p_1^{a_1}p_2^{a_2}\ldots p_{k-1}^{a_{k-1}}$ has only finitely many solution, where $p_i$ are distinct primes and $ a_{i} \geq 0 $ are integers, and $n$ is a parameter. The problem statement will follow. The idea is to get an upper bound for $n$. After this we are done. Assume we have a solution to the equation mentioned before for the rest of the solution. Lemma If $v_{q}(n + m) = a$ for some prime $q$ and integer $1 \leq m \leq k$, and $v_{q}(n+i) \leq a$ for all $i \neq m$, then $v_{q}((n+1)(n+2)\ldots (n+k)) \leq a + \frac{k}{q - 1}$. Proof It is quite easy to see that the amount of integers between $n+1$ and $n+k$ with divisor $q^b$ is at most $\lceil \frac{k}{q^b} \rceil$. This is good enough of a boundary: the amount of integers between $n+1$ and $n+k$ with divisor $q^b$ excluding $n + m$ is at most $\lfloor \frac{k}{q^b} \rfloor$ (which is at most $\frac{k}{q^b}$). Thus, the greatest power of $q$ dividing $(n+1)(n+2)\ldots (n+k)$ would be at most $a + \frac{k}{q} + \frac{k}{q^2} + \ldots \leq a + \frac{k}{q-1}$. An immediate consequence of the lemma is that for all $p_i$, there must be an integer $b_i$, such that $v_{p_i}(n + b_i) \geq a_i - \frac{k}{q-1}$, where $a_i$ was the exponent of $p_i$ in our equation (trivial proof by contradiction works here). Now, for each $p_i$ ($1 \leq i \leq k-1$), take the $1 \leq b_i \leq k$, such that $v_{p_i}(n + b_i)$ is maximal (if there are many options, pick any). Now, let $t$ be such a number that $t \neq b_i$ for all $i$. I will prove an explict upper bound for $n + t$ (a very poor one, but a bound anyway), which is what we wanted. Note that for each prime $q > k$, $q \neq p_i$, $q$ can't divide $n + t$, as $q$ would then divide the left hand side of the equation $(n+1)\ldots (n+k) = k!p_1^{a_1} \ldots p_{k-1}^{a_{k-1}}$, but not the right hand side. We also in the same manner see that for all $p_i$, $i = 1, 2, \ldots k - 1$ that, using the fact $v_{p_i}(n + b_i) \geq a_i - \frac{k}{p_i - 1}$ for some $b_i \neq t$, $v_{p_i}(n+t) \leq v_{p_i}((n+1)(n+2)\ldots (n+k)) - (a_i - \frac{k}{p_i - 1}) = v_{p_i}(k!) + a_i - (a_i - \frac{k}{p_i - 1}) \leq k + \frac{k}{p_i - 1} \leq 2k$. If we have $p_i \leq k$, we are happy with our result. If we have $p_i > k$, we simply have $v_{p_i}(n+t) = 0$, for we had $p_i | n + b_i$. If we had $p_i | n + t$, then $p_i | t - b_i$, a number whose absolute value is less than $k$ but not $0$, a contradiction. And also, for primes $q$, $q \leq k$, $q \neq p_i$, we have $v_q(n + t) \leq v_q(k!) \leq k$. Thus, we have $n + t \leq \prod q^k \cdot \prod {p_{i}}^{2k}$, where the first product is over the primes $q$ with $q \leq k$, $q \neq p_i$, and the latter one is over the primes $p_i$, with $p_i \leq k$. Thus, $n < n + t \leq \prod k^k \cdot \prod k^{2k} \leq k^{k^2} \cdot k^{2k^2} = k^{3k^2}$. We are done.
01.03.2018 10:42
Loppukilpailija wrote: Lemma If $v_{q}(n + m) = a$ for some prime $q$ and integer $1 \leq m \leq k$, and $v_{q}(n+i) \leq a$ for all $i \neq m$, then $v_{q}((n+1)(n+2)\ldots (n+k)) \leq a + \frac{k}{q - 1}$. Proof It is quite easy to see that the amount of integers between $n+1$ and $n+k$ with divisor $q^b$ is at most $\lceil \frac{k}{q^b} \rceil$. This is good enough of a boundary: the amount of integers between $n+1$ and $n+k$ with divisor $q^b$ excluding $n + m$ is at most $\lfloor \frac{k}{q^b} \rfloor$ (which is at most $\frac{k}{q^b}$). Thus, the greatest power of $q$ dividing $(n+1)(n+2)\ldots (n+k)$ would be at most $a + \frac{k}{q} + \frac{k}{q^2} + \ldots \leq a + \frac{k}{q-1}$. Can you explain the proof of the lemma better please? I don't understand where you used the fact that $n+m$ has the biggest $v_p$
01.03.2018 17:02
I'll admit the proof isn't very detailed in general. The reason why the number of integers in $[n + 1, n + k]$ with divisor $q^b$ is at most $\lceil \frac{k}{q^b} \rceil$ should be quite obvious: let the number $n + i$ be the smallest number having this divisor. Then, the numbers $n + m\cdot q^b + i$ are exactly the ones with the same factor, with $m = 0, 1, 2, \ldots$. Now, let $m_0$ be the largest $m$ so that this belongs to the interval $[n+1, n+k]$. We have $m \cdot q^b + i \leq k$, so $m \cdot q^b < k$. Thus, $m < \frac{k}{q^b} \leq \lceil \frac{k}{q^b} \rceil$. Now, the point where I used the fact that $n + m$ has the biggest $v_q$ is the sentence "the amount of integers between $n + 1$ and $n + k$ with divisor $q^b$ excluding $n + m$ is at most $\lfloor \frac{k}{q^b} \rfloor$". As $n + m$ has the biggest $v_q$, we must have $b \leq a$, (if $b > a$, the amount of integers with divisor $q^b$ would be $0$, when of course the statement of the sentence holds). Now, as $b \leq a$, we can exclude the number $n + m$, to decrease the amount of integers with divisor $q^b$ from $\lceil \frac{k}{q^b} \rceil$ (including the number $n + m$) to $\lfloor \frac{k}{q^b} \rfloor$ (excluding $n + m$). I hope this clears up. If you see anything else that's unclear, I'm glad to answer questions.
23.03.2019 01:41
I found a relatively easy solution, which should be wrong....but, yeah, check it, please.7 Assume the contrary. We begin with the following \textbf{Lemma.} Let $p$ be a prime number. Then $$p^{v_p({n\choose k})}\leq n.$$ \textit{Proof.} Let $[\log_{p} n]=s.$ Since $v_p(n!)=[n/p]+[n/p^2]+\cdots+[n/p^s],$ analogously we obtain $$v_p({n\choose k})=\sum_{i=1}^s [n/p^i]-[k/p^i]-[(n-k)/p^i]=\sum_{i=1}^s \{k/p^i\}+\{(n-k)/p^i\}-\{n/p^i\}\leq \sum_{i=1}^s 1=s.$$Thus, the lemma is proved. Back to the problem, if we write $\frac{n(n-1)\cdots(n-k+1)}{k!}={n\choose k}={p_1}^{\alpha_1}{p_2}^{\alpha_2}\ldots {p_j}^{\alpha_j}$ from the lemma we get ${n\choose k}\leq n^j\leq n^{k-1},$ which is a contradiction for all suficiently large $n.$ Hence, the conclusion follows.
16.07.2022 05:08
Thanks CANBANKAN for pointing out my mistake. Now I have seen at least four possible bounds.
20.07.2022 10:44
There is nothing wrong with the solution @2above because it proves the bound $N=k!$. I think the stronger bound is $N=lcm(1,\cdots,k)$