Theorem on Division by a Prime

[DeadOriginal]

Homework Statement

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.

Homework 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.

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?

 

[Dustinsfl]

This is called Euclid's Lemma.

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

 

[DeadOriginal]

This is called Euclid's Lemma.

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

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.

 

[Dustinsfl]

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.

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.

 

[DeadOriginal]

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.

I included the proof above.

I can't seem to follow why we can say that p divides ry. Wouldn't we need to know that p also divides (x+1)y before we can say that p divides ry?

 

[DeadOriginal]

Never mind. I figured it out.