Coprimality proofs

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.

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.

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.