8.02i Prime numbers: composites, HCF, coprimality

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

2 Consider the integers \(a\) and \(b\), where, for each integer \(n , \mathrm { a } = 7 \mathrm { n } + 4\) and \(\mathrm { b } = 8 \mathrm { n } + 5\). Let \(\mathrm { h } = \mathrm { hcf } ( \mathrm { a } , \mathrm { b } )\).

1. Determine all possible values of \(h\).
2. Find all values of \(n\) for which \(a\) and \(b\) are not co-prime.

8 Let \(f ( n )\) denote the base- \(n\) number \(2121 _ { n }\) where \(n \geqslant 3\).

1. 1. For each \(n \geqslant 3\), show that \(\mathrm { f } ( n )\) can be written as the product of two positive integers greater than \(1 , \mathrm { a } ( n )\) and \(\mathrm { b } ( n )\), each of which is a function of \(n\).
   2. Deduce that \(\mathrm { f } ( n )\) is always composite.
2. Let \(h\) be the highest common factor of \(\mathrm { a } ( n )\) and \(\mathrm { b } ( n )\).
   1. Prove that \(h\) is either 1 or 5 .
   2. Find a value of \(n\) for which \(h = 5\).

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$$

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.