Euclidean algorithm

  • Thread starter Arden1528
  • Start date

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

Science Advisor
Homework Helper
41,711
876
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.
 

Related Threads for: Euclidean algorithm

  • Posted
Replies
1
Views
3K
  • Posted
Replies
1
Views
5K
  • Posted
Replies
4
Views
3K
Replies
2
Views
6K
Replies
6
Views
3K
  • Posted
Replies
1
Views
1K
  • Posted
Replies
2
Views
3K
  • Posted
Replies
8
Views
4K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top