1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Euclid's Algorithm

  1. Mar 31, 2006 #1
    I can do it, but can't understand how it works. Is there a straightforward expalnation in terms of
    \ \mathbb{Z}_{n}
    the set of remainers in modulo n? Could someone try to explain, pls.
  2. jcsd
  3. Mar 31, 2006 #2


    User Avatar
    Science Advisor

    It's not clear to me what you want. "Explaining" Euclid's algorithm in terms of Zn seem much to complicated to me. Euclid certainly didn't know anything about Zn! Euclids algorithm asserts that if m and n are two positive integers, with greatest common divisor p, there exist two integers, a and b, such that am+ bn= p. The "algorithm" itself is a way of finding a and b by successive divisions. For example, if m= 18 and b= 8, then the greatest common divisor is 2. 8 divides into 18 twice, with remainder 2, 2 divides into 8 4 times with remainder 0, showing that 18- 2(8)= 2: a= 1, b= -2.
    Second example, the greatest common divisor of 31 and 7 is 1: 7 divides into 31 4 times with remainder 3: 31= (4)(7)+ 3 or 31- 4(7)= 3. 3 divides into 7 twice with remainder 1: 1= 7- 2(3)= 7- 2(31- 4(7))= 8(7)- 2(31).
    a= 8, b= -31.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook