2
$\begingroup$

Let $a,b$ be natural numbers. Show that $gcd(a^n,b^n)$ = ($gcd(a,b)^n)$ for any integer $n$.

How I started was first proof by contradiction, and then tried to do an inductive proof when that didn't work, but neither of them worked out for me. I think I'm confused as to the notation I should use. Hmmm.

I'm not looking for someone to answer the question fully, I just need a nudge in the right direction.

EDIT:

Okay, after the super helpful hints, here is what I have for the proof:

Suppose $gcd(a,b)$ = $c$ for some integer $c$

Then $c$ = ${p_1}^{min\{a_1, b_1\}\ }$... ${p_k}^{min\{a_k, b_k\}}$ for some positive integer $k$

So $gcd(a^n, b^n)$ = ${p_1}^{min\{na_1, nb_1\}\ }$... ${p_k}^{min\{na_k, nb_k\}}$ = ${p_1}^{nmin\{a_1, b_1\}\ }$... ${p_k}^{nmin\{a_k, b_k\}}$

Now we see ($gcd(a, b)^n$) = $(c)^n$ = (${p_1}^{min\{a_1, b_1\}\ }$... ${p_k}^{min\{a_k, b_k\}})^n$ = ${p_1}^{nmin\{a_1, b_1\}\ }$... ${p_k}^{nmin\{a_k, b_k\}}$

Therefore, $gcd(a^n, b^n)$ = $(gcd(a, b)^n)$ for all positive integers $n$

Is this too short? Should I show the prime factorization of $a$ and $b$ before showing the prime factorization of $gcd(a, b)$ ?

$\endgroup$
  • $\begingroup$ Hint: go prime by prime. Suppose $p^k$ is the largest power of p that divides gcd(a,b). Then $p^{nk}$ is the largest power of p dividing the right hand of your conjectured equation. Could the power of p be greater on the left? Could it be less? $\endgroup$ – lulu Jul 8 '15 at 21:52
  • $\begingroup$ See this answer for a few proofs of this GCD Freshman's Dream. $\endgroup$ – Gone Jul 8 '15 at 22:16
1
$\begingroup$

If you're just looking for a nudge in the right direction try looking at the prime factorization of $a$ and $b$ vs $a^n$ and $b^n$. (You could also try thinking of $a$ as $gcd(a,b)*p_1p_2....$ and $b$ as $gcd(a,b)*q_1q_2....$ where $p_i$ and $q_j$ are all prime). Further "nudge": Could it possibly be the case that $p_i=q_j$ for any $i,j$ pair?

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

A start: Let $d=\gcd(a,b)$, and let $a=da_1$ and $b=db_1$. We want to show that $\gcd(a^n,b^n)=d^n$, or equivalently that $\gcd(a_1^n,b_1^n)=1$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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