# How can I find the possible values that $\gcd(a^3,b^4)$ can take, if $\gcd(a,b)=10$?

I don´t know how to find them, any ideas would really help.

-

Hint: Since $10$ divides $a$ and $b$, we can write $\;a = 10k,\; b = 10j\;$ where $k, j$ are coprime integers (else $\gcd(a, b) > 10$). So $$\;a^3 = (10k)^3 = 1000k^3;\quad \;b^4 = (10j)^4 = 10000j^4.$$

Now consider $$\;\gcd(a^3, b^4) = \gcd(1000k^3, 10000j^4).$$

-
Yes, but there might be factors of $2$ or $5$ lurking in $j,k$ – Ross Millikan Feb 21 '13 at 21:04
Yes, there may: I'm not suggesting otherwise...just helping to give a helpful nudge. But your comment will help the OP not to make any conclusions too quickly. Thanks for including it. – amWhy Feb 21 '13 at 21:06
Richard, feel free to post follow-up questions to any of the answers if you're not clear as how an idea or hint might help, or if you have any other questions. – amWhy Feb 22 '13 at 0:31
Thank you amWhy, at this point I have come to the conclusion that only 1000,2000,5000 and 10000 are the only posible values for the gcd. Noting that gcd(j^3,k^4)=1 in addition to your hint did the trick. – Richard Codwater Feb 22 '13 at 2:39
gcd(a^3,b^3)=+10 – Babak S. Feb 22 '13 at 6:21

First idea: what's the biggest number you can think of that absolutely has to divide both $a^3$ and $b^4$, if $10$ divides both $a$ and $b$?

Second idea: if you changed the problem to $\gcd(a^4,b^4)$, would it be easier? What would the answer be? It might not be the same answer as for $\gcd(a^3,b^4)$, but it's certainly a multiple of $\gcd(a^3,b^4)$, since $a^3\mid a^4$.

Together, the two ideas should give you both a lower bound and an upper bound for $\gcd(a^3,b^4)$. Then you can start looking for examples that give you the various possibilities in that range (or maybe you'll find a reason why certain such possibilities never occur).

-

Hint $\rm\ 10^3\!=(a,b)^3\mid (a^3,b^4)\mid (a^4,b^4)=10^4\:$ so, by unique factorization, the only possible values are $\rm\,10^3\{1,2,5,10\},\:$ which are all realized for the values $\rm\ a,b\, =\, 10,10;\ \ 20,10;\ \ 50,10;\ \ 100,10.$

-

Let's think about the divisors :

Since ($a$,$b$) is equal to 10, and you have ($a^3$,$b^{3}$) as a subset, then you have $10^1$,$10^2$,$10^3$, and since you also have and extra b, you have an extra 10, you can can go up to $10^4$.

But also consider, the factors of 10: $2 \cdot 5$, so we also have :

$2^1$,$2^2$,$2^3$,$2^4$, and

$5^1$,$5^2$,$5^3$,$5^4$,

And all their combinations. However the 10 will be the greatest of these, so you will get one of :

($10^4,10^3,10^3 \cdot 2,10^3 \cdot 5$)

-
I'm so happy I got an upvote. I didn't really have any idea it was correct. – Cris Stringfellow Feb 21 '13 at 21:07
Upvoting doesn't necessarily imply the question is correct. – Pedro Tamaroff Feb 21 '13 at 21:11
Sigh.... What to do. – Cris Stringfellow Feb 21 '13 at 21:12
$\gcd(70^3, 110^4)$ doesn't appear anywhere on your list... – Steven Stadnicki Feb 21 '13 at 22:50
@Steven Stadnicki How did you get those two? – Cris Stringfellow Feb 22 '13 at 12:18