Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer
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$.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.