Understanding the Euclidean Algorithm: Solving for Relatively Prime Numbers

[Arden1528]

I am little confused on this issue, actually the thing that is confusing me is my book.
We all know the formula m=qn+r and 0<r<n
In the formula we go until r=0, then you will know relativley prime.
When given a problem, for example, (862,347) we have m=862 while n=347
so we have the equation 862=347(q)+r. Then we solve till r=0
For some reason in my book it gives the example (1251,1976)
the way they set it up is 1976=1251(1)+725 according to this
m=1976 and n=1251, isn't that backwards? I thought it went (m,n), with that in mind shouldn't it be 1251=1976(1)+r?
Or do you place the numbers accordingly so 0<r?

 

[HallsofIvy]

In the question of whether two numbers are relatively prime, the order of the two numbers is not important.

In determining whether or not 1251 and 1976 are relatively prime, you text is looking for 1976= 1251(q)+ r because 1251< 1976.

Yes, r has to be positive: that's part of the definition (in writing b= aq+ r you want 0<= r< a). You don't want to look at
1251= 1976q+ r because that has the obvious solution q= 0, r= 1251 which doesn't help.

 

[M98Ranger]

The Euclidean Algorithm is a mathematical method used to find the greatest common divisor (GCD) of two numbers. It is based on the fact that the GCD of two numbers is the largest number that divides both of them without leaving a remainder. The algorithm involves repeatedly dividing the larger number by the smaller number until the remainder is 0.

In your confusion, it seems like you are mixing up the order of the numbers in the equation. The equation m = qn + r is used to represent the division process, where m is the larger number, n is the smaller number, q is the quotient, and r is the remainder. The numbers m and n are fixed, while q and r change as the division is repeated.

In the example (862, 347), m = 862 and n = 347. This means that 862 is the larger number and 347 is the smaller number. When we divide 862 by 347, we get a quotient of 2 and a remainder of 168. This can be represented as 862 = 347(2) + 168. We then continue the process by dividing 347 by 168, which gives a quotient of 2 and a remainder of 11. This can be represented as 347 = 168(2) + 11. We continue this process until we reach a remainder of 0, which means that 11 is the GCD of 862 and 347.

In the example (1251, 1976), m = 1976 and n = 1251. This means that 1976 is the larger number and 1251 is the smaller number. When we divide 1976 by 1251, we get a quotient of 1 and a remainder of 725. This can be represented as 1976 = 1251(1) + 725. We then continue the process by dividing 1251 by 725, which gives a quotient of 1 and a remainder of 526. This can be represented as 1251 = 725(1) + 526. We continue this process until we reach a remainder of 0, which means that 526 is the GCD of 1251 and 1976.

In summary, the Euclidean Algorithm works for any two numbers, regardless of their order. The key is to correctly represent the division process using the equation m = qn + r. I hope