# If $p$ is prime and $\gcd(m,p) = 1$ show that $\gcd(m,p^k) = 1$

If $p$ is prime and $\gcd(m,p) = 1$ show that $\gcd(m,p^k) = 1$ where $k\geq1$.

I think I have come up with a solution:

Suppose $m$ has prime factorization $m = p_1^{a_1}...p_n^{a_n}$ where $p_i$ is prime. Since $\gcd(m,p) = 1$ none of $p_i = p$. Now if $\gcd(m,p^k) \neq 1$ then the $\gcd$ must be $p^n$ with $0< n \leq k$. Note that the divisors of $m$ are the integers $p_1^{\bar{a_1}}...p_n^{\bar{a_n}}$ with $0\leq \bar{a_i} \leq a_i$.

So then we must have that $p^n = p_1^{\bar{a_1}}...p_n^{\bar{a_n}}$ so then both numbers must have the same prime factorization so that means that one of $p_i = p$ a contradiction. Which proves the result.

Is this argument fine?

• Looks good. Longer than necessary. If $\gcd(m,p^k)\gt 1$, then some prime $q$ divides $m$ and $p^k$. Argue that $q=p$ from Euclid's Lemma, if a prime $q$ divides a product it divides one of the terms. – André Nicolas Nov 14 '15 at 18:55

## 1 Answer

It is fine, though it feels a bit elaborate to start speaking of prime factorizations for this case (but it is still an excellent way to think about gcds in general).

It would probably be enough to say something like

Since $\gcd(m,p)=1$, $p$ cannot divide $m$ (otherwise $p$ would be a greater common divisor).

The only divisors of $p^k$ are $p^n$ for $0\le n\le k$ and if any of those except $1$ divides $m$, then $p$ will also divide $m$, which we know it doesn't. So $1$ is the only (positive) common divisor of $m$ and $p^k$.