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