Prove that if gcd(a,b)=1, then gcd(a^n,b^n)=1.
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.
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.