googlymunja32
Aug17-08, 11:25 AM
So you are asking, "Is it true that np- n is divisible by p for p any prime?"
Yes, it is and for exactly the reason you state: if p is prime then \left(\begin{array}{c}p \\ i\end{array}\right) for p prime and 0< i< p is divisible by p. That itself can be proven directly from the definition:
\left(\begin{array}{c}p \\ i\end{array}\right)= \frac{p!}{i!(p-i)!}
as long as i is neither 0 nor p, 0<p-i< p and so neither i! nor (p- i)! have a factor of p. Since p! does, the binomial coefficient is divisible by p. (We need p to be prime so that other factors in i! and (p- i)! do not "combine" to cancel p.)
Now, to show that np- n is divisible by p, do exactly what mathman suggested.
First, when n= 1, 1p- 1= 0 which is divisible by p. Now assume the statement is true for some k: kp- k= mp for some integer m. Then, by the binomial theorem,
[tex](k+1)^p= \sum_{i=0}^p \left(\begin{array}{c}p \\ i\end{array}\right) k^i[/itex]
subtracting k+1 from that does two things: first it cancels the i=0 term which is 1. Also we can combine the "k" with the i= p term which is kp so we have kp- k= mp. The other terms, all with 0< i< p, contain, as above, factors of p.
What would be the converse of this conjecture, How can you prove whether or not the converse holds?
thanks
Yes, it is and for exactly the reason you state: if p is prime then \left(\begin{array}{c}p \\ i\end{array}\right) for p prime and 0< i< p is divisible by p. That itself can be proven directly from the definition:
\left(\begin{array}{c}p \\ i\end{array}\right)= \frac{p!}{i!(p-i)!}
as long as i is neither 0 nor p, 0<p-i< p and so neither i! nor (p- i)! have a factor of p. Since p! does, the binomial coefficient is divisible by p. (We need p to be prime so that other factors in i! and (p- i)! do not "combine" to cancel p.)
Now, to show that np- n is divisible by p, do exactly what mathman suggested.
First, when n= 1, 1p- 1= 0 which is divisible by p. Now assume the statement is true for some k: kp- k= mp for some integer m. Then, by the binomial theorem,
[tex](k+1)^p= \sum_{i=0}^p \left(\begin{array}{c}p \\ i\end{array}\right) k^i[/itex]
subtracting k+1 from that does two things: first it cancels the i=0 term which is 1. Also we can combine the "k" with the i= p term which is kp so we have kp- k= mp. The other terms, all with 0< i< p, contain, as above, factors of p.
What would be the converse of this conjecture, How can you prove whether or not the converse holds?
thanks