I understand that the algorithm proceeds as follows:
k=0, a=q₀b + r₀
k=1, b=q₁r₀ + r₁
k=2, r₀=q₂r₁ + r₂
k=3, r₁=q₃r₂ + r₃
The text I have is using a=75, b=38 as its example. In German this is represented as ggT(75, 38). They then write (I'm translating):
Quote:
We set r₀ = 75 (the larger of the two numbers) and r₁ = 38 and divide:
75 = 1 * 38 + 37, (thus q₁ = 1, r₂ = 37)
38 = 1 * 37 + 1, (thus q₂ = 1, r₃ = 1)
37 = 37 * 1 + 0
The problem is with "thus q₁ = 1." This means to me: r₀ = 75, r₁ = 38, q₁ = 1, r₂ = 37. At k=2, the equation should be: r₀=q₂r₁ + r₂. But at k=2 their equation is r₀=q₁r₁ + r₂.
I don't understand the discrepancy.
Login
FAQ
Search
