8.02d Division algorithm: a = bq + r uniquely

5 For integers \(a\) and \(b\), with \(a \geqslant 0\) and \(0 \leqslant b \leqslant 99\), the numbers \(M\) and \(N\) are such that $$M = 100 a + b \text { and } N = a - 9 b .$$

1. By considering the number \(M + 2 N\), show that \(17 \mid M\) if and only if \(17 \mid N\).
2. Demonstrate step-by-step how an algorithm based on the result of part (i) can be used to show that 2058376813901 is a multiple of 17 .

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 .

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

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. (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. (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. (i) Use the Euclidean algorithm to find the highest common factor of 602 and 161.

Show each step of the algorithm.
(ii) The digits which can be used in a security code are the numbers \(1,2,3,4,5,6,7,8\) and 9. Originally the code used consisted of two distinct odd digits, followed by three distinct even digits. To enable more codes to be generated, a new system is devised. This uses two distinct even digits, followed by any three other distinct digits. No digits are repeated. Find the increase in the number of possible codes which results from using the new system.

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

6 You are given that \(n\) is an integer.

1. (a) Show that \(\operatorname { hcf } ( 2 n + 1,3 n + 2 ) = 1\).
   (b) Hence prove that, if \(( 2 n + 1 )\) divides \(\left( 36 n ^ { 2 } + 3 n - 14 \right)\), then \(( 2 n + 1 )\) divides \(( 12 n - 7 )\).
2. Use the results of part (i) to find all integers \(n\) for which \(\frac { 36 n ^ { 2 } + 3 n - 14 } { 2 n + 1 }\) is also an integer.

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.