Algebraic Structures Sheet 2

Please hand in solutions to Pure Tutors no later than the morning of 17th February 1997 Material in square brackets [ ] is more challenging, and can be regarded as optional

1. For each set X, and relation R on X determine whether it is an equivalence relation. If so, describe its equivalence classes; if not, say which of the three conditions (reflexivity, symmetry, transitivity) fail. Justify your answers.

(i) Let X = ℚ − {0}. Define R by aRb if a/b is a power of 2. (Here powers of 2 include positive, zero and negative powers, e.g., 2^{3} = 8, 2^{0} = 1 and 2^{−4} = 1/16 etc.) (ii) Let X = ℝ. Define R by xRy if xy > 0. (iii) Let X = ℝ. Define R by xRy if xy ≥ 0. (iv) Let X = ℂ − \{0\}. Define R by zRw if z\overline{w} is a positive real number.

(v) Let X = ℤ, and choose a natural number n. Define R by aRb if a − b is a multiple of n.

2. Let X = {1, 2, 3, 4, 5}. Draw the “directed graphs” associated to the following relations R and S on X: aRb if a is divisible by b, and aSb if a − b is odd. Choose at least one other relation on X, and draw its directed graph.

If a relation is reflexive, what can one say about its directed graph? What if it is symmetric? transitive?

3. Let f : A → B be a function. Define a relation R on A by xRy if f(x) = f(y). Show that R is an equivalence relation.

4. (i) Define the relation R on ℕ × ℕ by (a, b)R(m, n) if a + n = b + m. Show that R is an equivalence relation, and describe its equivalence classes. (ii) Define the relation S on ℤ × ℕ by (a, b)S(m, n) if an = bm. Show that S is an equivalence relation, and describe its equivalence classes.

5. How many equivalence relations are there on the set {1, 2, 3, 4}. [If you want a challenge do the same for {1, 2, 3, 4, 5} etc.]

6. Criticize the following argument:

   Let R be a symmetric and transitive relation on a set X.  Then
R must be reflexive, for if aRb, then bRa by symmetry, and then,
since aRb and bRa, transitivity gives aRa.

7. Apply the Sieve of Eratosthenes to calculate all primes below 100. [If you like go further!]

8. Note that 3, 5 and 7 are three successive odd numbers, all of which are prime. Are there any other such triples?

9. If n is a composite number, show that it has a prime factor p with p ≤ \sqrt{n}.

10. Let n be a number with decimal digits a_{k−1}a_{k−2} ⋯ a_{1}a_{0}.

(i) Show that n is divisible by 8 if and only if the number with decimal digits a_{2}a_{1}a_{0} is also divisible by 8. (ii) Show that n is divisible by 9 if and only if the sum of its digits is also divisible by 9. (iii) Show that n is divisible by 11 if and only if a_{0}−a_{1}+a_{2}−⋯+(−1)^{k−1}a_{k−1} is also divisible by 11.

11. (a) Show that all of the numbers 2^{4} − 1, 2^{6} − 1, 2^{8} − 1, 2^{10} − 1 are composite. Can you generalize?

(b) Show that all of the numbers 2^{6} −1, 2^{9} −1, 2^{12} −1, 2^{15} −1 are composite. Can you generalize?

(c) Show that all of the numbers 2^{3} + 1, 2^{5} + 1, 2^{7} + 1, 2^{9} + 1 are composite. Can you generalize?

(d) Show that all of the numbers 2^{6} +1, 2^{10} +1, 2^{14} +1, 2^{18} +1 are composite. Can you generalize?

(e) [Show that n^{4} + 4 is composite for all integers n ≥ 2. Also show that n^{4} + 4^{n} is composite for all integers n ≥ 2.]

12. Describe how the last digit of a natural number n determines that of 2n. Hence find a way of determining the last digit of 2^{k} for each k ∈ ℕ. Repeat replacing 2 by 7. What are the last digits of 2^{1997} and 7^{1997}?

The largest known prime number is 2^{1398269} − 1 (due to Joel Armengaud, 13th November 1996). What is its last digit? How many digits has it, and what is its first? (Hint: the log key on your calculator will be useful.)

RJC 31/1/97