I am given that the following proposition is true. (Proved in class)
"Suppose that $x$, $y\in \Bbb Z$, not both zero. Then there exists $m$, $n\in\Bbb Z$ such that $$mx + ny = d$$ where $d$ is the greatest common factor of $x$ and $y$. Moreover, if $ax + by = f$ for some $a$, $b$, $f\in\Bbb Z$ then $d | f$."
Using the statement above, prove that if $p$ is prime and $p|xy$ then $p|x$ or $p|y$. (hint: if $p$ does not divide $x$, then $p$ and $x$ are relatively prime)(We just learned the definition of relatively prime, so that is probably why that hint is there.)
I just don't get why I need to use the statement above. The way I see it, if $p|xy$ then there are two possible cases:
- $p|x$
- $p$ does not divide $x$
And obviously, if $p|x$ then the original statement is true, and if $p$ does not divide $x$ then I just need to prove that $p|y$ in that case which I could do. That seems simpler than any other way, am I wrong? Working with prime numbers always throws me. I don't get why it matters if $p$ is prime, so if someone wants to explain that, it would be a nice addition.
Best Answer
Hint $gcd(p,x)$ is a divisor of $p$. Therefore it is either $p$ or $1$.
If the gcd is $p$ it means $p|x$ and you already treated that case.
Otherwise, by the lemma $$mp+nx=1$$ Multiply this by $y$, and use that $p|xy$.
P.S. The key to the proof is that $p$ is prime, otherwise the gcd could be something else but 1 or p. And it was already shown by examples that in that case the statement is not true.