H 57

Art of Problem Solving

AoPS Online

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

H 57

G H J

Reveal topic tags

Diophantine Equations

binomial coefficients

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3615 posts

Peter

#1 h May 25, 2007, 12:25 AM • 1 Y

Y by Adventure10

Show that the equation ${n \choose k}=m^{l}$ has no integral solution with $l \ge 2$ and $4 \le k \le n-4$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

602 posts

hxy09

#2 h Feb 21, 2009, 12:50 PM • 1 Y

Y by Adventure10

This problem has been given in a lecture of China IMO team training.It is really tough indeed.
We should prove http://www.mathlinks.ro/Forum/viewtopic.php?p=1414377#1414377 as a lemma.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15142 posts

#3 h Feb 14, 2012, 2:58 PM • 5 Y

Y by FlakeLCR, Tawan, vsamc, Adventure10, Mango247

As the source states, this has been proved by Erdös in 1951. See e.g. http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.pja/1195510942

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shekast-istadegi

81 posts

shekast-istadegi

#4 h Jul 6, 2012, 6:57 PM • 2 Y

Y by Adventure10, Mango247

we know that every natural number $n$ can be write the $n=P 1 P 2 . . . P k X^2$ for wich $Pi$ is

prime number .we get $T ( n ) = [P 1 , . . . , P k]$ . and $m a x {T ( n ) } = M n$ .

we know $c( n, k ) = n ( n - 1 ) . . . ( n - k + 1 ) / k . ( k + 1 ) . . . 2 . 1$ so we get $max[M n,Mn-1,...,M n-k+1]=Px$ so we get $m a x (k)$ such that $k$ is divisible by $Px$ is $S$ . so iff ther are no $l$ wich $Px$ divises $l$ We have a contradiction

Rsyzh.and iff ther exist $l$ such that $P x$ divises $l$ then $P x$ divises $S-l$ we know $S-l<=k$ and we obtain $( n, k )=c( n, k ).S-l/S-l$ and At the end we obtain $V p x (c ( n, k ) ) = 1$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1508 posts

#5 h Sep 17, 2020, 3:29 PM

Y by

Nice result. Here is my solution:
Assume WLOG $k \leq \frac{n}{2}$ as $\binom{n}{k}=\binom{n}{n-k}$ . If $k \geq \sqrt{n}$ , then by Sylvester Theorem $\binom{n}{k}$ is divisible by a prime factor larger than $k$ and hence larger than $\sqrt{n}$ . Since it is larger than $\sqrt{n}$ we have $v_p(\binom{n}{k})=1$ hence the binomial coefficient cannot be a perfect power. Now suppose the other case $4 \leq k \leq \sqrt{n}$ . I claim that there exist integers $a_1,a_2,...a_k, b_1,b_2,..b_k$ such that $\prod a_i=k!, a_ib_i=n-i+1$ and for each prime $2 \leq p \leq k$ , there is at most one term among the $b_i$ divisible by $p$ (hence the $b_i$ are co-prime). Consider a prime $p$ between $2$ and $k$ . Let $f_p$ be a number between $n$ and $n-k+1$ which has the maximal possible value of $v_p$ . For all $a_i$ such that $n-i+1 \neq f_p$ , set $v_p(a_i)=v_p(n-i+1)$ . For the $a_i$ corresponding to $f_p$ , adjust $v_p(a_i)$ such that it agrees with $\prod a_i=k!$ . Now we can check that this doesn't make any $v_p(a_i)$ negative by using induction. Repeat this process for each $2 \leq p \leq k$ and it is straightforward to check that the $a_i, b_i$ thus produced are indeed integers and they satisfy all the conditions in our claim. Hence, the $b_i$ are co-prime. Now if $\binom{n}{k}=m^l$ for some $l \geq 2$ then all the $b_i$ are perfect $l^{th}$ powers. We note that either the $a_i$ are $1,2,3,...k$ in some order or two of the $a_i$ are equal. If two of the $a_i$ are equal we get $a(b^l-c^l)=d$ where $ab^l, ac^l$ are between $n$ and $n-\sqrt{n}$ and $a,d$ are between $1$ and $\sqrt{n}$ . We can size-bound and show that $d \geq alc^{l-1}$ and note an easy size bounding contradiction as the size of $ac^l$ is on the order of $n$ while the the size of $a,d$ are lower than $\sqrt{n}$ . Consider the other case that the $a_i$ are $1,2,3,...k$ in some order. Take $i,j,k$ such that $a_i=\lfloor \frac{k}{4} \rfloor, a_j=2a_i$ and $a_k=2a_j$ . So the corresponding $a_ib_i$ will be $\lfloor \frac{k}{4} \rfloor a^l, \lfloor \frac{k}{4} \rfloor*2b^l, \lfloor \frac{k}{4} \rfloor*4c^l$ for some $a,b,c$ and $l \geq 2$ , and these numbers are between $n$ and $n-k$ and hence between $n$ and $n-\sqrt{n}$ . Now we see that $d=4*\lfloor \frac{k}{4} \rfloor^2*((ac)^l-(b^2)^l)$ is less than $\frac{nk}{2}$ . So an easy size argument shows that $l \geq 3$ is not possible as $m^l-n^l$ cannot be lower than $m^l-(m-1)^l$ whose size is on the order of $lm^{l-1}$ . So the only possible case remaining is that this number is a square. So consider $l=2$ . Consider $a_r,a_s$ such that $a_r=1, a_s=4$ (as $k \geq 4$ ). Then, $a_rb_r$ and $a_sb_s$ are two distinct perfect squares (as the $b_i$ are perfect $l^{th}$ powers) between $n$ and $n-\sqrt{n}$ . However, this is a clear contradiction because for two distinct positive integers $a,b$ , the numbers $a^2,b^2$ are at least $2a-1$ apart. So, for $4 \leq k \leq n-4$ , we have shown that $\binom{n}{k}$ cannot be a perfect power. Proved

Edit: After reading Erdos's proof of this, turns out that this solution is quite similar to Erdos's proof...

This post has been edited 4 times. Last edited by Mathotsav, Sep 17, 2020, 4:31 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a