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 ∗ 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)
STATE REASON WHY?
