Prove that \(3k + 2\) and \(5k + 3\) , \(k \in \mathbb{Z}\) are relatively prime.

EITHER

\(3k + 2\) and \(5k + 3\) , \(k \in \mathbb{Z}\) are relatively prime

if, for all \(k\) , there exist \(m,n \in \mathbb{Z}\) such that

\(m(3k + 2) + n(5k + 3) = 1\)     R1M1A1 

\( \Rightarrow 3m + 5n = 0\)     A1

\(2m + 3n = 1\)     A1

\(m = 5\) , \(n = - 3\)     A1

hence they are relatively prime     AG

OR

\(5k + 3 = 1 \times (3k + 2) + 2k + 1\)     M1A1

\(3k + 2 = 1 \times (2k + 1) + k + 1\)     A1

\(2k + 1 = 1 \times (k + 1) + k\)     A1

\(k + 1 = 1 \times (k) + 1\)     A1

GDC = 1     A1

so \(5k + 3\) and \(3k + 2\) are relatively prime     AG

[6 marks]

This was often done using Euclid's algorithm rather than writing \(m(3k + 2) + n(5k + 3) = 1\) for the relatively prime numbers.