Number Theory

1

1. Express 205 in the form \(7 q + r\) for positive integers \(q\) and \(r\), with \(0 \leqslant r < 7\).
2. Given that \(7 \mid ( 205 \times 8666 )\), use the result of part (a) to justify that \(7 \mid 8666\).

1. In this question you must show detailed reasoning.

Without performing any division, explain why \(n = 20210520\) is divisible by 66

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 In this question you must show detailed reasoning. Express the number \(\mathbf { 4 1 7 2 3 } _ { 10 }\) in hexadecimal (base 16).

2 The following steps define an algorithm which acts on two numbers.
STEP 1 Write down the two numbers side by side on the same row.
STEP 2 Beneath the left-hand number write down double that number. Beneath the right-hand number write down half of that number, ignoring any remainder. STEP 3 Repeat STEP 2 until the right-hand number is 1.
STEP 4 Delete those rows where the right-hand number is even. Add up the remaining left-hand numbers. This is the result.

1. Apply the algorithm to the left-hand number 3 and the right-hand number 8.
2. Apply the algorithm to the left-hand number 26 and the right-hand number 42.
3. Use your results from parts (i) and (ii), together with any other examples you may choose, to write down what the algorithm achieves.

2 Throughout this question ( \(a , b , c\) ) is a Pythagorean triple with the positive integers \(a , b , c\) ordered such that \(a \leqslant b \leqslant c\).

1. Show that \(\mathrm { a } ^ { 2 } = \mathrm { b } + \mathrm { c }\) if and only if \(\mathrm { c } = \mathrm { b } + 1\).
2. Create a program to find all the Pythagorean triples ( \(a , b , c\) ) such that \(\mathrm { a } ^ { 2 } = \mathrm { b } + \mathrm { c }\) and \(c \leqslant 1000\). Write out your program in full in the Printed Answer Booklet.
3. Write down the number of Pythagorean triples found by your program in (b).
4. Prove that there is no Pythagorean triple, \(( a , b , c )\), in which \(\mathrm { b } ^ { 2 } = \mathrm { a } + \mathrm { c }\).

3 Given that \(n\) is a positive integer, show that the numbers ( \(4 n + 1\) ) and ( \(6 n + 1\) ) are co-prime.

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

1. In this question you must show detailed reasoning.

Use Fermat's Little Theorem to determine the least positive residue of
\(21 { } ^ { 80 } ( \bmod 23 )\)
(4)

4 Solve the simultaneous linear congruences \(x \equiv 1 ( \bmod 3 ) , x \equiv 5 ( \bmod 11 ) , 2 x \equiv 5 ( \bmod 17 )\).

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

5 Given that \(n\) is a positive integer greater than 2 , prove that

1. \(\quad 10201 _ { n }\) is a square number.
2. \(\quad 1221 _ { n }\) is a composite number.

1. (i) Without performing any division, explain why 8184 is divisible by 6
   (ii) Use the Euclidean algorithm to find integers \(a\) and \(b\) such that

$$27 a + 31 b = 1$$

1. (i) Using a suitable algorithm and without performing any division, determine whether 23738 is divisible by 11
   (ii) Use the Euclidean algorithm to find the highest common factor of 2322 and 654

6 You are given that \(q \in \mathbb { Z }\) with \(q \geqslant 1\) and that
\(\mathrm { S } = \frac { 1 } { ( \mathrm { q } + 1 ) } + \frac { 1 } { ( \mathrm { q } + 1 ) ( \mathrm { q } + 2 ) } + \frac { 1 } { ( \mathrm { q } + 1 ) ( \mathrm { q } + 2 ) ( \mathrm { q } + 3 ) } + \ldots\).

1. By considering a suitable geometric series show that \(\mathrm { S } < \frac { 1 } { \mathrm { q } }\).
2. Deduce that \(S \notin \mathbb { Z }\). You are also given that \(\mathrm { e } = \sum _ { r = 0 } ^ { \infty } \frac { 1 } { r ! }\).
3. Assume that \(\mathrm { e } = \frac { \mathrm { p } } { \mathrm { q } }\), where \(p\) and \(q\) are positive integers. By writing the infinite series for e in a form using \(q\) and \(S\) and using the result from part (b), prove by contradiction that e is irrational.

8 In this question you must show detailed reasoning.

1. Prove that \(2 ( p - 2 ) ^ { p - 2 } \equiv - 1 ( \bmod p )\), where \(p\) is an odd prime.
2. Find two odd prime factors of the number \(N = 2 \times 34 ^ { 34 } - 2 ^ { 15 }\). \section*{END OF QUESTION PAPER} \section*{OCR
   Oxford Cambridge and RSA}

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?

5. (a) Explain why a network cannot have an odd number of vertices of odd degree. \begin{figure}[h] \end{figure} Figure 4 shows a network of paths in a public park. The number on each arc represents the length of that path in metres. Hamish needs to walk along each path at least once to check the paths for frost damage starting and finishing at \(A\). He wishes to minimise the total distance he walks.
(b) Use the route inspection algorithm to find which paths, if any, need to be traversed twice.
(c) Find the length of Hamish's route.
[0pt] [The total weight of the network in Figure 4 is 4180 m .]

6 Eight footpaths connect six villages. The lengths of these footpaths, in km , are given in the table.

1. The shortest route from B to C using these footpaths has length 10 km . Without using an algorithm, write down this shortest route from B to C.
2. Use an appropriate algorithm to find the shortest route from A to F .
3. Write down all the pairs of villages for which the shortest route between them uses at least one footpath that is not in the minimum spanning tree for the six villages.

5 A list of 8 values is given below. The list is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.

1. Carry out the first two passes of the sort. A different list of 8 values is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
2. 1. State the maximum number of passes that could be required.
   2. Find the minimum number of passes that could be required. The run-time for quick sort could be measured by counting the number of comparisons used. In the worst case, the run time for quick sort is \(\mathrm { O } \left( n ^ { 2 } \right)\). A computer takes at most 0.03 seconds to sort a list of 100 values into increasing order using quick sort.
3. Calculate an estimate for the time taken, in the worst case, to sort a list of 500 values using quick sort. A list of \(n\) values (where \(n > 10\) ) is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
4. Explain why, in the best case, \(n - 3\) comparisons are used in the second pass.

3 Floyd's algorithm is applied to the following network:
\includegraphics[max width=\textwidth, alt={}, center]{483a681e-011a-464f-b7cb-007d894d1516-3_398_394_331_833} At the end of the third iteration of the algorithm the distance and route matrices are as follows: \begin{center} \begin{tabular}{ | c | c | c | c | c | } \cline { 2 - 5 } \multicolumn{1}{c|}{} & \(\mathbf { 1 }\) & \(\mathbf { 2 }\) & \(\mathbf { 3 }\) & \(\mathbf { 4 }\)
\hline \(\mathbf { 1 }\) & 6 & 3 & 10 & 5
\hline \(\mathbf { 2 }\) & 3 & 6 & 7 & 2
\hline \(\mathbf { 3 }\) & 10 & 7 & 14 & 1
\hline

8 A simple connected graph has six vertices.

1. One vertex has degree \(x\). State the greatest and least possible values of \(x\).
2. The six vertices have degrees $$x - 2 , x - 2 , x , 2 x - 4,2 x - 4,4 x - 12$$ Find the value of \(x\), justifying your answer.
   
   \includegraphics[max width=\textwidth, alt={}]{fe9c0da0-40e3-4a87-ae9a-13ec0740ffff-19_2484_1707_223_155}