| Date | November 2010 | Marks available | 11 | Reference code | 10N.3dm.hl.TZ0.2 |
| Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ0 |
| Command term | Find | Question number | 2 | Adapted from | N/A |
Question
(a) Find the general solution for the following system of congruences.
\(N \equiv 3(\bmod 11)\)
\(N \equiv 4(\bmod 9)\)
\(N \equiv 0(\bmod 7)\)
(b) Find all values of N such that \(2000 \leqslant N \leqslant 4000\).
Markscheme
(a) \(N = 3 + 11t\) M1
\(3 + 11t \equiv 4(\bmod 9)\)
\(2t \equiv 1(\bmod 9)\) (A1)
multiplying by 5, \(10t \equiv 5(\bmod 9)\) (M1)
\(t \equiv 5(\bmod 9)\) A1
\(t = 5 + 9s\) M1
\(N = 3 + 11(5 + 9s)\)
\(N = 58 + 99s\) A1
\(58 + 99s \equiv 0(\bmod 7)\)
\(2 + s \equiv 0(\bmod 7)\)
\(s \equiv 5(\bmod 7)\) A1
\(s = 5 + 7u\) M1
\(N = 58 + 99(5 + 7u)\)
\(N = 553 + 693u\) A1
Note: Allow solutions that are done by formula or an exhaustive, systematic listing of possibilities.
[9 marks]
(b) u = 3 or 4
hence N = 553 + 2079 = 2632 or N = 553 + 2772 = 3325 A1A1
[2 marks]
Total [11 marks]
Examiners report
This was a standard Chinese remainder theorem problem that many candidates gained good marks on. Some candidates employed a formula, which was fine if they remembered it correctly (but not all did), although it did not always show good understanding of the problem.
