# What are the possible values for $\gcd(a^2, b)$ if $\gcd(a, b) = 3$?

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?

-

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.

-

HINT: write out the prime factorization of a and that of b. Divisors of a are products of the primes in the prime factorization of a. Same for b. since gcd(a,b)=3, then a and be share a $3^{1}$ in their prime factorization. What happens when you square a number? You end up squaring all the primes, including the 3.

-
I see that all the primes get squared for a when a is squared. But how would that change the GCD from 3? –  Dominick Gerard Feb 23 '12 at 22:24
@DominickGerard: Check the edit I added to my answer, it should make things clearer. –  savick01 Feb 24 '12 at 9:46

There exist integers $x$ and $y$ such that $ax+by=3$. Square both sides. Then $$a^2 x^2+b(2axy+by^2)=9,$$ and therefore $\gcd(a^2,b)$ divides $9$. Finally, show that $1$ cannot happen, but $3$ and $9$ can.

-
Remark $\:$ This is just a Bezout form of the first proof I gave, i.e. it proves $(a^2,b)\:|\:(a,b)^2$ not by gcd laws but, rather, by writing the gcd in Bezout form $\:(a,b) = ax+by,\:$ which yields $$(a^2,b)\ |\ a^2,b\ \ \Rightarrow\ \ (a^2,b)\:|\:a^2x^2 + b\:(2axy+b^2x^2) = (ax+by)^2 = (a,b)^2$$ Using gcd laws yields a more general proof, since the proof works in any domain with gcds, e.g. it works in non-PID UFDs such as $K[x,y]$, where the Bezout proof fails. –  Math Gems Feb 23 '12 at 23:16
@Math Gems: My opinion is that dealing directly with common divisors, like you did, is better. Just wanted to mention the linear combination idea to add to the mix. –  André Nicolas Feb 23 '12 at 23:16
Yes, the Bezout proof is more accessible to those not fluent in gcd laws. It's instructive to compare the two proofs. Hence my above remark. –  Math Gems Feb 23 '12 at 23:19

Hint $\rm\: \ (a,b)\ |\ (a^2,b)\ |\ (a,b)^2\$ since $\rm\ (a^2,b)\ |\ a^2,ab,b^2\ \Rightarrow\ (a^2,b)\ |\ (a^2,ab,b^2) = (a,b)^2$

Therefore $\rm\:3\ |\ (a^2,b)\ |\ 9\:$ when $\rm\:(a,b) = 3\ \$ QED

Or: $\:$ let $\rm\:a = 3^K A,\:\ b = 3^N B,\ \ 3\nmid A,B.\ \$ $\rm(a,b)=3\ \Rightarrow \ (A,B) = 1\:$ and $\rm\:\min(K,N) = 1.\:$ Thus

$$\rm (a^2,b) = (3^{2K} A^2, 3^N B) = (3^{2K},3^N)(A^2,B) = (3^{2K},3^N) = 3\: \ if\: \ N\! =\! 1\: \ else \ 9\ ( N \ge 2\Rightarrow K = 1)$$

-

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)}.$$

-