Elementary number theory proof difficulty

Question

I am having trouble proving this implication involving greatest common divisors

Prove that for all $a,b\in\Bbb{Z}$, if $gcd(a,b)=1$, then $gcd(a^n,b^m)=1$ for all $n,m\in\Bbb{N}$

Since $gcd(a,b)=1$, then $\exists x,y\in \Bbb{Z}$ such that $ax+by=1$ by the Coprimeness Characterization Theorem.

Raising both sides to the power to the power of $n$ gives $(ax+by)^n=1$

$$\sum^n_{k=0}{n \choose k}(ax)^{n-k}(by)^k=1\implies a^nx^n+b\sum^n_{k=1}{n \choose k}(ax)^{n-k}b^{k-1}y^k=1$$

A similar argument of course applies for raising both sides to the power of $m$: $(ax+by)^m=1$

$$\sum^m_{k=0}{m \choose k}(ax)^k(by)^{m-k}=1\implies b^my^m+a\sum^m_{k=1}{m \choose k}a^{k-1}x^k(by)^{m-k}=1$$

From both of these I can conclude separately that $gcd(a^n,b)=1$ and $gcd(a,b^m)=1$, but I don't know how to prove that $gcd(a^n,b^m)=1$ with $n$ and $m$ combined. Any help?

Answer 1

An alternate and arguably a better approach is as follows: Suppose the $\gcd(a^m,b^n)>1$. Let a prime $p \mid \gcd(a^m,b^n)$. Then $p \mid a^m$ and $p \mid b^n$. By the prime property ($p$ divides a product, hence divides at least one component of the product), we get $p \mid a$ and $p \mid b$. Thus $p \mid \gcd(a,b)$. But $\gcd(a,b)=1$. So we get a contradiction.

Answer 2

Raise the equation to the power $m+n-1$ (in the exceptional case $m=n=0$, it is clear that $\gcd(1, 1) = 1$): $$\sum_{i=0}^{m+n-1} \binom{m+n-1}{i} a^i x^i b^{m+n-1-i} y^{m+n-1-i} = 1.$$ Now each term is divisible either by $a^m$, if $i \ge m$, or by $b^n$, if $m+n-1-i \ge n$. (One of these must hold; otherwise, $i \le m-1$ and $m+n-1-i \le n-1$, and summing gives a contradiction $m+n-1 \le m+n-2$.)

Answer 3

That seems very complicated and I'd give up.

If $\gcd(a,b)= 1$ means that $a$ and $b$ have no prime factors in common. $a^n$ has only the prime factors that $a$ has and $b^m$ has only the prime factors that $b$ has.

So $a^n$ and $b^n$ have no prime factors in common either. So $\gcd(a^n, b^m) = 1$.

Simple as that.