1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Theorem on Division by a Prime

  1. May 18, 2012 #1
    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. jcsd
  3. May 18, 2012 #2
    This is called Euclid's Lemma.

    Why would you use induction? You can do this directly.
  4. May 18, 2012 #3
    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.
  5. May 18, 2012 #4
    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.
  6. May 18, 2012 #5
    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?
  7. May 20, 2012 #6
    Never mind. I figured it out.
    Last edited: May 20, 2012
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook