Show that ${\text{gcd}}\left( {4k + 2,\,3k + 1} \right) = {\text{gcd}}\left( {k - 1,\,2} \right)$, where $k \in {\mathbb{Z}^ + },\,k > 1$.

State the value of ${\text{gcd}}\left( {4k + 2,\,3k + 1} \right)$ for odd positive integers $k$.

State the value of ${\text{gcd}}\left( {4k + 2,\,3k + 1} \right)$ for even positive integers $k$.

METHOD 1

attempting to use the Euclidean algorithm       M1

$4k + 2 = 1\left( {3k + 1} \right) + \left( {k + 1} \right)$      A1

$3k + 1 = 2\left( {k + 1} \right) + \left( {k - 1} \right)$      A1

$K + 1 = \left( {k - 1} \right) + 2$      A1

$= {\text{gcd}}\left( {k - 1,\,2} \right)$     AG

METHOD 2

${\text{gcd}}\left( {4k + 2,\,3k + 1} \right)$

$= {\text{gcd}}\left( {4k + 2 - \left( {3k + 1} \right),\,3k + 1} \right)$     M1

$= {\text{gcd}}\left( {3k + 1,\,k + 1} \right)\,\,\left( { = {\text{gcd}}\left( {{\text{k + 1,}}\,{\text{3k + 1}}} \right)} \right)$     A1

$= {\text{gcd}}\left( {3k + 1 - 2\left( {k + 1} \right),\,k + 1} \right)\,\,\left( { = {\text{gcd}}\left( {k - 1{\text{,}}\,k + {\text{1}}} \right)} \right)$     A1

$= {\text{gcd}}\left( {k + 1 - \left( {k - 1} \right),\,k - 1} \right)\,\,\left( { = {\text{gcd}}\left( {{\text{2,}}\,k - {\text{1}}} \right)} \right)$     A1

$= {\text{gcd}}\left( {k - 1,\,2} \right)$     AG

[4 marks]

(for $k$ odd), ${\text{gcd}}\left( {4k + 2,\,3k + 1} \right) = 2$     A1

[1 mark]

(for $k$ even), ${\text{gcd}}\left( {4k + 2,\,3k + 1} \right) = 1$     A1

[1 mark]