Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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..
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.
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$.
Lemma: $\gcd(a,b)=1\implies\gcd\left(a^2,b^2\right)=1$
Proof: By Bezout, $\gcd(a,b)=1$ implies $$ \begin{align} ax+by&=1\\ a^2x^2&=1-2by+b^2y^2\\ \left(2y-by^2\right)b&=1-a^2x^2\\ \left(2y-by^2\right)^2b^2&=1-2a^2x^2+a^4x^4\\ \left(2x^2-a^2x^4\right)a^2+\left(2y-by^2\right)^2b^2&=1 \end{align} $$ Therefore, $\gcd\left(a^2,b^2\right)=1$.$\qquad\square$
Corollary: $\gcd(a,b)=1\implies\gcd\left(a^{2^n},b^{2^n}\right)=1$
Proof: Induction using the Lemma.$\qquad\square$
Thus, for any $k$, we can find an $n$ so that $k\le2^n$. The Corollary says that there are $x_n$ and $y_n$ so that $$ a^{2^n}x_n+b^{2^n}y_n=1 $$ and therefore, $$ a^k\left(a^{2^n-k}x_n\right)+b^k\left(b^{2^n-k}y_n\right)=1 $$ Thus, $\gcd(a,b)=1\implies\gcd\left(a^k,b^k\right)=1$.
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}^+.$$
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.
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$.
You just need to show that $\gcd(a,b) = 1 \implies \gcd(a^n,b) = 1$, then you have $1 = \gcd(a,b) = \gcd(a^n,b) = \gcd(b,a^n) = \gcd(b^n,a^n) = \gcd(a^n,b^n)$.
From Bézout's identity, $\gcd(a,b) = 1 \iff \exists x,y: ax + by = 1$
Given $\gcd(a,b) = 1$, there exist integers $x$ and $y$ such that $ax + by = 1$. So $(ax + by)^n = 1$.
You can expand $(ax + by)^n$ to get $a^nx^n$ plus a bunch of other terms that are each divisible by $b$. So there exists $y'$ such that $a^nx^n + by' = 1$, so $\gcd(a^n,b) = 1$.
Suppose $\gcd(a^n,b^n)\gt1$. Let $d\gt1$ be a common divisor, and let $p$ be a prime divisor of $d$. Then $p$ divides both $a^n$ and $b^n$. But an elementary induction argument, using the theorem that if a prime divides a product of two numbers then it divides one of the two factors, shows that $p\mid x^n$ implies $p\mid x$ for any (integer) $x$. Hence $p$ divides both $a$ and $b$, implying $p\mid\gcd(a,b)$, which contradicts the assumption $\gcd(a,b)=1$.
Note: The key step, $p\mid x^n\Longrightarrow p\mid x$, is Proposition 12 of Book IX in Euclid's Elements.
Here's a colored, edited version of user17762's answer.
The proof is by induction. Let us denote $\gcd(a,b) = d$. It's given $\gcd(a,b) = 1
\iff$
by Bezout's Lemma, there exist $x,y \in \mathbb{Z}$ such that $ax+by = d. (\dagger)$
Assume that the statement is true for all $n \leq k$. Scilicet $\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$.
Multiply this with $(\dagger)$ to result in $\begin{align} (ax+by) \left( a^k x_k + b^k y_k \right)^2 & = d^{2k+1}. \\ \color{green}{a^{2k + 1}xx_k^2 + a^{k + 1}2b^kx_ky_kx} \color{blue}{+ ab^{2k}yk^2x} &= \\ + \color{red}{a^{2k}bx_k^2y} + b^{k + 1}2a^kx_ky_ky + b^{2k+1}y_k^2y \end{align}$
$LHS = \color{green}{a^{k+1} \left( a^k x_k^2 x \color{red}{+ 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 + \color{blue}{ab^{k-1} y_k^2 x} + 2 a^k x_k y_k y \right) $
Since $d|a$ and $d|b$, we have that $\color{brown}{a = d e}$ and $\color{brown}{b = df}$. $LHS = a^{k+1} \left( \color{brown}{d^k e^k} x_k^2 x + \color{brown}{d^k e^{k-1} f} x_k^2 y + 2\color{brown}{ d^k f^k} x_k y_k x \right) + b^{k+1} \left( \color{brown}{d^k f^k} y_k^2 y + \color{brown}{d^k ef^{k-1}} y_k^2 x + 2 \color{brown}{d^k e^k} x_k y_k y \right)$
Divide both sides by $d^k$ to result in
$$a^{k+1} \underbrace{( e^k x_k^2 x + e^{k-1} f x_k^2 y + 2 f^k x_k y_k x)}_{\huge{x_{k+1}}} + b^{k+1} \underbrace{\left( f^k y_k^2 y + ef^{k-1} y_k^2 x + 2 e^k x_k y_k y \right)}_{\huge{y_{k+1}}} = d^{k+1}.$$
Hence, we have found integers $x_{k+1}, \, y_{k+1}$ such that $a^{k+1} x_{k+1} + b^{k+1} y_{k+1} = d^{k+1}$
$ \iff \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})$.
In all , we get that $\gcd(a^{k+1}, b^{k+1}) = \gcd(a,b)^{k+1}.$
Hence, by the principle of mathematical induction $\gcd(a^n,b^n) = \gcd(a,b)^n, \,\, \forall n \in \mathbb{N}.$
I add more details to Andre Nicolas's answer.
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
$(ax+by)^{2n-1} = \sum_{0 \le k \le 2n - 1}\dbinom{2n - 1}{k}(ax)^k(by)^{(2n - 1)-k}$
$= \color{blue}{\sum_{0 \le k \le n - 1} \dbinom{2n - 1}{k}(ax)^k(by)^{(2n - 1)-k}}+ \color{brown}{\sum_{n \le k \le 2n - 1} \dbinom{2n - 1}{k}(ax)^k(by)^{(2n - 1)-k}}$
There are $2n$ terms in the expansion. Note — this part is opposite to Andre Nicolas's answer.
The first $n$ — the blue terms — are divisible by $b^n$.
The last $n$ terms — the brown terms — are divisible by $a^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$.
I expose more steps in NovaDenizen's answer.
Master plan for proof — You just need to show that $\gcd(\alpha,\beta) = 1 \implies \gcd(\alpha^n,\beta) = 1$.
Why? After you prove that, the key is $\begin{align} 1 = \gcd(a^n,b) & = \gcd(b,a^n) \\ & {\huge{\color{cyan}{=}}} \gcd(b^n,a^n) = \gcd(a^n,b^n) \end{align}$.
The cyan equality hails from the master plan by cause of substituting $\alpha = b$ and $\beta = a^n$.
From Bézout's identity, $\gcd(a,b) = 1 \iff \exists \; x,y: ax + by = 1$
Given $\gcd(a,b) = 1$, there exist integers $x$ and $y$ such that $ax + by = 1$. So $(ax + by)^n = 1$.
Expand $(ax + by)^n$ by reason of Binomial Theorem —
$(ax+by)^{n} = \sum_{0 \le k \le n}\dbinom{n }{k}(ax)^k(by)^{n -k}$ $= \color{brown}{\dbinom{n }{n}(ax)^n(by)^{n - n}} + \color{blue}{\sum_{0 \le k \le n - 1} \dbinom{n}{k}(ax)^k(by)^{n -k}}$
Therefore $(ax + by)^n = \color{brown}{a^nx^n}$ + the blue bunch of other terms that are each divisible by $b$.
So there exists $y'$ such that $\color{brown}{a^nx^n} + \color{blue}{by'} = 1$.
So by reason of all those equalities in the master plan, $\gcd(a^n,b) = 1$.
Lemma. If $(x,y)=1$ then $(xz,y)=(z,y)$.
Proof. See here: Prove that if $\gcd( a, b ) = 1$ then $\gcd( ac, b ) = \gcd( c, b ) $
In words: we can add a factor to one side of the gcd provided it is coprime to the other side. Carefully adjoining factors $a$ and $b$ should allow to eventually get $(a^n,b^n)=1$ from $(a,b)=1$.
Here comes a proof of the following more general fact:
Theorem. If $(a,b)=1$ then $(a^m,b^n)=1$ for all $m,n>0$.
The adjoining of factors $a$ and $b$ is cleanest when done with induction.
Proof. By induction on $m+n$. True for $m+n=2$. $\checkmark$
Induction step: Let $m+n>2$ and suppose wlog $m>1$. Let $x=a$, $y=b^n$, $z=a^{m-1}$. By the induction hypothesis, $(x,y)=1$, and the lemma gives
$$(\underset{xz}{a^m},\underset y{b^n})=(\underset xa\cdot \underset z{a^{m-1}},\underset y{b^n})=(\underset z{a^{m-1}},\underset y{b^n})$$
which is $1$ by the induction hypothesis, as $m-1+n<m+n$. $\square$
