• Support PF! Buy your school textbooks, materials and every day products Here!

Question on the Euclidean Algorithm

  • Thread starter Kindayr
  • Start date
  • #1
161
0

Homework Statement


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].


Homework Equations





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 :)

Thanks!
 

Answers and Replies

  • #2
22,097
3,282
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).
 
  • #3
161
0
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.
 

Related Threads on Question on the Euclidean Algorithm

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
335
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
6
Views
1K
Replies
5
Views
1K
Replies
0
Views
3K
Replies
10
Views
1K
Replies
5
Views
2K
Top