Mathematics Homework Solutions
#111793
Remainders of Euclidean Algorithms
Let b = r_0, r_1, r_2, ... be the successive remainders in the Euclidean Algorithm applied to a and b. Show that every 2 steps reduces the remainder by at least one half. In other words, verify that r_{i+2} < (1/2)r_{i}, for every i = 0,1,2,.... Conclude that the Euclidean algorithm terminates in at most 2log_{2}(b) steps, where log_2 is the logarithm to the base 2.
In particular, show that the number of steps is at most seven times the number of digits of b. [Hint: What is the value of log_{2}(10)].
Remainders of a Euclidean algorithm are investigated. The response received a rating of "5/5" from the student who originally posted the question.
What is this?
By OTA - Overall OTA Rating
Fabio Mainardi, PhD - 4.9/5
Purchase Cost Now
$2.19 CAD (was ~$15.96)
Included in Download
- Plain text response
- Attached file(s):
- Euclid.doc
Why you can trust BrainMass.com
- Your Information is Secure
- Best Online Academic Help Service
- Students find real academic Success
- Euclidean Ring: Prove that a necessary and sufficient condition that the element 'a' in the Euclidean ring is a unit is that d(a) = d(1). Or, Prove that the element 'a' in the Euclidean ring is a unit if and only if d(a) = d(1). - Prove that a necessary and sufficient condition that the element 'a' in the Euclidean ring is a unit is that d(a) = d(1). Or, Prove that the element 'a' in the Euclidean ring is a unit if and ...
- Ring Theory : Euclidean Rings - Prove that in a Euclidean ring ( a , b ) can be found as follows b = q0 a + r1 where d ( r1) < d (a ) ...
- Euclidean and non-euclidean geometry - Euclidean and non-euclidean geometry. See attached file for full problem description.
- Ring Theory : Euclidean Ring: In a Euclidean ring, prove that any two greatest common divisors of a and b are associates. - In a Euclidean ring, prove that any two greatest common divisors of a and b are associates.
- Euclidean Domains and Principal Integral Domains - Determine whether the ring R=Z[(1+√-5)/2] is a Euclidean Domain. And whether the ring R=Z[(1+√-5)/2] is a Principal Ideal Domain See attached file for full problem description.
