5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you familiar with the Unique Factorization Theorem? $\endgroup$ – Gerry Myerson May 11 '13 at 23:33
  • $\begingroup$ What if $a=6$ and $b=40$? $\endgroup$ – Ted Shifrin May 11 '13 at 23:41
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Why is $b = p^{50}m$? $\endgroup$ – AlanH May 12 '13 at 1:30
  • 1
    $\begingroup$ @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$. $\endgroup$ – Michael Hardy May 12 '13 at 17:50
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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