1. Not finding help here? Sign up for a free 30min 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!

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
    [tex]
    \ \mathbb{Z}_{n}
    [/tex]
    the set of remainers in modulo n? Could someone try to explain, pls.
     
  2. jcsd
  3. Mar 31, 2006 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Euclid's Algorithm
  1. Algorithm Time (Replies: 4)

  2. Division Algorithm (Replies: 3)

Loading...