Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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..

share|improve this question
4  
Suppose prime $p\mid a^n$ and $p\mid b^n$, thus $p\mid a$ and $p\mid b$, so $p\mid\gcd(a,b)$. –  Frank Science Jul 5 '12 at 3:01
1  
Induction is the way to go here! Prove by induction that $(a^n,b)=1$.Then that $(a,b^n)=1$. Profit. –  Pedro Tamaroff Jul 5 '12 at 3:01
    
Possible duplicate of math.stackexchange.com/questions/63323/… –  lhf Jul 5 '12 at 3:20
    
@lhf Not exactly a duplicate since that question specifically asks for the proof using fundamental theorem of arithmetic. –  user17762 Jul 5 '12 at 3:21
add comment

11 Answers 11

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.

share|improve this answer
    
I guess it is $p_i \ne q_j$ –  Rajesh D Jul 5 '12 at 3:25
    
@RajeshD Yes, thanks for pointing that out. –  William Jul 5 '12 at 3:26
    
+1 for giving the simple, elegant proof. –  mew Jul 5 '12 at 6:41
add comment

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$.

share|improve this answer
    
Nicely done. (+1) The extra detail to your answer added by Dwayne Pouiller brought this to my notice, and I added another Bezout proof. –  robjohn Jan 4 at 23:20
add comment

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}^+.$$

share|improve this answer
2  
This is the best answer posted. One rarely has to appeal to the sledgehammer of unique factorization. –  Potato Jul 5 '12 at 3:32
2  
@Potato Personally I like André Nicolas's one a bit more. Both answers used Bézout critically but André's argument seems cleaner due to the Binomial trick. –  Ragib Zaman Jul 5 '12 at 3:42
2  
I did not see André's! His is good as well! My point is that I see the fundamental theorem used in many places where Bézout and little ingenuity will suffice. –  Potato Jul 5 '12 at 3:44
1  
@RagibZaman Yes. Andre's answer is indeed elegant. Though if $(a,b) = d > 1$, I think you need to resort to an argument similar to mine. –  user17762 Jul 5 '12 at 4:51
    
I can't see how unique factorization can possibly be a sledgehammer when dealing with anything in number theory at any level at least at senior high school or college. Marvis's proof has the charm of dealing with it using induction yet he uses Bezout's Identity, which I guess could also be called "sledgehammer" –  DonAntonio Jul 5 '12 at 11:55
show 2 more comments

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}.$

share|improve this answer
add comment

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$.

share|improve this answer
add comment

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$.

share|improve this answer
    
I like this forward-backward type of induction. +1 for a short and elegant proof. –  barto Jan 5 at 13:11
add comment

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$.

share|improve this answer
add comment

Hint $\ $ prime $\rm\,p\:|\:a^n,b^n\:\Rightarrow\:p\:|\:a,b\:$ since prime $\rm\:p\:|\:d_1\cdots d_k\:\Rightarrow\:p\:|\:d_1\ $ or $\rm\,\ldots\,$ or $\rm \,p\:|\:d_k\,$

Alternatively, more generally, see my post here on the "freshmans dream" for gcds or ideals.

Alternatively, 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.

share|improve this answer
add comment

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$.

share|improve this answer
add comment

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$.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.