This question already has an answer here:

Proof via induction for $n,m \geq 0$ that if $\gcd(a,b) = 1$ then $\gcd(a^n, b^m) = 1$ for any $n,m$ that are positive integers.


marked as duplicate by Leucippus, user10354138, Bill Dubuque elementary-number-theory Jun 24 at 23:24

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


In the proof, I will use the following theorem:

If a prime p divides a*b then p either divides a or b or both

Now the proof

Say by way of contradiction gcd(an,bm) = k > 1

Recall for all integers k greater than 1, there is a prime p such that p divides k. let p be such a prime.

k is the gcd of an and bm thus k divides an and bm
p divides k thus p divides an and bm
Recall that if a prime divides the product of two integers it must divide one of them, as a corollary we have that if p divides an, p must divide a. similarly p divides b.

Thus p divides a and b, so p must divide gcd(a,b) however gcd(a,b) = 1. Thus by way of contradiction, gcd(an,bm) = 1.

As your question suggests, there is induction in this proof. I have hidden the induction step in the corollary.

Try proving the corollary of the theorem I stated via induction.


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