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 :

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

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

Show that $\displaystyle p=t^2$

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

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

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

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

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

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

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

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

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

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

Then $\displaystyle rt(rt+1) = t^2s(r+s)$, hence $\displaystyle 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 !)