GCD proof using fundamental theorem of arithmetic

Question

prove: $\gcd(m,n)=1$ if and only if $\gcd(m^i,n^r)=1$

I believe you need to do something with fundamental theorem of arithmetic to prove one of the sides. Not quite sure though.

Help is appreciated.

Answer 1

• $\Leftarrow\qquad$ If $\gcd(m^i,n^r)=1$ then by the Bezout's theorem there's $u,v\in\Bbb Z$ such that

$$um^i+vn^r=1\iff (um^{i-1})m+(vn^{r-1})n=1\iff \gcd(m,n)=1$$

• $\Rightarrow\qquad$ By the contrapositive if $1\ne p=\gcd(m,n)$ then $p$ divides $m^i$ and $n^r$ so $p$ divides $\gcd(m^i,n^r)$ so $\gcd(m^i,n^r)\ne1$.

Answer 2

There are several ways to show this, but using the Fundamental Theorem of Arithmetic is certainly one way.

The key is to note that the prime decomposition of $m^i$ (for $m$ and $i$ positive integers) is the same as the prime decomposition of $m$ but with the exponents multiplied by $i$. Note especially that the same prime numbers are in both decompositions.

If $\gcd(m,n)=1$ then the prime decompositions of $m$ and $n$ have no primes in common. Then by the previous paragraph, this is also true of $m^i$ and $n^r$. The reverse implication also works.