Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer
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. – alvoutila 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? – alvoutila 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.