8.02e Finite (modular) arithmetic: integers modulo n

8 A passage of plaintext is encoded by using the Caesar cipher corresponding to a shift of 2 places followed by the Vigenere cipher with keyword ODE.

1. The first letter in the plaintext passage is \(F\). Show that the first letter in the transmitted text is \(V\).
2. The first four letters in the transmitted text are VFIU. What are the first four letters in the plaintext passage?
3. The 800th letter in the transmitted text is \(W\). What is the 800th letter in the plaintext passage?

3 It is given that, for \(n = 0,1,2,3 , \ldots\), $$a _ { n } = 17 ^ { 2 n } + 3 ( 9 ) ^ { n } + 20$$ Simplify \(a _ { n + 1 } - a _ { n }\), and hence prove by induction that \(a _ { n }\) is divisible by 24 for all \(n \geqslant 0\).

4 Let \(\mathrm { N } = 10 \mathrm { a } + \mathrm { b }\) and \(\mathrm { M } = \mathrm { a } + 3 \mathrm {~b}\), where \(a\) and \(b\) are integers such that \(a \geqslant 1\) and \(0 \leqslant b \leqslant 9\).

1. Prove that \(29 \mid N\) if and only if \(29 \mid M\).
2. Use an iterative method based on the result of part (a) to show that 899364472 is a multiple of 29 .

2 For all positive integers \(n\), the terms of the sequence \(\left\{ u _ { n } \right\}\) are given by the formula \(u _ { n } = 3 n ^ { 2 } + 3 n + 7 ( \bmod 10 )\).

1. Show that \(u _ { n + 5 } = u _ { n }\) for all positive integers \(n\).
2. Hence describe the behaviour of the sequence, justifying your answer.

1

1. Evaluate \(13 \times 19\) modulo 31 .
2. Solve the linear congruence \(13 x \equiv 9 ( \bmod 31 )\).

4 Let \(S\) be the set \(\{ 16,36,56,76,96 \}\) and \(\times _ { H }\) the operation of multiplication modulo 100 .

1. Given that \(a\) and \(b\) are odd positive integers, show that \(( 10 a + 6 ) ( 10 b + 6 )\) can also be written in the form \(10 n + 6\) for some odd positive integer \(n\).
2. Construct the Cayley table for \(\left( S , \times _ { H } \right)\)
3. Show that \(\left( S , \times _ { H } \right)\) is a group.
   [0pt] [You may use the result that \(\times _ { H }\) is associative on \(S\).]
4. Write down all generators of \(\left( S , \times _ { H } \right)\).

4 Let \(N\) be the number 15824578 .

1. 1. Use a standard divisibility test to show that \(N\) is a multiple of 11 .
   2. A student uses the following test for divisibility by 7 . \begin{displayquote} 'Throw away' multiples of 7 that appear either individually or within a pair of consecutive digits of the test number.
      Stop when the number obtained is \(0,1,2,3,4,5\) or 6 .
      The test number is only divisible by 7 if that obtained number is 0 . \end{displayquote} For example, for the number \(N\), they first 'throw away' the " 7 " in the tens column, leaving the number \(N _ { 1 } = 15824508\). At the second stage, they 'throw away' the " 14 " from the left-hand pair of digits of \(N _ { 1 }\), leaving \(N _ { 2 } = 01824508\); and so on, until a number is obtained which is \(0,1,2,3,4,5\) or 6 .
      • Justify the validity of this process.
      • Continue the student's test to show that \(7 \mid N\).
        (iii) Given that \(N = 11 \times 1438598\), explain why 7| 1438598 .
      • Let \(\mathrm { M } = \mathrm { N } ^ { 2 }\).
        1. Express \(N\) in the unique form 101a + b for positive integers \(a\) and \(b\), with \(0 \leqslant b < 101\).
        2. Hence write \(M\) in the form \(\mathrm { M } \equiv \mathrm { r } ( \bmod 101 )\), where \(0 < r < 101\).
        3. Deduce the order of \(N\) modulo 101.

9

1. (a) Prove that \(p \equiv \pm 1 ( \bmod 6 )\) for all primes \(p > 3\).
   (b) Hence or otherwise prove that \(p ^ { 2 } - 1 \equiv 0 ( \bmod 24 )\) for all primes \(p > 3\).
2. Given that \(p\) is an odd prime, determine the residue of \(2 ^ { p ^ { 2 } - 1 }\) modulo \(p\).
3. Let \(p\) and \(q\) be distinct primes greater than 3 . Prove that \(p ^ { q - 1 } + q ^ { p - 1 } \equiv 1 ( \bmod p q )\). \section*{END OF QUESTION PAPER} www.ocr.org.uk after the live examination series.
   If OCR has unwittingly failed to correctly acknowledge or clear any third-party content in this assessment material, OCR will be happy to correct its mistake at the earliest possible opportunity. For queries or further information please contact the Copyright Team, First Floor, 9 Hills Road, Cambridge CB2 1GE.
   OCR is part of the

2

1. Prove that if \(x\) and \(y\) are integers which satisfy \(x ^ { 2 } - 2 y ^ { 2 } = 1\), then \(x\) is odd and \(y\) is even.
2. Create a program to find, for a fixed positive integer \(s\), all the positive integer solutions \(( x , y )\) to the equation \(x ^ { 2 } - 2 y ^ { 2 } = 1\) where \(x \leqslant s\) and \(y \leqslant s\). Write out your program in the Printed Answer Booklet.
3. Use your program to find all the positive integer solutions \(( x , y )\) to the equation \(x ^ { 2 } - 2 y ^ { 2 } = 1\) where \(x \leqslant 600\) and \(y \leqslant 600\). Give the solutions in ascending order of the value of \(x\).
4. By writing the equation \(x ^ { 2 } - 2 y ^ { 2 } = 1\) in the form \(( x + \sqrt { 2 } y ) ( x - \sqrt { 2 } y ) = 1\) show how the first solution (the one with the lowest value of \(x\) ) in your answer to part (c) can be used to generate the other solutions you found in part (c).
5. What can you deduce about the number of positive integer solutions \(( x , y )\) to the equation \(x ^ { 2 } - 2 y ^ { 2 } = 1\) ? In the remainder of this question \(T _ { m }\) is the \(m ^ { \text {th } }\) triangular number, the sum of the first \(m\) positive integers, so that \(T _ { m } = \frac { m ( m + 1 ) } { 2 }\).
6. Create a program to find, for a fixed positive integer \(t\), all pairs of positive integers \(m\) and \(n\) which satisfy \(T _ { m } = n ^ { 2 }\) where \(m \leqslant t\) and \(n \leqslant t\). Write out your program in the Printed Answer Booklet.
7. Use your program to find all pairs of positive integers \(m\) and \(n\) which satisfy \(T _ { m } = n ^ { 2 }\) where \(m \leqslant 300\) and \(n \leqslant 300\). Give the pairs in ascending order of the value of \(m\).
8. By comparing your answers to part (c) and part (g), or otherwise, prove that there are infinitely many triangular numbers which are perfect squares.

1. (i) Determine all the possible integers \(a\), where \(a > 3\), such that

$$15 \equiv 3 \bmod a$$ (ii) Show that if \(p\) is prime, \(x\) is an integer and \(x ^ { 2 } \equiv 1 \bmod p\) then either $$x \equiv 1 \bmod p \quad \text { or } \quad x \equiv - 1 \bmod p$$ (iii) A company has \(\pounds 13940220\) to share between 11 charities. Without performing any division and showing all your working, decide if it is possible to share this money equally between the 11 charities.

4. In this question you must show all stages of your working. Solutions relying on calculator technology are not acceptable.

1. (a) Use the Euclidean algorithm to find the highest common factor \(h\) of 416 and 72
   (b) Hence determine integers \(a\) and \(b\) such that $$416 a + 72 b = h$$ (c) Determine the value \(c\) in the set \(\{ 0,1,2 \ldots , 415 \}\) such that $$23 \times 72 \equiv c ( \bmod 416 )$$
2. Evaluate \(5 ^ { 10 } ( \bmod 13 )\) giving your answer as the smallest positive integer solution.

1. 1. Making your reasoning clear and using modulo arithmetic, show that

$$214 ^ { 6 } \text { is divisible by } 8$$ (ii) The following 7-digit number has four unknown digits $$a 5 \square b \square a b 0$$ Given that the number is divisible by 11

1. determine the value of the digit \(a\). Given that the number is also divisible by 3
2. determine the possible values of the digit \(b\).

1. Tiles are sold in boxes with 21 tiles in each box.

The tiles are laid out in \(x\) rows of 5 tiles and \(y\) rows of 6 tiles.
All the tiles from a box are used before the next box is opened.
When all the rows of tiles have been laid, there are \(n\) tiles left in the last opened box.

1. Write down a congruence expression for \(n\) in the form $$a x + b y ( \bmod c )$$ where \(a\), \(b\) and \(c\) are integers. Given that
   • exactly 43 rows of tiles are laid
   • there are no tiles left in the last opened box
   • use your congruence expression to determine the minimum number of rows of 6 tiles laid.

1. (a) Use the Euclidean Algorithm to find integers \(a\) and \(b\) such that

$$125 a + 87 b = 1$$ (b) Hence write down a multiplicative inverse of 87 modulo 125
(c) Solve the linear congruence $$87 x \equiv 16 ( \bmod 125 )$$

1. 1. The polynomial \(\mathrm { F } ( x )\) is a quartic such that

$$\mathrm { F } ( x ) = p x ^ { 4 } + q x ^ { 3 } + 2 x ^ { 2 } + r x + s$$ where \(p , q , r\) and \(s\) are distinct constants.
Determine the number of possible quartics given that

1. the constants \(p , q , r\) and \(s\) belong to the set \(\{ - 4 , - 2,1,3,5 \}\)
2. the constants \(p , q , r\) and \(s\) belong to the set \(\{ - 4 , - 2,0,1,3,5 \}\) (ii) A 3-digit positive integer \(N = a b c\) has the following properties
   • \(N\) is divisible by 11
   • the sum of the digits of \(N\) is even
   • \(N \equiv 8 \bmod 9\)
   • Use the first two properties to show that
   $$a - b + c = 0$$
3. Hence determine all possible integers \(N\), showing all your working and reasoning.

1. 1. A security code is made up of 4 numerical digits followed by 3 distinct uppercase letters.

Given that the digits must be from the set \(\{ 1,2,3,4,5 \}\) and the letters from the set \{A, B, C, D\}

1. determine the total number of possible codes using this system. To enable more codes to be generated, the system is adapted so that the 3 letters can appear anywhere in the code but no letter can be next to another letter.
2. Determine the increase in the number of codes using this adapted system.
   (ii) A combination lock code consists of four distinct digits that can be read as a positive integer, \(N = a b c d\), satisfying
   • all the digits are odd
   • \(\quad N\) is divisible by 9
   • the digits appear in either ascending or descending order
   • \(\quad N \equiv e ( \bmod a b )\) where \(a b\) is read as a two-digit number and \(e\) is the odd digit that is not used in the code
   • Use the first two properties to determine the four digits used in the code.
   • Hence determine the code on the lock.

4

1. (a) Find all the quadratic residues modulo 11.
   (b) Prove that the equation \(y ^ { 5 } = x ^ { 2 } + 2017\) has no solution in integers \(x\) and \(y\).
2. In this question you must show detailed reasoning. The numbers \(M\) and \(N\) are given by $$M = 11 ^ { 12 } - 1 \text { and } N = 3 ^ { 2 } \times 5 \times 7 \times 13 \times 61$$ Prove that \(M\) is divisible by \(N\).

3

1. Show that \(10 ^ { 2 } \equiv 6 ( \bmod 47 )\).
2. Determine the integer \(r\), with \(0 < r < 47\), such that \(6 r \equiv 1 ( \bmod 47 )\).
3. Determine the least positive integer \(n\) for which \(10 ^ { n } \equiv 1\) or \(- 1 ( \bmod 47 )\).

1 The table shows some of the outcomes of performing a modular arithmetic operation. Which pair are operations that could each be represented by the table?
Tick ( ✓ ) one box. \includegraphics[max width=\textwidth, alt={}, center]{5a826f8b-4751-4589-ad0a-109fc5c821f2-02_109_111_1338_497} Addition \(\bmod 6\) and multiplication \(\bmod 5\) \includegraphics[max width=\textwidth, alt={}, center]{5a826f8b-4751-4589-ad0a-109fc5c821f2-02_108_109_1471_497} Addition mod 6 and multiplication \(\bmod 6\) \includegraphics[max width=\textwidth, alt={}, center]{5a826f8b-4751-4589-ad0a-109fc5c821f2-02_113_109_1603_497} Addition mod 4 and multiplication \(\bmod 5\) \includegraphics[max width=\textwidth, alt={}, center]{5a826f8b-4751-4589-ad0a-109fc5c821f2-02_107_109_1742_497} Addition mod 4 and multiplication mod 6

2 The binary operation ⊗ is given by \(a \otimes b = 3 a ( 5 + b ) ( \bmod 8 )\) where \(a , b \in \mathbb { Z }\) Given that \(2 \otimes x = 6\), which of the integers below is a possible value of \(x\) ?
Circle your answer.
[0pt] [1 mark]
0123

5

1. Complete the Cayley table in Figure 1 for multiplication modulo 4 \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{dcf97b92-d067-41d4-89a6-ea5bab9ea4ff-08_761_1017_434_493}
   \end{figure} 5
2. The set \(S\) is defined as $$S = \{ a , b , c , d \}$$ Figure 2 shows an incomplete Cayley table for \(S\) under the commutative binary operation • \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2}

   •	\(a\)	\(b\)	\(c\)	\(d\)
   \(a\)	\(b\)	\(a\)	\(a\)	\(c\)
   \(b\)		\(c\)		\(c\)
   \(c\)		\(d\)	\(d\)
   \(d\)			\(d\)	\(d\)

   \end{table} 5 (b) (i) Complete the Cayley table in Figure 2. 5 (b) (ii) Determine whether the binary operation • is associative when acting on the elements of \(S\). Fully justify your answer.

5

1. The set \(S\) is defined as \(S = \{ 0,1,2,3,4,5 \}\) 5
   1. (i) State the identity element of \(S\) under the operation multiplication modulo 6 5
   2. (ii) An element \(g\) of a set is said to be self-inverse under a binary operation * if $$g * g = e$$ where \(e\) is the identity element of the set. Find all the self-inverse elements in \(S\) under the operation multiplication modulo 6
      5
   3. \(\quad\) The set \(T\) is defined as $$T = \{ a , b , c \}$$ Figure 1 shows a partially completed Cayley table for \(T\) under the commutative binary operation - \begin{table}[h]
      \captionsetup{labelformat=empty} \caption{Figure 1}

      -	\(a\)	\(b\)	c
      \(a\)	\(a\)	c	b
      \(b\)		\(b\)	\(a\)
      c			c

      \end{table} 5
   4. 1. Complete the Cayley table in Figure 1 5
   5. (ii) Prove that is not associative when acting on the elements of \(T\)

6 For positive integers \(n\), let \(f ( n ) = 1 + 2 ^ { n } + 4 ^ { n }\).

1. 1. Given that \(n\) is a multiple of 3 , but not of 9 , use the division algorithm to write down the two possible forms that \(n\) can take.
   2. Show that when \(n\) is a multiple of 3 , but not of 9 , \(f ( n )\) is a multiple of 73 .
2. Determine the value of \(\mathrm { f } ( n )\), modulo 73 , in the case when \(n\) is a multiple of 9 .

4

1. Let \(a = 1071\) and \(b = 67\).
   1. Find the unique integers \(q\) and \(r\) such that \(\mathrm { a } = \mathrm { bq } + \mathrm { r }\), where \(q > 0\) and \(0 \leqslant r < b\).
   2. Hence express the answer to (a)(i) in the form of a linear congruence modulo \(b\).
2. Use the fact that \(358 \times 715 - 239 \times 1071 = 1\) to prove that 715 and 1071 are co-prime.