Please see attached file for full problem description.

1. Use the euclideanalgorithm 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)

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.

a) When we write a=mb+r in the Euclidean algorithm, call the number ma multiplier. ... a) Consider these examples of the Euclidean algorithm with large integers. ...

... 1,2,...,n−1} such that ad ≡ 1 (mod ϕ(n)). This number d is the "decryption key" and can be constructed by going backwards in the Euclid's algorithm. ...

... adversary can mount the following chosen-message attack to obtain the signature on m. Apply the extended Euclidean algorithm (Algorithm 2.107) to n and m = R(m ...

... 2 Euclidean Algorithm The Euclidean Algorithm (EA for short) is the key to understanding the ex- istence of multiplicative inverses mod n (and many other things ...

... Cartesian coordinates (ie, xPos, yPos), the "NearestNeighbor" method algorithm calculates the ... client node cartesian coordinates, all based on Euclidean distance ...

... A recursive program to calculate the Greatest Common Divisor of two integers using the Euclidean Method. The algorithm in non-recursive form is as follows ...

... with predicate "R1.a > 2 and R1.a = R2.b", what join algorithm will you ... space partitioning is the process of dividing a space (usually a Euclidean space) into ...

... But this process is precisely Euclid's algorithm for computing the GCD of r and s. So we have that 2^[GCD(r,s)] = 1. Then, because d is the smallest exponent ...

... m(x)s(x) for some s(x) from F[x]. Since q(g)=0, by above we have deg(q) is bigger or equal deg(m). Apply Euclidean algorithm to divide q(x) by m(x). We will ...