User interface language: English | Español

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\).

[4]
a.

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

[1]
b.i.

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

[1]
b.ii.

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]

 

a.

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

[1 mark]

b.i.

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

[1 mark]

b.ii.

Examiners report

[N/A]
a.
[N/A]
b.i.
[N/A]
b.ii.

Syllabus sections

Topic 10 - Option: Discrete mathematics » 10.2 » \(\left. a \right|b \Rightarrow b = na\) for some \(n \in \mathbb{Z}\) .

View options