How to show that a certain number is not divisible by another in a proof I am given the prompt:

"Let $x$ and $y$ represent two integers such that their product $xy$ is divisible by 3. Then at least one of the two integers is divisible by 3."

I am to prove this using contraposition.
So far, I have, "If neither x nor y are divisible by 3, then their product xy is not divisible by 3."
My problem comes in when trying to prove this. I am not sure how I am supposed to say that a number is not divisible by 3 in a useful way that I can use in the proof. How can you show that x or y is not divisible by 3 so that I can show that their product is also not divisible by 3?
 A: You can use the division algorithm: 

Division Algorithm If $a$ and $b$ are integers, with $b\neq 0$, then there exist unique integers $q$ and $r$ such that $a=bq+r$ and $0\leq r\lt |b|$. The integer $q$ is called the quotient and $r$ is called the remainder of dividing $a$ by $b$.

As a corollary, $b$ divides $a$ if and only if the remainder is $0$.
So now, write
$$\begin{align*}
x &= 3q_1+r_1\\
y &= 3q_2+r_2
\end{align*}$$
with $0\leq r_1\lt 3$, $0\leq r_2\lt 3$. If you are assuming that neither $x$ nor $y$ are divisible by $3$, then in fact $r_1,r_2\in\{1,2\}$.
Now, for example, if $r_1=r_2=1$, then
$$\begin{align*}
xy &= (3q_1+1)(3q_2+1)\\
 &= 9q_1q_2+3q_1+3q_2+1\\
 &= 3(3q_1q_2+q_1+q_2)+1,\end{align*}$$
and so when we divide $xy$ by $3$ we get a quotient of $3q_1q_2+q_1+q_2$, and a remainder of $1$, so $xy$ is not divisible by $3$.
You should check the other two possibilities (one remainder equal to $1$ and the other to $2$; both equal to $2$; note that one of them will require a bit of care).
A: Every integer has a unique prime factorization. If neither $x$ nor $y$ is divisible by $3$, then neither $x$ nor $y$ has $3$ as a prime factor. Hence, the product given by $xy$ will also fail to have $3$ as a prime factor. This of course implies that $xy$ is not divisible by $3$.
