# Math Help - GCD(a^n,b^n)

1. ## GCD(a^n,b^n)

Prove that if gcd(a,b)=1, then gcd(a^n,b^n)=1.

proof. Let $S = \{ n \in N : a^nv + b^nw = 1 , v,w \in Z \}$

1 is in S since ax + by = 1, let k be in S, now I have trouble trying to prove k+1 is in S.

Prove that if gcd(a,b)=1, then gcd(a^n,b^n)=1.

proof. Let $S = \{ n \in N : a^nv + b^nw = 1 , v,w \in Z \}$

1 is in S since ax + by = 1, let k be in S, now I have trouble trying to prove k+1 is in S.
Are you allowed to use a prime factorization argument? It looks pretty easy using that.

-Dan

3. I'm not sure if I can do that, because this problem comes before the chapter involving prime.

I'm not sure if I can do that, because this problem comes before the chapter involving prime.
A sketch would go something like this:
Call P(a) be the prime factorization of a. So any element of P(a) appears n more times in P(a^n). (The point being that taking a^n introduces no new prime factors to the factorization.) Now, if GCD(a, b) = 1 then no element of P(b) is the same as any as any element of P(a). Thus no element of P(b^n) is the same as any element of P(a^n). Thus GCD(a^n, b^n) = 1.

-Dan