# Homework Help: 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