8.02f Single linear congruences: solve ax = b (mod 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?

6

1. Determine all values of \(x\) for which \(16 x \equiv 5 ( \bmod 101 )\).
2. Solve
   1. \(95 x \equiv 6 ( \bmod 101 )\),
   2. \(95 x \equiv 5 ( \bmod 101 )\).

5

1. Express as a decimal (base-10) number the base-23 number \(7119 _ { 23 }\).
2. Solve the linear congruence \(7 n + 11 \equiv 9 ( \bmod 23 )\).
3. Let \(N = 10 a + b\) and \(M = a + 7 b\), where \(a\) and \(b\) are integers and \(0 \leqslant b \leqslant 9\).
   1. By considering \(3 N - 7 M\), prove that \(23 \mid N\) if and only if \(23 \mid M\).
   2. Use a procedure based on this result to show that \(N = 711965\) is a multiple of 23 .

1

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

3

1. Solve \(7 x \equiv 6 ( \bmod 19 )\).
2. Show that the following simultaneous linear congruences have no solution. $$x \equiv 3 ( \bmod 4 ) , x \equiv 4 ( \bmod 6 )$$

8

1. Solve the second-order recurrence system \(\mathrm { H } _ { \mathrm { n } + 2 } = 5 \mathrm { H } _ { \mathrm { n } + 1 } - 4 \mathrm { H } _ { \mathrm { n } }\) with \(H _ { 0 } = 3 , H _ { 1 } = 7\) for \(n \geqslant 0\).
2. 1. Write down the quadratic residues modulo 10 .
   2. By considering the sequence \(\left\{ \mathrm { H } _ { \mathrm { n } } \right\}\) modulo 10, prove that \(\mathrm { H } _ { \mathrm { n } }\) is never a perfect square.

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. (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. (a) Use the Euclidean algorithm to show that 124 and 17 are relatively prime (coprime).
   (b) Hence solve the equation

$$124 x + 17 y = 10$$ (c) Solve the congruence equation $$124 x \equiv 6 \bmod 17$$

1. (a) Use the Euclidean algorithm to show that the highest common factor of 168 and 66 is 6
   (b) Use back substitution to determine integers \(a\) and \(b\) such that

$$168 a + 66 b = 6$$ (c) Explain why there are no integer solutions to the equation $$168 x + 66 y = 10$$ (d) Solve the congruence equation $$11 v \equiv 8 ( \bmod 28 )$$

1 Solve \(12 x \equiv 3 ( \bmod 99 )\).

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 )\).

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\)