| Date | None Specimen | Marks available | 5 | Reference code | SPNone.3dm.hl.TZ0.1 |
| Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ0 |
| Command term | Find and Hence or otherwise | Question number | 1 | Adapted from | N/A |
Question
Use the Euclidean algorithm to find the greatest common divisor of 259 and 581.
[4]
a.
Hence, or otherwise, find the general solution to the diophantine equation 259x + 581y = 7 .
[5]
b.
Markscheme
\(581 = 2 \times 259 + 63\) M1A1
\(259 = 4 \times 63 + 7\) A1
\(63 = 9 \times 7\)
the GCD is therefore 7 A1
[4 marks]
a.
consider
\(7 = 259 - 4 \times 63\) M1
\( = 259 - 4 \times (581 - 2 \times 259)\) A1
\( = 259 \times 9 + 581 \times ( - 4)\) A1
the general solution is therefore
\(x = 9 + 83n;{\text{ }}y = - 4 - 37n{\text{ where }}n \in \mathbb{Z}\) M1A1
Notes: Accept solutions laid out in tabular form. Dividing the diophantine equation by 7 is an equally valid method.
[5 marks]
b.
Examiners report
[N/A]
a.
[N/A]
b.
