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?

  • 1
    $\begingroup$ 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. $\endgroup$ Nov 14 '15 at 18:55

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


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.