# Using $\gcd(a,b)$ to find gcd of other values $\gcd(a^2,b)$ and $\gcd(a^3,b)$

If $\gcd(a,b) = p$, a prime, what are the possible values of $\gcd(a^2,b)$ and $\gcd(a^3,b)$?

Through examples I've been able to find the answer, but I don't know how to come up with a proof.

Update: I think gcd of either is $p^2$, but again this is just by working examples.

I'm not familiar with much number theory. I've just started the second section of my textbook, so all I know is just divisibility and primes.

-
What do you think the answer is? – Pedro Tamaroff May 11 '13 at 23:28
So tell us your conjectures. – Ted Shifrin May 11 '13 at 23:32
Are you familiar with the Unique Factorization Theorem? – Gerry Myerson May 11 '13 at 23:33
What if $a=6$ and $b=40$? – Ted Shifrin May 11 '13 at 23:41

You do not have enough information to answer unambiguously. The most we can say is that $\mathrm{gcd}(a^2,b)$ is either $p$ or $p^2$, and $\mathrm{gcd}(a^3,b)$ is one of $p$, $p^2$, and $p^3$.

For suppose $\mathrm{gcd}(a,b)=p$. Then there are integers $x,y$ such that $ax+by=p$, so (squaring this expression) $a^2x^2+b(2axy+by^2)=p^2$, showing that a linear combination of $a^2,b$ with integer coefficients is $p^2$, which implies that $\mathrm{gcd}(a^2,b)$ divides $p^2$. Since $\mathrm{gcd}(a,b)$ divides any combination of $a,b$ and therefore of $a^2,b$, then $p$ divides $\mathrm{gcd}(a^2,b)$.

Now: $\gcd(p,p^2)=p$ and $\gcd(p^2,p^2)=p^2$, so certainly $p^2$ is possible. On the other hand, $\gcd(p,p)=p$ and $\gcd(p^2,p)=p$, so $p$ is possible as well.

A similar analysis, with similar examples, gives the result for $\mathrm{gcd}(a^3,b)$.

-

Suppose $\gcd(a,b)=p$ is prime. Then both $a$ and $b$ are divisible by $p$ at least once, and at least one of the two is divisible by $p$ only once i.e. by $p$ but not by $p^2$. So suppose $a=pn$ where $n$ is not divisible by $p$, and $b=p^{50}m$. Then $\gcd(a^2,b)=p^2$ and $\gcd(a^3,b)=p^3$, etc.

But not suppose $a=pn$ and $b=pm$ where $n,m$ are not divisible by $p$. Then $\gcd(a^2,b)=\gcd(a^3,b)=p$.

Also if $a=pn$ where $n$ is not divisible by $p$, then it's possible that $\gcd(a^2,b)=\gcd(a^3,b)=p^2$. You should be able to figure out what would have to be true of the factorization of $b$ for that to happen.

-
Why is $b = p^{50}m$? – AlanH May 12 '13 at 1:30
@AlanH : That's not a conclusion I drew; it's an example. The point then is that $\gcd(a^k,b)=k$ as long as $k\le50$, and when $k>50$ then the gcd is just $50$. – Michael Hardy May 12 '13 at 17:50

Recall that integers can be factored uniquely into a product of primes, so we can write $a=p_1^{d_1}\cdots p_m^{d_m}$ and $b=q_1^{e_1}\cdots q_n^{e_n}$ where the $p_i$ and $q_i$ are prime. By relabeling, we can assume that $p_1=q_1,\ldots,p_k=q_k$ and the remaining prime factors are distinct ($k$ might be $0$). One very nice consequence of unique factorization is $$\gcd(a,b)=p_1^{\min(d_1,e_1)}\cdots p_k^{\min(d_k,e_k)}.$$ Since $\gcd(a,b)=p$, we know that $k=1$, $p_1=p$ and $\min(d_1,e_1)=1$. Note that the factorizations of $a^2$ and $a^3$ are $p_1^{2d_1}\cdots p_m^{2d_m}$ and $p_1^{3d_1}\cdots p_m^{3d_m}$ respectively, so we have $$\gcd(a^2,b)=p^{\min(2d_1,e_1)} \text{ and } \gcd(a^3,b)=p^{\min(3d_1,e_1)}.$$ Note that if $e_1$ is sufficiently large then these are $p^2$ and $p^3$ respectively, but if $e_1=1$ both are $p$ and if $e_1=2$ then both are $p^2$. Thus the possibilities are $p,p^2$ and $p^3$.

-

It is easy to prove that is $\gcd(a, b) = m$ then $\gcd(a / m, b / m) = 1$, $\gcd(k a, k b) = k \gcd(a, b)$, and if $\gcd(a, b) = \gcd(a, c) = 1$ then $\gcd(a, b c) = 1$. Splice those together.

-