# Proof that if $\gcd(a,b) = 1$ then $\gcd(a^n, b^m) = 1$ [duplicate]

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 StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jun 24 at 23:24

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.