1. ## [SOLVED] Dividing problem

Hi !

I've got a little problem, seems simple... Here it is :

Text :
We're going to study all couples (n,k) such as :

${n \choose k}={n+1 \choose k-1}$

Question :
Let $p=n-k+1$ and $t=gcd(p,k)$. Also $s=\frac{k}{t}$

Show that $p=t^2$

So far... :
By replacing the combinations with their formulas with !, i've found that :

$p(p+1)=(p+k)k$

$p^2+p=pk+k^2$

So it's easy to show that $t^2|p$

And now... ?
I can't find how to show that $p|t^2$ or $p \leq t^2$ :'(

I thought Bézout's identity could help, but no...

2. Originally Posted by Moo
I've found that :

$p(p+1)=(p+k)k$
$p^2+p=pk+k^2$

So it's easy to show that $t^2|p$

And now... ?
I can't find how to show that $p|t^2$ or $p \leq t^2$ :'(
So if $t = \gcd(p,k)$, let p = rt and k = st, where r and s are co-prime.

Then $rt(rt+1) = t^2s(r+s)$, hence $r(rt+1) = s(r+s)t$.

Since t has to divide the left-hand side of the last equation, and t is clearly co-prime with rt+1, it follows that t divides r (so that t^2 divides p: you already knew that).

Similarly, since r has to divide the right-hand side of that equation, and r is co-prime with both s and r+s, it follows that r divides t.

Put those two facts together, and you have r=t as required.

3. Hello,

Thanks for the answer ! This is exactly what i wanted (and even for the following question !)