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: Question on the Euclidean Algorithm

  1. Sep 26, 2011 #1
    1. The problem statement, all variables and given/known data
    Let [itex]a,b\in\mathbb{Z}[/itex]. Suppose [itex]r_{0}=a[/itex] and [itex]r_{1}=b[/itex]. By the algorithm, [itex]r_{i}=0[/itex] for some [itex]i\geq 2[/itex] is the first remainder that terminates. Show that [itex]r_{i-1}=\gcd(a,b)[/itex].

    2. Relevant equations

    3. The attempt at a solution
    I've shown that [itex]c|r_{i-1}[/itex], and I know that I should show that [itex]r_{i-1}|a[/itex] and [itex]r_{i-1}|b[/itex]. I just don't know how to show both the latter. I don't know where to continue.

    I don't want full solutions just given to me (obviously), just some insight :)

  2. jcsd
  3. Sep 27, 2011 #2
    Maybe prove first that if a certain c divides [itex]r_k[/itex] and [itex]r_{k+1}[/itex], then it divides [itex]r_{k-1}[/itex].
    Then apply this result for c=gcd(a,b).
  4. Sep 27, 2011 #3
    Nevermind, I got it without having to break it down into cases!

    Note, [itex]\gcd(a,b)=\gcd(a+mb,b)[/itex] for any [itex]m\in\mathbb{Z}[/itex].

    Define [itex]P(n): \gcd(a_{n-1},a_{n})=\gcd(a_{n},a_{n+1})[/itex]. Let [itex]n_{0}=1[/itex] be our base case. Since [itex]a_{0}=ma_{1}+a_{2}[/itex] by the division algorithm, we have [itex]\gcd(a_{0},a_{1})=\gcd(ma_{1}+a_{2})=\gcd(ma_{1}-ma_{1}+a_{2},a_{1})=\gcd(a_{2},a_{1})=\gcd(a_{1},a_{2})[/itex], thus [itex]P(n_{0})[/itex] is true.

    Now let [itex]n\geq 1[/itex] such that [itex]P(n)[/itex] is true. Then we have [itex]\gcd(a_{n-1},a_{n})=\gcd(a_{n},a_{n+1})=\gcd(ma_{n+1}+a_{n+2},a_{n+1})=\gcd(ma_{n+1}-ma_{n+1}+a_{n+2},a_{n+1})=\gcd(a_{n+2},a_{n+1})=\gcd(a_{n+1},a_{n+2})[/itex]. Hence, [itex]\gcd(a_{n},a_{n+1})=\gcd(a_{n+1},a_{n+2})[/itex], thus for all [itex]n\geq 1[/itex], [itex]P(n)\implies P(n+1)[/itex]. Hence, by the principle of Mathematical Induction: [itex]\forall n\geq 1,P(n)[/itex].

    Since we know that for some [itex]i[/itex], [itex]a_{i}=0[/itex], it follows that: [tex]\gcd(a,b)=\gcd(a_{0},a_{1})=\cdots =\gcd(a_{i-1},a_{i})=\gcd(a_{i-1},0)=a_{i-1}.[/tex] Therefore, [itex]\gcd(a,b)=a_{i-1}[/itex], as required.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook