1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Let d = gcd(a, b), prove kd = gcd(ka, kb)

  1. Apr 7, 2012 #1
    I feel like I am convoluting this problem. Any help is appreciated! Also, I'm not sure how to rewrite the first part to make it more readable. Any help here is appreciated, too.

    1. The problem statement, all variables and given/known data
    Let a and b be integers and let d = gcd(a, b). If k is a positive integer, prove that
    kd = gcd(ka, kb).

    HINT: Set d1 = gcd(ka, kb). Argue that kd is a common divisor of ka and kb, so kd
    divides d1 . Next, apply Theorem 5 to argue that d1 divides kd.

    2. Relevant theorems
    Theorem 4: Let a and b be integers and suppose d = gcd(a, b). Then there exist integers
    m and n such that d = ma + nb.

    Theorem 5: Let a, and b be integers, where a and b are not both zero. Then gcd(a, b)
    exists so let d = gcd(a, b). For an integer c there exist integers m and n such that
    c = ma + nb if and only if c is a multiple of d.

    3. The attempt at a solution
    Proof. Let [itex]a, b, d \in \mathbb{Z}[/itex] such that [itex]d=\mathrm{gcd}(a,b)[/itex]. Let [itex]k[/itex] be a positive integer and set [itex]d_1=\mathrm{gcd}(ka, kb)=kma+knb \implies d_1=k(ma+nb)[/itex]. Because [itex]d|a[/itex] and [itex]d|b[/itex], [itex]d_1=kd(\frac{ma}{d}+\frac{nb}{d})[/itex]. Therefore, [itex]kd|d_1[/itex]. Using Theorem 5, because [itex]kd[/itex] divides [itex]d_1[/itex], [itex]d_1[/itex] is a multiple of [itex]d[/itex] and therefore [itex]d_1=ra+sb[/itex]

    From here, I'm not sure where to go. I don't know how to introduce k back into [itex]d_1=ra+bs[/itex]
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted