The converse and proving whether or not the converse holds

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 [itex]\left(\begin{array}{c}p \\ i\end{array}\right)[/itex] for p prime and 0< i< p is divisible by p. That itself can be proven directly from the definition:
[tex]\left(\begin{array}{c}p \\ i\end{array}\right)= \frac{p!}{i!(p-i)!}[/tex]
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
 

HallsofIvy

Science Advisor
Homework Helper
41,731
885
The converse of "If A then B" is "If B then A" so the converse of "If p is prime then np- n is divisible by p (for all n)" is "If np- n is divisible by p (for all n) then p is prime". I haven't looked at that in depth but I think you should try "indirect proof": if p is not prime, say p= ij for some integers i and j, can you find find an n so that np is not divisible by p?
 

Related Threads for: The converse and proving whether or not the converse holds

Replies
2
Views
1K
  • Last Post
Replies
1
Views
9K
Replies
3
Views
21K
Replies
2
Views
2K
Replies
3
Views
4K
Replies
6
Views
2K
Replies
5
Views
6K
  • Last Post
Replies
1
Views
1K
Top