MAT 312/AMS 351 - Applied Algebra -- Spring 2005

Problems marked with an asterisk (*) are for extra credit.

Section 1.4: Ex 3, 4, 5, 9
Find all integral solutions of the equation:
1. 60x+18y=97
2. 21x+14y=147
How many ways can change be made for one dollar, using each of the following coins:
1. dimes and quarters
2. nickels, dimes and quarters

Section 1.6: Ex 9^*, 12, 13
Find the primes p and q if pq=4,386,607 and φ(pq)=4,382,136. Explain the method you have used.
Are there any numbers n such that φ(n)=14? Explain!
Find the remainder at division of 3¹⁰⁰⁰ by 35.
^*Suppose that a cryptanalyst discovers a message P that is not relatively prime to the enciphering modulus n=pq used in a RSA cipher. Show that the cryptanalyst can actually factor n.

^* Compute φ(n) for the following values of n= 10!, 20! and 100!. Explain the method you have used.
Section 2.1: Ex 1, 3, 4, 6
Section 2.2: Ex 1, 2, 5, 9, 10
Section 2.3: Ex 1

Section 2.3: 2 (only c, e, d, f), 4, 6 (only the Hasse diagram), 7
Let X= {1, 2, 3, 4, 5}. For each part, define a relation R on the set X so that R is
1. reflexive and symmetric, but not transitive.
2. symmetric and transitive, but not reflexive.
3. reflexive, symmetric, transitive, and weakly antisymmetric.
Let M be the relation on the real numbers R defined as follows: for all x, y ∈R, xMy if and only if
x-y
is an integer.
1. Prove that M is an equivalence relation.
2. Describe the equivalence classes of M.
Section 4.1: Ex 1 (only the products π₁π₂, π₂π₃ and π₂π₁), 2, 3

Section 4.1: 4, 5, 6
Write the permutations π₁, π₂ and π₄ in the exercise 1 of section 4.1 as a product of disjoint cycles.
Section 4.2: 1, 2, 3, 5, 6, 7

Section 4.3: 2, 3, 5, 6, 8
Describe the group of symmetries of a regular hexagon. How many symmetries does it have? What do they look like? What relationships are there among them?
Section 4.4: 1, 3 ((i), (iii) and (v) only).

MAT 312/AMS 351 Applied Algebra