If $\gcd(a,b)=1$, then $\gcd(a^n,b^n)=1$

Question

If $\gcd(a,b)=1$, then $\gcd(a^n,b^n)=1$

This seems clear, but I don't know how to prove this..

I was trying to show this by induction such that if $a^{n+1}$ = $rs$ and $b^{n+1}$ = $rt$, then $s,t$ are divisible by $a,b$ respectively, but i think this is a wrong way..

Answer 1

Let $a = p_1 ... p_n$ and $b = q_1 ... q_m$ be the prime factorization of $a$ and $b$ (possibly with repetition). $gcd(a,b) = 1$ implies that $p_i \neq q_j$ for all $1 \leq i \leq n$ and $1 \leq j \leq m$. Hence $a^k = p_1^k ... p_n^k$ and $b^k = q_1^k ... q_m^k$ also have no prime factors in commmon. So $gcd(a^k, b^k) = 1$, as well.

Answer 2

Assuming that we're working in a Unique Factorization Domain, then the factorizations of $a^n$ and $b^n$ are simply the factorizations of $a$ and $b$, repeated $n$ times. Then if there were a common factor between $a^n$ and $b^n$, there would be a common irreducible factor between $a^n$ and $b^n$, and this would have to appear in the factorizations of both $a$ and $b$, and since $\operatorname{gcd}(a,b) = 1$, $\operatorname{gcd}(a^n,b^n) = 1$.

Answer 3

The proof is by induction. Let us denote $\gcd(a,b) = d$.

For $n=1$, there is nothing to prove. Assume that it is true for all $n \leq k$ i.e. $\gcd(a^n,b^n) = d^n$ for all $n \leq k$. We now need to prove that $\gcd(a^{k+1},b^{k+1}) = d^{k+1}$. Since $\gcd(a^k,b^k) = d^k$, there exists $x_k,y_k \in \mathbb{Z}$ such that $a^k x_k + b^k y_k = d^k$. We also have $x,y \in \mathbb{Z}$ such that $ax+by = d$. Hence, we get that $$(ax+by) \left( a^k x_k + b^k y_k \right)^2 = d^{2k+1}.$$ Expanding this, we get that $$a^{k+1} \left( a^k x_k^2 x + a^{k-1} b x_k^2 y + 2 b^k x_k y_k x \right) + b^{k+1} \left( b^k y_k^2 y + ab^{k-1} y_k^2 x + 2 a^k x_k y_k y \right) = d^{2k+1}.$$ Since $d|a$ and $d|b$, we have that $a = d e$ and $b = df$. Hence, we get that $$a^{k+1} \left( d^k e^k x_k^2 x + d^k e^{k-1} f x_k^2 y + 2 d^k f^k x_k y_k x \right) + b^{k+1} \left( d^k f^k y_k^2 y + d^k ef^{k-1} y_k^2 x + 2 d^k e^k x_k y_k y \right) = d^{2k+1}.$$ This gives us that $$a^{k+1} \left( e^k x_k^2 x + e^{k-1} f x_k^2 y + 2 f^k x_k y_k x \right) + b^{k+1} \left( f^k y_k^2 y + ef^{k-1} y_k^2 x + 2 e^k x_k y_k y \right) = d^{k+1}.$$ Hence, we have found integers $$x_{k+1} = \left( e^k x_k^2 x + e^{k-1} f x_k^2 y + 2 f^k x_k y_k x \right), \, y_{k+1} = \left( f^k y_k^2 y + ef^{k-1} y_k^2 x + 2 e^k x_k y_k y \right)$$ such that $$a^{k+1} x_{k+1} + b^{k+1} y_{k+1} = d^{k+1}.$$ Hence, we have that $\gcd(a^{k+1}, b^{k+1}) \vert d^{k+1}$. It is also true that $d^{k+1} \vert a^{k+1}$ and $d^{k+1} \vert b^{k+1}$, since $d \vert a$ and $d \vert b$. Hence, $d^{k+1} \vert \gcd(a^{k+1}, b^{k+1})$. Hence, we get that $$\gcd(a^{k+1}, b^{k+1}) = \gcd(a,b)^{k+1}.$$ Hence, by the principle of mathematical induction, we have that $$\gcd(a^n,b^n) = \gcd(a,b)^n, \,\, \forall n \in \mathbb{Z}^+.$$

Answer 4

We use Bézout's Theorem. Recall that the integers $c$ and $d$ are relatively prime iff there exist integers $x$ and $y$ such that $cx+dy=1$.

Suppose that $\gcd(x,y)=1$, and let $x$ and $y$ be integers such that $ax+by=1$. Then $(ax+by)^{2n-1}=1$. Now imagine expanding $(ax+by)^{2n-1}$ using the Binomial Theorem. There are $2n$ terms in the expansion. The first $n$ terms are divisible by $a^n$, and the last $n$ are divisible by $b^n$. It follows that there are integers $u$ and $v$ such that $a^n u+b^n v=1$. Thus $\gcd(a^n,b^n)=1$.

Answer 5

Hint $\rm\ n,m>0,\,$ prime $\rm\,p\mid a^n,b^m\Rightarrow\:p\mid a,b\:$ by prime $\rm\:p\mid d_1\cdots d_k\Rightarrow p\mid d_1\, $ or $\rm\,\ldots\,$ or $\rm \,p\mid d_k,\,$ by Euclid's Lemma ($k$-ary inductive extension), or by existence & uniqueness of prime factorizations.

Or more generally, see my post here on the "Freshmans Dream" for gcds or ideals.

Or Gauss's Lemma (GL) yields a quick proof. Let $\rm\:{\cal C}(f)\:$ denote the content of a polynomial, i.e. the gcd of its coefficients. GL states $\rm\: {\cal C}(f\,g)\ =\ {\cal C}(f)\ {\cal C}(g)\ $ hence

$\rm\qquad\qquad\qquad\ \ 1\ =\ (a,b)\ =\ {\cal C}\:(a\ x + b)\ =\ {\cal C}\:(a\ x - b)$

$\rm\qquad\qquad \Rightarrow\ \ 1\ =\ {\cal C}\:((a\ x + b)\:(a\ x - b))\ =\ {\cal C}\:(a^2\: x^2 - b^2)\: =\: (a^2,b^2)$

Iterating shows that $\rm\,(a^n,b^n) = 1\,$ for $\rm\:n = 2^k,\,$ hence for all $\rm\:n,\:$ by $\rm\,m\le n\,\Rightarrow\,(a^m,b^m)\:|\:(a^n,b^n),\,$ another example of the "up then down" (or interval) induction.

Corollary $\,\ (A^n,B^n) = (A,B)^n$

Proof $ $ Cancelling $\, c^n := (A,B)^n $ reduces it to the above, by $\,(A/c,B/c) = (A,B)/c = 1,$ by the GCD Distributive Law.

Answer 6

We can proceed by induction using the associativity of gcd:

$\begin{align}\gcd(a^n,b) &=\gcd(a^n,b\cdot\gcd(a,1))&\gcd(a,1)=1\\ &=\gcd(a^n,\gcd(ab,b))&\lambda\gcd(x,y)=\gcd(\lambda x,\lambda y)\\ &=\gcd(a^n,ab,b)&\text{associativity}\\ &=\gcd(\gcd(a^n,ab),b)&\text{associativity}\\ &=\gcd(a\cdot\gcd(a^{n-1},b),b)&\text{induction }\gcd(a^{n-1},b)=1\\ &=\gcd(a,b)\\ &=1\end{align}$

By symmetry you get both : $\quad\gcd(a,b^n)=\gcd(a^n,b)=1\quad\forall n\in\mathbb N$

Using exactly the same reduction process we get:

$\begin{align}\gcd(a^n,b^m) &=\gcd(a^n,b^m\cdot\gcd(a,1))\\ &=\gcd(a^n,\gcd(ab^m,b^m))\\ &=\gcd(a^n,ab^m,b^m)\\ &=\gcd(\gcd(a^n,ab^m),b^m)\\ &=\gcd(a\cdot\gcd(a^{n-1},b^m),b^m)&\text{induction }\gcd(a^{n-1},b^m)=1\\ &=\gcd(a,b^m)\\ &=1\end{align}$

And we can conclude, notice that this is a strong induction because we suppose it verified for all couples $<(n,m)$ with lexicographic ordering. (check this https://math.stackexchange.com/a/7665/399263)