Results 1 to 4 of 4

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

  1. #1
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,845
    Thanks
    320
    Awards
    1
    Quote Originally Posted by tttcomrader View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2
    I'm not sure if I can do that, because this problem comes before the chapter involving prime.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,845
    Thanks
    320
    Awards
    1
    Quote Originally Posted by tttcomrader View Post
    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
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum