Question: I was looking back at my notes on number theory and I came across this question.

Let $a$, $b$ be positive integers such that $\gcd(a, b) = 3$. What are the possible values for $\gcd(a^2, b)$?

I know it has to do with their prime factorization decomposition, but where do I go from here?

Answer: 
If $p$ is a prime, and $p|a^2$, then $p|a$; thus, if $p|a^2$ and $p|b$, then $p|a$ and $p|b$, hence $p|\gcd(a,b) = 3$. So $\gcd(a^2,b)$ must be a power of $3$.

Also, $3|a^2$ and $3|b$, so $3|\gcd(a^2,b)$; so $\gcd(a^2,b)$ is a multiple of $3$.

If $3^{2k}|a^2$, then $3^k|a$ (you can use prime factorization here); so if $3^{2k}|\gcd(a^2,b)$, then $3^k|\gcd(a,b) = 3$. Thus, $k\leq 1$. That is, no power of $3$ greater than $3^2$ can divide $\gcd(a^2,b)$.

In summary: $\gcd(a^2,b)$ must be a power of $3$, must be a multiple of $3$, and cannot be divisible by $3^3=27$. What's left? Now give examples to show all of those possibilities can occur.
We know that among all the divisors of $b$, only 3 divides $a$. There are two cases: 1) 3 divides $b$ only one time xor 2) 3 divides $a$ only one time (and $b$ more then once!). 1) $GCD(a^2,b)$ is 3. 2) 3 divides $a^2$ two times, so $GCD(a^2,b)$ is $3^2=9$.

EDIT:
I think I need to add the general law, which is extensively used here and enables short reasonings. Let $\{ p\_i\}$ be the set of all the prime divisors of $a$ or $b$. Then we have:

> 
> If $a=\prod\_{i=1}^n p\_i^{q\_i},\ b=\prod\_{i=1}^n p\_i^{r\_i}$ (some of $q\_i,\ r\_i$ might be equal to zero), then
>  $$GCD(a,b) = \prod\_{i=1}^n p\_i^{min(r\_i,q\_i)}.$$
> 
> 
>