Algebraic Structures Sheet 3

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

1. Complete the proof of the division algorithm by showing that if a ∈ ℤ and n ∈ ℕ with a < 0, then there are q ∈ ℤ and r ∈ ℤ with a = qn + r and 0 ≤ r < n.

(Hint: there are at least two possible approaches: either use “descending induction”, or deduce such an expression for a from one for −a.)

2. For each natural number n, let d(n) denote the number of positive integer factors of n. (For instance d(10) = 4 since the positive integers which divide 10 are 1, 2, 5 and 10.) Calculate d(n) for all n up to 20. For which of these n is d(n) odd? In general, state and prove a criterion on n for when d(n) is odd.

3. Use the Euclidean algorithm to find the gcd g of each of the following pairs of integers (a, b). In each case find integers r and s with g = ra + sb:

(i) a = 17, b = 10; (ii) a = 36, b = 102; (iii) a = 333, b = 717; (iv) a = 280, b = 1001; (v) a = 610, b = 987.

4. The Fibonacci numbers (F_{n}) are defined by F_{1} = 1, F_{2} = 1 and F_{n} = F_{n−1} + F_{n−2} for each n ≥ 3. (That is each Fibonacci number from F_{3} onwards is the sum of the previous two.) Compute F_{n} for 1 ≤ n ≤ 20. Show that the gcd of F_{n} and F_{n+1} is 1 for each n. Also find integers a and b such that 1 = aF_{n} + bF_{n+1}. (Hint: if you cannot immediately see how to do this, then calculate some examples, e.g., gcd(F_{5}, F_{6}) or gcd(F_{10}, F_{11}) and see what the pattern is.)

[If you have time investigate gcd(F_{n}, F_{n+2}), gcd(F_{n}, F_{n+3}) etc.]

5. If a, b ∈ ℤ and r, m ∈ ℕ, show that

a ≡ b (mod m)

is true if and only if

ra ≡ rb (mod rm)

is true.

6. Write down the complete addition and multiplication tables for ℤ_{7} and ℤ_{8}.

7.(a) In each of the following examples find a, b ∈ ℤ with a/m + b/n = 1/r, or show that no such numbers exist:

(i) m = 3, n = 4, r = 12;

(ii) m = 10, n = 12, r = 120;

(iii) m = 30, n = 42, r = 210.

(b) Given m, n, r ∈ ℕ find a criterion for when the equation

\frac{a}{m} + \frac{b}{n} = \frac{1}{r}

has a solution with a, b ∈ ℤ.

8. Find the general solutions of the following congruences, or show that no solution exists:

(i) 3x ≡ 17 (mod 31); (ii) 7x ≡ 13 (mod 59); (iii) 12x ≡ 33 (mod 75); (iv) 35x ≡ 44 (mod 112);

(v) 176x ≡ 209 (mod 1001).

Choose and solve three similar examples of your own.

9. Find the general solutions of each of the following sets of simultaneous congruences, or show that no solution exists:

(i)  \{ \begin{matrix}x & ≡ & 6 & (mod 7) \\ x & ≡ & 9 & (mod 15) \end{matrix}

(ii)  \{ \begin{matrix}x & ≡ & 1 & (mod 22) \\ x & ≡ & 25 & (mod 38) \end{matrix}

(iii)  \{ \begin{matrix}x & ≡ & 33 & (mod 77) \\ x & ≡ & 41 & (mod 112) \end{matrix}

(iv)  \{ \begin{matrix}x & ≡ & 51 & (mod 120) \\ x & ≡ & 159 & (mod 198) \end{matrix}

(v)  \{ \begin{matrix}2x & ≡ & 14 & (mod 35) \\ 2x & ≡ & 35 & (mod 99) \end{matrix}

(vi)  \{ \begin{matrix}3x & ≡ & 15 & (mod 42) \\ 5x & ≡ & 65 & (mod 66) \end{matrix}

(vii)  \{ \begin{matrix}x & ≡ & 3 & (mod 12) \\ x & ≡ & 24 & (mod 35) \\ x & ≡ & 23 & (mod 43) \end{matrix}

(viii)  \{ \begin{matrix}3x & ≡ & 102 & (mod 105) \\ 5x & ≡ & 95 & (mod 120) \\ 7x & ≡ & 37 & (mod 144) \end{matrix}

RJC 17/2/97