Explore BrainMass

Euclidean Algorithm

Please see attached file for full problem description.

1. Use the euclidean algorithm to find gcd(729,75), then rerun the algorithm to find integers m and n such that gcd(729,75) = 729m + 75n.

2. Find the prime factorizations of (482,1687). Thus find the gcd and the lcm of the pair. Also find the gcd by Euclid's algorithm and then find the lcm from lcm(x,y)=xy/gcd(x,y).

3. Prove the following statment by induction. Use the headings Base, Inductive step, and By induction.
n3 - n is divisible by 6, for every natural number n > 1.

4. Show that the group (Z/16Z)× has 8 elements, and that each element has order 1, 2 or 4. Use the following definition of the order of an element in a finite group : The order of an element g in a finite group G is the least positive integer n such that gn=1.





9. In each of the following exercises, set S and a binary operation ∗ on S will be specified. In each case, determine whether ∗ is associative, whether ∗ has an identity element and, if the latter is the case, whether each element of S has an inverse (with regard to ∗), i.e. whether S is a group: (State reason for each)



Solution Summary

Euclid's algorithm is investigated. The solution is detailed and well presented. The response was given a rating of "5/5" by the student who originally posted the question.