- #1

- 113

- 1

Is there any proof ?Please clarify.

thanks.

- Thread starter AlbertEinstein
- Start date

- #1

- 113

- 1

Is there any proof ?Please clarify.

thanks.

- #2

- 113

- 1

Th: Prove that p divides C(mp,r) where p is a prime and r is an integer not divisible by p.

- #3

HallsofIvy

Science Advisor

Homework Helper

- 41,833

- 956

Yes, _{n}C_{i} is always an integer (for n, i integers and 0<= i<= n). One proof is to note that _{n}C_{i} is the coefficient of x^{i}y^{n-i} in (x+ y)^{n}- which is necessarily an integer.

I would not say that that was "trivial" and certainly would expect a proof of the theorem you give.

I would not say that that was "trivial" and certainly would expect a proof of the theorem you give.

Last edited by a moderator:

- #4

- 113

- 1

C(mp,r) = (mp)! / (r!) (mp-r)!

= mp(mp-1)(mp-2)../ (r!) (mp-r)!

= p*an integer

Therefore p divides C(mp,r).

- #5

- 88

- 0

[tex]C(mp,r) = \frac{(mp)!}{(mp-r)!r!} = C(n,i)[/itex] where mp = n and i = r. So long as r greater than or equal to zero and less than or equal to mp you clearly get an integer by the basic construction. In fact this coefficient has to happen for one of the term's in the expansion of [itex](x+1)^{mp}[/itex]. So you have an integer and now you want to know whether it is divisible by p? Think about expanding it and writing each factor in the numerator and denominator in the form pa+r. Notice that there must be m factors in the numerator that are divisible by p. The number of factors in the denominator divisible by p are related like thisAlbertEinstein said:

Th: Prove that p divides C(mp,r) where p is a prime and r is an integer not divisible by p.

[tex]Div(r,p)+ Div(mp-r,p) < m \leftrightarrow Mod(r,p)\neq0[/tex]

Just simply count them if Div(r,p) = 4 and Mod(r,p) > 0 then subtracting r from mp removes the factors mp, (m-1)p, (m-2)p, (m-3)p, (m-4)p. So there were m factors divisible by p in mp!, in (mp-r)! there are m-5 the sum of m-5 and 4 is m-1 factors in the denominator to cancel the m factors in the numerator. C(mp,r) is divisible by p unless Mod(r,p)=0 ie r is divisble by p, so the answer to your question is yes the statement is true. However I do not think it is obvious from the first statement you made. We can get at this more obviously by the following

[tex]Div(mp,p)=Div(r+(mp-r),p) =Div(r,p)+ Div(mp-r,p)+\{0,1\}[/tex]

[tex]m-\{0,1\} =Div(r,p) + Div(mp-r,p)[/tex]

Residues are not completely obliterated by the Div operator, they survive as elements of the set {0,1}. We could give such sets the name case identifier sets or

Last edited:

- #6

- 113

- 1

Thanks.

- #7

- 113

- 1

Hey everyone, please help me.

- #8

- 88

- 0

Div(a,p) means integer division of a by p. Mod(a,p) is a related function it means the remainder after dividing a by p. The following statement is true generally and is called the division algorithmAlbertEinstein said:

Thanks.

a = aDiv(a,p)+Mod(a,p)

Mod(a,p) is alos sometimes written as a Mod p. I prefer the function notation. Your theroem is true and I gave a proof because I think one was required and it was interesting.

Does that help?

If it does'nt don't worry about it. I am wondering what I was drinking that night myself. When I wrote it, it was as clear as a bell to me. No it works write this

[tex]Div(r,p)+Div(mp-r,p) = \frac{r-Mod(r,p)}{p}+\frac{mp-r -Mod(mp-r,p)}{p}[/tex]

No if p divides r then Mod(r,p)=Mod(mp-r,p) = 0 so this last becomes

[tex]r/p + m - r/p = m[/tex]

If p does not divide r this becomes

[tex]r/p + m - r/p -(Mod(r,p)+Mod(mp-r,p))/p = m-1[/tex]

That should help.

Last edited:

- Last Post

- Replies
- 4

- Views
- 3K

- Last Post

- Replies
- 1

- Views
- 7K

- Last Post

- Replies
- 19

- Views
- 5K

- Replies
- 5

- Views
- 2K

- Last Post

- Replies
- 7

- Views
- 2K

- Replies
- 1

- Views
- 10K

- Last Post

- Replies
- 4

- Views
- 1K

- Last Post

- Replies
- 11

- Views
- 3K

- Last Post

- Replies
- 1

- Views
- 615

- Last Post

- Replies
- 1

- Views
- 1K