Theorem on Division by a Prime

1. May 18, 2012

1. The problem statement, all variables and given/known data
I am working my way through the Theorem on Division by a Prime. "Let p be a prime number.Then for all integers x and y, if p divides xy, then p divides x or p divides y.

The proof is being done by complete induction.
Proof. Let x be a whole number p a prime numberk and y be an integer. Then let P(x) be the sentence "If p divides xy, then p divides x or p divides y.

Base Case: P(0) says if p divides (0*y) then p divides 0 or p divides y. This is true since anything divides 0.

Inductive Step: Assume P(0),...,P(x) are all true. We wish to show that P(x+1) is also true. Now x+1<p or x+1>=p.

Case 1: Assume x+1<p. So by the division lemma, p=q(x+1)+r for some integer q and r in {0,1,...,x}. Now multiply by y such that py=q(x+1)y+ry. Then ry=py-q(x+1)y. Thus p divides ry. Now r satisfies the induction hypothesis so P(r) is true. Thus p divides r or p divides y. If p divides r then since 0<=r<x+1<p we know that r=0. So p=q(x+1). Since p is prime then q=1 or x+1=1. But q does not = 1 since p>x+1. Thus x+1=1 and so (x+1)y=y and so since p divides (x+1)y, p must divide y. So P(x+1) is true.

Case 2: Assume x+1>=p. By the division lemma, x+1=qp+r for some integer q and r in {0,1,...,p-1}. Since p<=x+1, then p-1<=x so r in {0,1,...,x}. Now multiply by y such that (x+1)y=qpy+ry so ry=(x+1)y-qpy. Thus p divides ry. By the inductive hypothesis p must divide r or p must divide y. If p divides r then since x+1=qp+r, we must have p divides x+1. So P(x+1) is true.

Conclusion: Therefore, by complete mathematical induction, P(x) is true for all whole numbers x so it is true for all integers x.

2. Relevant equations
The part that I don't understand is py=q(x+1)y+ry so ry=py-q(x+1)y, so p divides ry.

3. The attempt at a solution
I don't understand how we can say that p divides ry. I know that if p divides a number say x, then there exists an integer k such that x=pk so we can say y is that integer but here we also have the extra term q(x+1)y. Doesn't that interfere with the division of p?

Last edited: May 18, 2012
2. May 18, 2012

Dustinsfl

This is called Euclid's Lemma.

Why would you use induction? You can do this directly.

3. May 18, 2012

Hmm.. Thanks for the post. I will definitely look that up and try to learn it to surprise my professor if he by any chance puts it on a test but the reason why I am using complete induction for this is because it is being used as an example in my proofs class to teach us how to use complete induction.

4. May 18, 2012

Dustinsfl

If you are using induction, are you sure you aren't trying to prove the generalized Euclid's Lemma?

$p|a_1a_2\cdots a_n$ Then $p|a_i$.

This is a case to use induction on it.

5. May 18, 2012