Prove ∀x ∈ Z, ∀y ∈ Z, 3 div xy ⇒ (3 div x ∨ 3 div y)

Question

I am trying to prove:

∀y ∈ Z, 3 div xy ⇒ (3 div x ∨ 3 div y)

This is what I have right now is:

Given $x$ in $Z$ and $y$ in $Z$, assume 3 div xy, that is $xy = 3k$ for some $k$ in $Z$.

I'm not sure where to go from here. I know I want to say something like $x=3k$ or $y=3k$ but I don't think I can jump straight from what I have to those two statements. I also thought about saying $x=3k/y$ or $y=3k/x$, but again, I'm not sure if it is valid to say these. Can someone confirm if it is correct to say these things or if there is something else I should be doing?

Answer 1

Since $xy=3k$ and that $3$ is a prime, either $x$ or $y$ must have a prime factor $3$, and thus is divisible by $3$.

Therefore, if $3\mid xy$, $3 \mid x$ or $3 \mid y$.

Answer 2

You could use that fact that $3$ is a prime and then use something like Euclid's Lemma ...

but for a proof that does not use as 'heavy' of artillery, you could do this by contraposition:

Assume that $3$ does not divide $x$ and also not divides $y$. Then $x=3k+1$ or $x=3k+2$. Similar for $y$. So you get $4$ cases. Now show that in each case, their product will be of the form $3n+1$ or $3n+2$