[SOLVED] Dividing problem

**Moo** · April 9th 2008, 01:08 PM

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...

Thanks in advance !

**Opalg** · April 10th 2008, 02:03 AM

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.

**Moo** · April 10th 2008, 05:48 AM

Hello,

Thanks for the answer ! This is exactly what i wanted

(and even for the following question !)

Thread: [SOLVED] Dividing problem

LinkBack

Thread Tools

Display

[SOLVED] Dividing problem

Similar Math Help Forum Discussions

[SOLVED] Help dividing exponent by exponent

Dividing

[SOLVED] dividing by 0!

[SOLVED] [SOLVED] Dividing Polymonials by Polynomials

Problem of Dividing By Zero Solved

Search Tags