PLEASE SHOW DETAIL WILL RATE LIFESAVER if done so!! Use Proposition and the meth
ID: 2943770 • Letter: P
Question
PLEASE SHOW DETAIL WILL RATE LIFESAVER if done so!!
Use Proposition and the method talked through in class to find ged(765, 25), ged(196, 56), and god(34, 23). The procedure we worked out for finding these ged's is a version of what is called the Euclidian algorithm. Explain how we are using Theorem 31 and Proposition 45 when applying our procedure. Two key questions we want to be sure we understand: When does this procedure "stop"? Do we know that it must always stop (or did we just get lucky when working with our small set of examples)? In your explanation of how and why the procedure always stops, is it important to know what ged(a.0) is, for any nonzero integer a? Why? (See also "Euclidean algorithm" on Wikipedia for a simpler version. How is the procedure describe*! there simpler? Can you explain why the version on Wikipedia also always "stops"?)Explanation / Answer
a) gcd(765,25)
= gcd(765-25,25) = gcd(740,25)
= gcd(740-25,25) = gcd(715,25)
.
.
= gcd(15,25)
= gcd(15,25-15) = gcd(15,10)
= gcd(15-10,10) = gcd(5,10)
= gcd(5,10-5) = gcd(5,5)
So, gcd(765,25) = 5
b) gcd(196,56)
= gcd(196-56,56) = gcd(140,56)
.
.
= gcd(28,56)
= gcd(28,56-28) = gcd(28,28)
So, gcd(196,56) = 28
c) gcd(34,23)
= gcd(34-23,23) = gcd(11,23)
= gcd(11,23-11) = gcd((11,12)
= gcd(11,12-11) = gcd(11,1)
.
= gcd(1,1)
So, gcd(34,23) is 1