Share
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.

5.

6.

7.

8.

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

STATE REASON WHY?

#### 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.

\$2.19