User interface language: English | Español

Date May 2017 Marks available 5 Reference code 17M.3dm.hl.TZ0.1
Level HL only Paper Paper 3 Discrete mathematics Time zone TZ0
Command term Find Question number 1 Adapted from N/A

Question

Use the Euclidean algorithm to find the greatest common divisor of 264 and 1365.

[5]
a.

Hence, or otherwise, find the general solution of the Diophantine equation

\[264x - 1365y = 3.\]

[6]
b.i.

Hence find the general solution of the Diophantine equation

\[264x - 1365y = 6.\]

[2]
b.ii.

By expressing each of 264 and 1365 as a product of its prime factors, determine the lowest common multiple of 264 and 1365.

[3]
c.

Markscheme

\(1365 = 5 \times 264 + 45\)     M1

\(264 = 5 \times 45 + 39\)     A1

\(45 = 1 \times 39 + 6\)     A1

\(39 = 6 \times 6 + 3\)

\(6 = 2 \times 3\)     A1

so gcd is 3

[5 marks]

a.

EITHER

\(39 - 6 \times 6 = 3\)     (M1)

\(39 - 6 \times (45 - 39) = 3 \Rightarrow 7 \times 39 - 6 \times 45 = 3\)     (A1)

\(7 \times (264 - 5 \times 45) - 6 \times 45 = 3 \Rightarrow 7 \times 264 - 41 \times 45 = 3\)     (A1)

\(7 \times 264 - 41 \times (1365 - 5 \times 264) = 3 \Rightarrow 212 \times 264 - 41 \times 1365 = 3\)     (A1)

OR

tracking the linear combinations when applying the Euclidean algorithm (could be displayed in (a))

M17/5/MATHL/HP3/ENG/TZ0/DM/M/01.b.i

THEN

a solution is \(x = 212,y = 41\) (or equivalent eg \(x = - 243,y = - 47\))     (A1)

\(x = 212 + 455N,y = 41 + 88N\) (or equivalent) \((N \in \mathbb{Z})\)     A1

[6 marks]

b.i.

a solution is \(x = 424,y = 82{\text{ }}({\text{or equivalent }}eg{\text{ }}x = - 31,{\text{ }}y = - 6)\)     (A1)

\(x = 424 + 455N,{\text{ }}y = 82 + 88N({\text{or equivalent}}){\text{ }}\left( {N \in \mathbb{Z}} \right)\)     A1

 

Note:     Award A1A0 for \(x = 424 + 910N,{\text{ }}y = 82 + 176N\).

 

[2 marks]

b.ii.

\(264 = 2 \times 2 \times 2 \times 3 \times 11\)     A1

\(1365 = 3 \times 5 \times 7 \times 13\)     A1

\(1\,{\text{cm}} = 2 \times 2 \times 2 \times 3 \times 5 \times 7 \times 11 \times 13 = 120120\)     A1

 

Note:     Only award marks if prime factorisation is used.

 

[3 marks]

c.

Examiners report

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

Syllabus sections

Topic 10 - Option: Discrete mathematics » 10.2
Show 26 related questions

View options