Proof $3\mid xy$ if and only if $3\mid x$ or $3\mid y$

Question

State whether the following statement is true and give a proof.

For every integer $x,y$: $(xy\mid 3)$ if and only if $3\mid x$ or $3\mid y$

I get that this statement is true the product of 2 numbers is divisible by $3$ only if one of the numbers $x$ or $y$ is divisible by $3$. However how do I prove it algebraically?

Answer 1

More generally, if $p$ is a prime and $x,y$ are integers, then if $p$ divides $xy$, then $p$ divides $x$ or $p$ divides $y$.

Suppose $p$ is not a divisor of $x$. Then since $p$ is prime, $p$ and $x$ have non common nontrivial divisor, i.e., $\gcd(p,x)=1$. By the extended Euclidean algorithm,

$1=ap+bx$

for some integers $a,b$. Thus

$y = ayp+bxy.$

Then $p$ divides the right-hand side $ayp+bxy$, since $p$ divides $xy$ by hypothesis. Hence, $p$ divides the left-hand side, which is $y$. Done.