8.02e Finite (modular) arithmetic: integers modulo n

7

1. Let \(f ( n ) = 2 ^ { 4 n + 3 } + 3 ^ { 3 n + 1 }\). Use arithmetic modulo 11 to prove that \(\mathrm { f } ( n ) \equiv 0 ( \bmod 11 )\) for all integers \(n \geqslant 0\).
2. Use the standard test for divisibility by 11 to prove the following statements.
   1. \(10 ^ { 33 } + 1\) is divisible by 11
   2. \(10 ^ { 33 } + 1\) is divisible by 121

8

1. \(S\) is the set \(\{ 1,2,4,8,16,32 \}\) and \(\times _ { 63 }\) is the operation of multiplication modulo 63 .
   1. Construct the multiplication table for \(\left( S , \times _ { 63 } \right)\).
   2. Show that \(\left( S , \times _ { 63 } \right)\) forms a group, \(G\). (You may assume that \(\times _ { 63 }\) is associative.)
   3. The group \(H\), also of order 6, has identity element \(e\) and contains two further elements \(x\) and \(y\) with the properties $$x ^ { 2 } = y ^ { 3 } = e \quad \text { and } \quad x y x = y ^ { 2 } .$$ (a) Construct the group table of \(H\).
      (b) List all the proper subgroups of \(H\).
   4. State, with justification, whether \(G\) and \(H\) are isomorphic.

The set \(S\) is given by \(S = \{0, 2, 4, 6\}\)

1. Construct a Cayley table, using the grid below, for \(S\) under the binary operation addition modulo 8 [3 marks] \includegraphics{figure_2}
2. State the identity element for \(S\) under the binary operation addition modulo 8 [1 mark]

The set \(S\) is defined as \(S = \{1, 2, 3, 4\}\)

1. Complete the Cayley Table shown below for \(S\) under the binary operation multiplication modulo 5 [2 marks]

   \(\times_5\)	1	2	3	4
   1
   2
   3
   4

2. State the identity element for \(S\) under multiplication modulo 5 [1 mark]
3. State the self-inverse elements of \(S\) under multiplication modulo 5 [1 mark]

The group \(G\) has binary operation \(*\) and order \(p\), where \(p\) is a prime number.

1. Determine the number of distinct subgroups of \(G\) Fully justify your answer. [2 marks]
2. \(G\) contains an element \(g\) which has period \(p\)
   1. State the general name given to elements such as \(g\) [1 mark]
   2. State the name of a group that is isomorphic to \(G\) [1 mark]
3. \(G\) contains an element \(g^r\), where \(r < p\) Find, in terms of \(g\), \(r\) and \(p\), the inverse of \(g^r\) [2 marks]
4. In the case when \(p = 5\) and the binary operation \(*\) represents addition modulo 5, \(G\) contains the elements 0, 1, 2, 3 and 4
   1. Explain why \(G\) is closed. [1 mark]
   2. Complete the Cayley table for \((G, *)\) [1 mark]

      \(*\)

The binary operation \(\oplus\) acts on the positive integers \(x\) and \(y\) such that $$x \oplus y = x + y + 8 \pmod{k^2 - 16k + 74}$$ where \(k\) is a positive integer.

1. 1. Show that \(\oplus\) is commutative. [1 mark]
   2. Determine whether or not \(\oplus\) is associative. Fully justify your answer. [2 marks]
2. Find the values of \(k\) for which 3 is an identity element for the set of positive integers under \(\oplus\) [3 marks]

Which one of the following sets forms a group under the given binary operation? Tick \((\checkmark)\) one box. [1 mark]

Set	Binary Operation
\(\{1, 2, 3\}\)	Addition modulo 4	\(\square\)
\(\{1, 2, 3\}\)	Multiplication modulo 4	\(\square\)
\(\{0, 1, 2, 3\}\)	Addition modulo 4	\(\square\)
\(\{0, 1, 2, 3\}\)	Multiplication modulo 4	\(\square\)

\(G\) is the set \(\{2, 4, 6, 8\}\), \(H\) is the set \(\{1, 5, 7, 11\}\) and \(\times_n\) denotes the operation of multiplication modulo \(n\).

1. Construct the multiplication tables for \((G, \times_{10})\) and \((H, \times_{12})\). [2]
2. By verifying the four group axioms, show that \(G\) and \(H\) are groups under their respective binary operations, and determine whether \(G\) and \(H\) are isomorphic. [6]

[You may assume that \(\times_n\) is associative.]