Date | May 2018 | Marks available | 1 | Reference code | 18M.3dm.hl.TZ0.4 |
Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ0 |
Command term | State | Question number | 4 | Adapted from | N/A |
Question
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\).
Markscheme
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]