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

proof. Let $\displaystyle 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.

Results 1 to 4 of 4

- Jan 23rd 2008, 12:58 PM #1

- Joined
- Mar 2006
- Posts
- 705
- Thanks
- 2

- Jan 23rd 2008, 02:34 PM #2

- Jan 30th 2008, 06:29 AM #3

- Joined
- Mar 2006
- Posts
- 705
- Thanks
- 2

- Jan 30th 2008, 06:57 PM #4
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