# Can one show that if $\gcd(p^k,b)=1$, then $p^k \nmid b$?

If $\gcd(a,b)=1$ and $p \mid a$ then $p \nmid b$. But how one can show that $\gcd(p^k,b)=1$? And can one show that if $p^k \nmid b$, then $\gcd(p^k, b)=1$? And can one show that if $\gcd(p^k,b)=1$, then $p^k \nmid b$?

-

## 1 Answer

Since $\gcd(p^k,b)=1$ doesn't hold in general, I'll assume that you intended the first question to share the assumptions of the first sentence, $\gcd(a,b)=1$ and $p\mid a$. In that case, since $p\nmid b$ and $p$ is the only prime factor in $p^k$, it follows that $p^k$ and $b$ have no factors in common, and thus $\gcd(p^k,b)=1$.

The answer to the second question is no: $p^2\nmid p$, but $\gcd(p^2,p)\ne1$.

The answer to the third question is yes, for if $p^k\mid b$, then $p^k\mid\gcd(p^k,b)$, so $\gcd(p^k,b)\ne1$.

-
How you show that if $gcd(a,b)=1$ and $p \mid a$, then $p \nmid b$? And can you show intermediate stages from $gcd(a,b)=1$ and $p \mid a$ to $gcd(p^k, b)=1$? To me it doesn't look as trivial but requires explanation in language of math if possible. –  laovultai Oct 29 '11 at 14:23
@alvoutila: I get the impression (from this comment but also from the question as a whole) that you should review your understanding of the greatest common divisor. If $p\mid a$ and $p\mid b$, then $p$ is a common factor of $a$ and $b$, so their greatest common divisor is at least $p$. –  joriki Oct 29 '11 at 14:25
But how would you show that then $gcd(p^k,b)=1$ using previous assumptions and definition(s) of gcd? –  laovultai Oct 29 '11 at 14:45
@alvoutila: I showed this in my answer above. Since you seem to be lacking a rather basic understanding of factorization, it's very difficult for me to know what part of the explanation requires more detail. Please be as specific as you can in your questions and refer specifically to the part of the answer that you don't understand. Also, I would suggest that you read a basic text that covers things like unique factorization and gcds, as the answers to your questions will probably become apparent to you once you've understood those concepts. –  joriki Oct 29 '11 at 14:55