| Date | May 2008 | Marks available | 7 | Reference code | 08M.3dm.hl.TZ1.1 |
| Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ1 |
| Command term | Justify, State, Find, and Hence | Question number | 1 | Adapted from | N/A |
Question
Use the Euclidean Algorithm to find the greatest common divisor of 7854 and 3315.
Hence state the number of solutions to the diophantine equation 7854x + 3315y = 41 and justify your answer.
Markscheme
\(7854 = 2 \times 3315 + 1224\) M1A1
\(3315 = 2 \times 1224 + 867\) A1
\(1224 = 1 \times 867 + 357\)
\(867 = 2 \times 357 + 153\)
\(357 = 2 \times 153 + 51\)
\(153 = 3 \times 51\) A1
The gcd is 51. A1
Since 51 does not divide 41, R1
there are no solutions. A1
[7 marks]
Examiners report
Most candidates were able to use the Euclidean Algorithm correctly to find the greatest common divisor. Candidates who used the GCD button on their calculators were given no credit. Some candidates seemed unaware of the criterion for the solvability of Diophantine equations.
