MAS1003 Discrete Mathematics: Problem sheet 3

Please hand in solutions to your tutor no later than Monday 22nd November

l

1. [3] For m a positive integer and a any integer, the least non-negative residue of a (mod m) is the unique integer b with a ≡ b (mod m) and 0 ≤ b < m − 1. (Alternatively the least non-negative residue of a (mod m) is the remainder left after dividing a by m.) For instance the least non-negative residue of 100 (mod 7) is 2, and the least non-negative residue of −100 (mod 11) is 10.

Find the least non-negative residue of 2^{k} (mod 5) for each integer k with 1 ≤ k ≤ 10. Hence explain how to find the least non-negative residue of 2^{k} (mod 5) for an arbitrary integer k. Use a similar method to find the least non-negative residues of 2^{77} (mod 17) and 5^{101} (mod 13).

2. [2] Devise tests for divisibility by (i) 4, (ii) 5 and (iii) 6. If you feel very brave [4] think about divisibility by 7.

3. [3] Show that an r-digit number A with digits a_{r−1}, a_{r−2}, …, a_{1}, a_{0} is divisible by 11 if and only if a_{0} −a_{1} +a_{2} −⋯+(−1)^{r−1}a_{r−1} is divisible by 11.

4. [2] Write down the multiplication tables for Z_{6}, Z_{7} and Z_{8}. Identify the invertible elements of each of Z_{6}, Z_{7} and Z_{8}. (Recall that Z_{n} = {0, 1, 2, …, n− 1} is the set of integers modulo n, with operations addition modulo n, subtraction modulo n and multiplication modulo n.)

5. [2] Let m be a positive integer. Show that if a and b are invertible in Z_{m}, then ab is invertible in Z_{m}.

6. [4] Let m and n be positive integers. Show that if m is invertible in Z_{n}, then n is invertible in Z_{m}.

7. [2] Fill the gaps in the following Latin squares:

(i) \begin{matrix}A & B & C & D \\ B & A \\ C & & B \\ D \end{matrix} , (ii) \begin{matrix}A & B & C & D \\ B & C \\ C \\ D \end{matrix} , (iii) \begin{matrix}A & B & C & D & E \\ B & C & A & E & D \\ C & E & D & B & A \\ D \\ E \end{matrix} .

8. [3] The two Latin squares of order 4

\begin{matrix}A & B & C & D \\ B & A & D & C \\ C & D & A & B \\ D & C & B & A \end{matrix} and \begin{matrix}A & B & C & D \\ C & D & A & B \\ D & C & B & A \\ B & A & D & C \end{matrix}

are orthogonal. Find a third Latin square orthogonal to both of these.

9. [3] Recall the theorem given in lectures on the construction of orthogonal Latin squares. Show that it implies that for each odd n, there is a pair of orthogonal Latin squares of order n. Why does this theorem not imply the existence of orthogonal Latin squares of order 6?

10. [3] Find four Latin squares of order 5, with the property that each pair of them is orthogonal.

11. [3] In MAPLE the mod command calculates the least non-negative residue. For instance the command

                          100 mod 7;

produces the result 2 as 100 ≡ 2 (mod 7) and 0 ≤ 2 < 7. In this question we shall investigate the least non-negative residue of a^{n−1} modulo n for various values of a and n. But care is needed. Try the MAPLE command

                 2^4294967296 mod 4294967297;

You find it produces an error message. This is because it attempts to calculate 2^{4294967297} first, a number of 1292913987 digits, then reduces it modulo 4294967297. This number is too big for MAPLE to store. It would be better if MAPLE kept reducing the intermediate steps in computing 2^{4294967296} modulo 4294967297 at each stage; luckily the alternative MAPLE syntax

                 2&^4294967297 mod 4294967297;

does this. This version works!

Using MAPLE calculate the least non-negative residue of a^{n−1} modulo n in each of the following cases:

(i) a = 2, n = 97; (ii) a = 3, n = 97; (iii) a = 2, n = 255; (iv) a = 2, n = 257;

(v) a = 3, n = 257; (vi) a = 2, n = 341; (vii) a = 3, n = 341; (viii) a = 3, n = 407; (ix) a = 2, n = 561; (x) a = 3, n = 561; (xi) a = 2, n = 1001; (xii) a = 2, n = 1007; (xiii) a = 2, n = 1009; (xiv) a = 3, n = 1009; (xv) a = 5, n = 1009; (xvi) a = 2, n = 1729; (xvii) a = 3, n = 1729; (xviii) a = 2, n = 1997; (xix) a = 2, n = 9605797; (xx) a = 3, n = 4294967297.

Are there any patterns in the data? You may like to test any conjectures you make by inventing suitable examples of your own.

12. [3] Using MAPLE calculate the least non-negative residue of (n−1)! (mod n) for n up to 25 (or if you feel energetic you can go further). Is there any pattern to the observed data? How much of this pattern can you explain?

RJC 3/11/1999