I am little confused on this issue, actually the thing that is confusing me is my book.(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums - The Fusion of Science and Community**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Euclidean algorithm

Loading...

Similar Threads for Euclidean algorithm | Date |
---|---|

Euclidean Algorithm Gaussian Integers | Aug 6, 2014 |

Extended Euclidean Algorithm | May 17, 2011 |

Efficiency and the Euclidean Algorithm | Feb 10, 2011 |

Euclidean algorithm Proof | Dec 21, 2009 |

Euclidean algorithm congruences | May 7, 2009 |

**Physics Forums - The Fusion of Science and Community**