• Support PF! Buy your school textbooks, materials and every day products Here!

A division problem.

  • #1
391
0

Homework Statement



the idea is to prove wether a prime 'p' divides the quantities [tex] {p \choose k} [/tex]

for k=01,2,3,....,p-1

Homework Equations





The Attempt at a Solution



i have tried by inspection for small primes 3,5,7,11,13,17,...... but can not guess a simple solution , the idea is to see if for p prime , the Cyclotomic polynomial

[tex] x^{p}+..........+x+1 [/tex] for p prime.
 

Answers and Replies

  • #2
1,013
65
Trying more general circumstances, where p is any prime, we get the simpler question of whether the product (p-1)...(p-n) is divisible by n+1 for all n <= p - 1.
Ie., for n = 1, we question whether p-1 is divisible by 2, which is trivial. (p-1)(p-2) divisibility by 3 can be seen as well with a little more care.
There is a basic divisibility theorem about these products that you may have already proven earlier. If not, it is not difficult to prove by a little inspection.
 
  • #3
tiny-tim
Science Advisor
Homework Helper
25,832
249
Hi zetafunction! :smile:
the idea is to prove wether a prime 'p' divides the quantities [tex] {p \choose k} [/tex]

for k=01,2,3,....,p-1
If p is prime, how can it not divide pCk (except for k = 0) …

there's a p on the top, and nothing larger than p-1 on the bottom. :redface:
 
  • #4
1,013
65
Hi zetafunction! :smile:


If p is prime, how can it not divide pCk (except for k = 0) …

there's a p on the top, and nothing larger than p-1 on the bottom. :redface:
This question may only be trivial in retrospect. ;) The quotient [itex]\frac{(r-1)!}{(r-k)!k!}[/itex] trivially simplifies to [itex]\frac{(r-1)\cdots(r-k-1)}{k!}[/itex] which depends on k! successfully dividing the product on the top. This is not generally true when r is not prime. Ie., 8 does not divide 8C4.
It is then up to the OP to show why this is true for primes, but not necessarily composites.
 

Related Threads for: A division problem.

  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
4
Views
792
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
16
Views
1K
Replies
42
Views
3K
Replies
25
Views
3K
  • Last Post
Replies
1
Views
793
  • Last Post
Replies
6
Views
1K
Top