Division algorithm and Prime Numbers

Question

In my class, the professor went through a proof that if $p|xy$ then $p|x$ or $p|y$. where p is a prime number. And now that I am reading through it, there is a small piece of the proof that I do not understand. He used complete induction on x and said for all y, $p|x$ or $p|y$. He then used the division algorithm in the inductive step to get

$$p=q(x+1)+r$$ $$py=q(x+1)y+ry$$

So, since $p|py$ and $p|q(x+1)y$ then $p|ry$. I don't understand how we know that $p|q(x+1)y$ and why that means $p|ry$. Can anybody help me figure that out?

Thank you.

Answer 1

I suggest a different proof.

By strong induction, we can decompose a number into its prime factors. Do so with $ xy $. Since $ p | xy $ and $p$ is prime, $p$ is amongst them. It is therefore amongst the prime factors of $x$ or those of $y$.

Answer 2

I'm guessing that what you didn't write is that the argument you are having trouble with is trying to prove that $p \mid (x+1) y$ implies $p \mid x+1$ or $p \mid y$, and therefore $p \mid (x+1) y$ is taken as a hypothesis for that part of the argument.

You probably already know your other questions but just haven't thought of them:

• If $a \mid b$, then $a \mid bc$
• If $a \mid b$ and $a \mid c$ then $a \mid b+c$