# Prove that if $a$ and $b$ are coprime then so are $a^n$ and $b^m$

I have to prove that if a and b are relatively prime then so are $$a^n$$ and $$b^m$$ by contrapositive I'm asking for help please because i really don't know how to proceed and this assignment is due this afternoon Can someone please just give me a hint or something to start with I tried solving it with different ways but it doesn't work

I'd really appreciate your help.

• Did you try to use prime factorization? – Mark Apr 24 at 10:38
• Do you know that, if $\operatorname{gcd}(a, b) = 1$ and $\operatorname{gcd}(a, c) = 1$, then $\operatorname{gcd}(a, bc) = 1$? You can use this fact and induction to solve this problem. First show $\operatorname{gcd}(a, b^m) = 1$ by induction on $m$, then show $\operatorname{gcd}(a^n, b^m) = 1$ by symmetry of the variables $a, n$ and $b, m$. – Theo Bendit Apr 24 at 10:41
• I'll try to solve it this way thank you so much for replying – Byun Bacon Gogh Apr 24 at 10:56

## 1 Answer

If $$\gcd(a^n,b^m)\neq 1$$ then there exist a prime $$p$$ such that:

$$p|a^n,b^m\Rightarrow p|\underbrace{a\times...\times a}_{n}, \underbrace{b\times...\times b}_{m}$$

For the definition of prime number :

$$p|ab\Rightarrow p|a \vee p|b$$

In our case since all of the factors are equal:

$$p|a \wedge p|b$$

So if $$a^n,b^m$$ are not coprimes, then $$a,b$$ are not coprimes

:)

• thank you soo much i didn't knew it was simplr you really saved me thank you so much – Byun Bacon Gogh Apr 24 at 10:53
• The result you used is known as Euclid's lemma. – Chris Custer Apr 24 at 11:54