Proof that $q^2$ is indivisible by 3 if $q$ is indivisible by 3. 
Let $q$ be a natural number. Show that if $q$ is not divisible by $3$, the neither is $q^2.$ 

Is this proved by contradiction or a different method of proof? All responses are appreciated...
 A: First, let's prove something a little more general: 


*

*If $p$ is a prime number and $p | ab$, then $p|a$ or $p|b$. 


Proof: suppose $p|ab$. Then the greatest common divisor $\gcd(a, p)$ divides $p$; since $p$ is prime, either $\gcd(a, p) = p$ or $\gcd(a, p) = 1$. Now $\gcd(a, p)$ also divides $a$; if $\gcd(a, p) = p$, then $p|a$ and we are done. So suppose we are in the case $\gcd(a, p) = 1$. 
There is a key fact about the gcd that follows from the Euclidean division algorithm: that for any given integers $a, b$, there exist integers $m, n$ such that $am + bn = \gcd(a, b)$. So in our case, there exist integers $m, n$ such that $am + pn = 1$. We then have $abm + pnb = b$. Since $p|ab$, we can write $ab = pk$ for some $k$. Now we have $pkm + pnb = b$, or that $p(km + nb) = b$. This shows $p|b$, and we are done. 
We apply this general fact to our situation: suppose $3|q^2 = qq$. Since $3$ is prime, we conclude $3|q$ or $3|q$. Done. 
A: Sure, proof by contradiction will work, or rather, proving the contrapositive works well. 
The contrapositive that is the equivalent of your statement is given by: 

Suppose $\,q\,$ is a natural number, and $\,3\mid q^2.\;$ Then $\,3\mid q.$

Suppose $q$ is a natural number, and suppose $\,3\mid q^2\,$. Then there exists an integer $\,k\,$ such that $\,3k = q^2 = q\cdot q.\;$ If you break $\,q\,$ down into its prime decomposition, what does this imply about the divisibility of $\,q\,$ by $\,3\;$ ? 

To answer the OP's question in a comment below:  By the Fundamental Theorem of Arithmetic, every integer can be decomposed uniquely into a product of primes, up to permutation (that is, the order in which prime factors appear in the product doesn't matter.)  So, e.g., $52 = 2^2\cdot 13$, and $210 = 2
\cdot 3\cdot 5 \cdot 7.$
