| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Number Theory |
| Type | Algorithm tracing and properties |
| Difficulty | Easy -1.2 This is a straightforward algorithm tracing exercise from D1 (Decision Mathematics), which is typically easier than pure maths modules. Parts (i) and (ii) require only mechanical execution of the Euclidean algorithm with simple arithmetic. Part (iii) involves basic algebraic manipulation to express the HCF as a linear combination, but follows a guided template. This is routine procedural work with no conceptual challenges or problem-solving required. |
| Spec | 7.03a Algorithm definition: input, output, deterministic, finite7.03c Working with algorithms: trace, interpret, adapt |
| A | B | Q | R 1 | R 2 |
| 30 | 42 | 1 | 12 | |
| 12 | 30 | 2 | 6 | |
| 6 | ||||
| 6 | 12 | 2 | 0 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Trace table: A=84, B=660, Q=7, R1=72; then A=72, B=84, Q=1, R2=12; then A=12, B=72, Q=6, R2=0 | M1 | |
| Correct trace | A1 | |
| Print 12 | B1\(\checkmark\) | Follow through their 12 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| A=660, B=84, Q=0, R1=84; then A=84, B=660, etc. | M1 | |
| Correct continuation | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Line 2 gives \(6 = 30 - 2 \times 12\) | B1 | |
| Substituting: \(6 = 30 - 2(42-30) = 3\times30 - 2\times42\) | B1 | 3 |
| B1 | 2 |
# Question 3:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Trace table: A=84, B=660, Q=7, R1=72; then A=72, B=84, Q=1, R2=12; then A=12, B=72, Q=6, R2=0 | M1 | |
| Correct trace | A1 | |
| Print 12 | B1$\checkmark$ | Follow through their 12 |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| A=660, B=84, Q=0, R1=84; then A=84, B=660, etc. | M1 | |
| Correct continuation | A1 | |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Line 2 gives $6 = 30 - 2 \times 12$ | B1 | |
| Substituting: $6 = 30 - 2(42-30) = 3\times30 - 2\times42$ | B1 | 3 |
| | B1 | 2 |
---3 The following algorithm finds the highest common factor of two positive integers. ("int (x)" stands for the integer part of x, e.g. int (7.8) = 7.)
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{b9ee9306-18ca-42b3-9f2e-b23849374b5e-4_888_693_422_717}
\captionsetup{labelformat=empty}
\caption{Fig. 3.1}
\end{center}
\end{figure}
(i) Run the algorithm with $\mathrm { A } = 84$ and $\mathrm { B } = 660$, showing all of your calculations.\\
(ii) Run the algorithm with $\mathrm { A } = 660$ and $\mathrm { B } = 84$, showing as many calculations as are necessary.\\
(iii) The algorithm is run with $\mathrm { A } = 30$ and $\mathrm { B } = 42$, and the result is shown in Table 3.2 below.
\begin{table}[h]
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
A & B & Q & R 1 & R 2 \\
\hline
30 & 42 & 1 & 12 & \\
\hline
12 & 30 & 2 & & 6 \\
\hline
& & & 6 & \\
\hline
6 & 12 & 2 & & 0 \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Print 6}
\end{center}
\end{table}
Table 3.2
The first line of the table shows that $12 = 42 - 1 \times 30$.\\
Use the second line to obtain a similar expression for 6 in terms of 30 and 12.\\
Hence express 6 in the form $\mathrm { m } \times 30 - \mathrm { n } \times 42$, where m and n are integers.
\hfill \mbox{\textit{OCR MEI D1 2005 Q3 [8]}}