Question
a.Given a sequence of non negative integers \(\{ {a_r}\} \) show that
(i) \(\sum\limits_{r = 0}^n {{a_r}{{(x + 1)}^r}(\bmod x) = \sum\limits_{r = 0}^n {{a_r}(\bmod x)} } \) where \(x \in \{ 2,{\text{ }}3,{\text{ }}4 \ldots \} \).
(ii) \(\sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){9^r} = \sum\limits_{r = 0}^{2n + 1} {{a_r}{3^r}} } \).[5]
b.Hence determine whether the base \(3\) number \(22010112200201\) is divisible by \(8\).[5]
▶️Answer/Explanation
Markscheme
(i) \((x + 1)(\bmod x) \equiv 1(\bmod x)\) (M1)
\({(x + 1)^r}(\bmod x)\left( { \equiv {1^r}(\bmod x)} \right) = 1(\bmod x)\) A1
\(\sum\limits_{r – 0}^n {{a_r}{{(x + 1)}^r}(\bmod x) \equiv \sum\limits_{r = 0}^n {{a_r}(\bmod x)} } \) AG
(ii) METHOD 1
\(\sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){9^r} = \sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){3^{2r}}} } \) M1
\( = \sum\limits_{r = 0}^n {({3^{2r + 1}}{a_{2r + 1}} + {3^{2r}}{a_{2r}})} \) M1A1
\( = \sum\limits_{r = 0}^{2n + 1} {{a_r}{3^r}} \) AG
METHOD 2
\(\sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){9^r} = 3{a_1} + {a_0} + 9(3{a_3} + {a_2}) + \ldots + {9^n}(3{a_{2n + 1}} + {a_{2n}})} \) A1
\( = {a_0} + 3{a_1} + {3^2}{a_2} + {3^3}{a_3} + \ldots + {3^{2n + 1}}{a_{2n + 1}}\) M1A1
\( = \sum\limits_{r = 0}^{2n + 1} {{a_r}{3^r}} \) AG
[5 marks]
METHOD 1
using part (a) (ii) to separate the number into pairs of digits (M1)
\(22010112200201{\text{ }}({\text{base }}3) \equiv 8115621{\text{ }}({\text{base }}9)\) A1
using the sum of digits identity from part (a) (i) (M1)
Note: Award M1 if result from a(i) is used to show that the number is divisible by \(2\), even if no other valid working given.
\({\text{sum}} = 24\) A1
which is divisible by \(8\) A1
hence \(22010112200201\) (base \(3\)) is divisible by \(8\)
METHOD 2
\(\sum\limits_{r = 0}^{13} {{a_r}{3^r}\sum\limits_{r = 0}^6 {(3{a_{2r + 1}} + {a_{2r}}){9^r}} } \) (M1)
\( \equiv \sum\limits_{r = 0}^6 {(3{a_{2r + 1}} + {a_{2r}})(\bmod 8)} \) A1
\( = {a_0} + 3{a_1} + {a_2} + 3{a_3} + \ldots + {a_{12}} + 3{a_{13}}(\bmod 8)\) M1
\( = (1 + 3 \times 0 + 2 + 3 \times 0 + \ldots + 3 \times 2)(\bmod 8) \equiv 24(\bmod 8)\) A1
\( \equiv 0\) OR divisible by \(8\) A1
hence \(22010112200201\) (base \(3\)) is divisible by \(8\)
[5 marks]
Total [10 marks]
Examiners report
[N/A]
[N/A]
Question
a.Show that there are exactly two solutions to the equation \(1982 = 36a + 74b\), with \(a,{\text{ }}b \in \mathbb{N}\).[8]
b.Hence, or otherwise, find the remainder when \({1982^{1982}}\) is divided by \(37\).[5]
▶️Answer/Explanation
Markscheme
\(74 = 2 \times 36 + 2\) OR \(\gcd (36,{\text{ }}74) = 2\) (A1)
\(2 = ( – 2)(36) + (1)(74)\) M1
\(1982 = ( – 1982)(36) + (991)(74)\) A1
so solutions are \(a = – 1982 + 37t\) and \(b = 991 – 18t\) M1A1
\(a,{\text{ }}b \in \mathbb{N}{\text{ so }}\frac{{1982}}{{37}} \le t \le \frac{{991}}{{18}}\;\;\;{\text{(}}15.56 \ldots \le t \le 55.055 \ldots )\) (M1)(A1)
\(t\) can take values \(54\) or \(55\) only A1AG
(Or the solutions are \((16,{\text{ }}19)\) or \((53,{\text{ }}1)\))
Note: Accept arguments from one solution of increasing/decreasing \(a\) by \(37\) and increasing/decreasing \(b\) by \(18\) to give the only possible positive solutions.
[8 marks]
\(1982 = 53 \times 36 + 74\)
\(1982 = 55 \times 36 + 2\) (M1)
\({1982^{36}} \equiv 1(\bmod 37){\text{ }}({\text{by FLT}})\) (M1)
\({1982^{1982}} = {1982^{36 \times 55 + 2}} \equiv {1982^2}(\bmod 37)\) (A1)
\( \equiv 34(\bmod 37)\) A1
so the remainder is \(34\) A1
Note: \(1982\) in the base can be replaced by \(21\).
Note: Award the first (M1) if the \(1982\) in the experiment is correctly broken down to a smaller number.
[5 marks]
Total [13 marks]
Examiners report
[N/A]
[N/A]
Question
Anna is playing with some cars and divides them into three sets of equal size. However, when she tries to divide them into five sets of equal size, there are four left over. Given that she has fewer than 50 cars, what are the possible numbers of cars she can have?
▶️Answer/Explanation
Markscheme
METHOD 1
let x be the number of cars
we know \(x \equiv 0(\bmod 3)\) (A1)
also \(x \equiv 4(\bmod 5)\) (A1)
so \(x = 3t \Rightarrow 3t \equiv 4(\bmod 5)\) M1
\( \Rightarrow 6t \equiv 8(\bmod 5)\)
\( \Rightarrow t \equiv 3(\bmod 5)\)
\( \Rightarrow t = 3 + 5s\)
\( \Rightarrow x = 9 + 15s\) A1
since there must be fewer than 50 cars, x = 9, 24, 39 A1A1A1
Note: Only award two of the final three A1 marks if more than three solutions are given.
[7 marks]
METHOD 2
x is a multiple of 3 that ends in 4 or 9 R4
therefore x = 9, 24, 39 A1A1A1 N3
Note: Only award two of the final three A1 marks if more than three solutions are given.
[7 marks]
Examiners report
There were a number of totally correct solutions to this question, but some students were unable to fully justify their results.
Question
a.Use the Euclidean algorithm to express gcd (123, 2347) in the form 123p + 2347q, where \(p,{\text{ }}q \in \mathbb{Z}\).[8]
b.Find the least positive solution of \(123x \equiv 1(\bmod 2347)\) .[3]
c.Find the general solution of \(123z \equiv 5(\bmod 2347)\) .[3]
▶️Answer/Explanation
Markscheme
\(2347 = 19 \times 123 + 10\) M1A1
\((123 = 12 \times 10 + 3)\)
\(10 = 3 \times 3 + 1\) A1
\(1(\gcd ) = 10 – 3 \times 3 = 10 – 3 \times (123 – 12 \times 10)\) M1A1
\( = 37 \times 10 – 3 \times 123\) A1
\( = 37 \times (2347 – 19 \times 123) – 3 \times 123\) (for continuation) M1
\( = 37 \times 2347 – 706 \times 123\) A1
[8 marks]
EITHER
\(1(\bmod 2347) = ( – 706 \times 123)(\bmod 2347)\) M1A1
OR
\(x = – 706 + 2347n\) M1A1
solution: 1641 A1
[3 marks]
\(5(\bmod 2347) = ( – 3530 \times 123)(\bmod 2347)\) (M1)
\({\text{GS}}:z = – 3530 + k2347\) A1A1
Note: Other common possibilities include \(1164 + k2347\) and \(8205 + k2347\) .
[3 marks]
empty set (123 and 2346 both divisible by 3) A1
[1 mark]
Examiners report
The majority of candidates were successful in parts (a) and (b). In part (c), some candidates failed to understand the distinction between a particular solution and a general solution. Part (d) was a 1 mark question that defeated all but the few who noticed that the gcd of the numbers concerned was 3.
The majority of candidates were successful in parts (a) and (b). In part (c), some candidates failed to understand the distinction between a particular solution and a general solution. Part (d) was a 1 mark question that defeated all but the few who noticed that the gcd of the numbers concerned was 3.
The majority of candidates were successful in parts (a) and (b). In part (c), some candidates failed to understand the distinction between a particular solution and a general solution. Part (d) was a 1 mark question that defeated all but the few who noticed that the gcd of the numbers concerned was 3.
The majority of candidates were successful in parts (a) and (b). In part (c), some candidates failed to understand the distinction between a particular solution and a general solution. Part (d) was a 1 mark question that defeated all but the few who noticed that the gcd of the numbers concerned was 3.
Question
a.Use the Euclidean algorithm to find the greatest common divisor of the numbers 56 and 315.[4]
b.(i) Find the general solution to the diophantine equation \(56x + 315y = 21\).
(ii) Hence or otherwise find the smallest positive solution to the congruence \(315x \equiv 21\) (modulo 56) .[9]
▶️Answer/Explanation
Markscheme
\(315 = 5 \times 56 + 35\) M1
\(56 = 1 \times 35 + 21\)
\(35 = 1 \times 21 + 14\) A1
\(21 = 1 \times 14 + 7\)
\(14 = 2 \times 7\) A1
therefore gcd = 7 A1
[4 marks]
(i) \(7 = 21 – 14\) M1
\( = 21 – (35 – 21)\)
\( = 2 \times 21 – 35\) (A1)
\( = 2 \times (56 – 35) – 35\)
\( = 2 \times 56 – 3 \times 35\) (A1)
\( = 2 \times 56 – 3 \times (315 – 5 \times 56)\)
\( = 17 \times 56 – 3 \times 315\) (A1)
therefore \(56 \times 51 + 315 \times (- 9) = 21\) M1
\(x = 51,{\text{ }}y = – 9\) is a solution (A1)
the general solution is \(x = 51 + 45N\) , \(y = – 9 – 8N\) , \(N \in \mathbb{Z}\) A1A1
(ii) putting N = –2 gives y = 7 which is the required value of x A1
[9 marks]
Examiners report
This question was generally well answered although some candidates were unable to proceed from a particular solution of the Diophantine equation to the general solution.
This question was generally well answered although some candidates were unable to proceed from a particular solution of the Diophantine equation to the general solution.
Question
Given that \(a,{\text{ }}b,{\text{ }}c,{\text{ }}d \in \mathbb{Z}\), show that
\[(a – b)(a – c)(a – d)(b – c)(b – d)(c – d) \equiv 0(\bmod 3).\]
▶️Answer/Explanation
Markscheme
EITHER
we work modulo 3 throughout
the values of a, b, c, d can only be 0, 1, 2 R2
since there are 4 variables but only 3 possible values, at least 2 of the variables must be equal \((\bmod 3)\) R2
therefore at least 1 of the differences must be \(0(\bmod 3)\) R2
the product is therefore \(0(\bmod 3)\) R1AG
OR
we attempt to find values for the differences which do not give \(0(\bmod 3)\) for the product
we work modulo 3 throughout
we note first that none of the differences can be zero R1
a − b can therefore only be 1 or 2 R1
suppose it is 1, then b − c can only be 1
since if it is 2, \((a – b) + (b – c) \equiv 3 \equiv 0(\bmod 3)\) R1
c − d cannot now be 1 because if it is
\((a – b) + (b – c) + (c – d) = a – d \equiv 3 \equiv 0(\bmod 3)\) R1
c − d cannot now be 2 because if it is
\((b – c) + (c – d) = b – d \equiv 3 \equiv 0(\bmod 3)\) R1
we cannot therefore find values of c and d to give the required result R1
a similar argument holds if we suppose a − b is 2, in which case b − c must be 2 and we cannot find a value of c − d R1
the product is therefore \(0(\bmod 3)\) AG
[7 marks]
Examiners report
Most candidates who solved this question used the argument that there are four variables which can take only one of three different values modulo 3 so that at least two must be equivalent modulo 3 which leads to the required result. This apparently simple result, however, requires a fair amount of insight and few candidates managed it.
Question
a.Define what is meant by the statement \(x \equiv y(\bmod n){\text{ where }}x{\text{, }}y{\text{, }}n \in {\mathbb{Z}^ + }\) .[1]
b.Hence prove that if \(x \equiv y(\bmod n)\) then \({x^2} \equiv {y^2}(\bmod n)\) .[4]
c.Determine whether or not \({x^2} \equiv {y^2}(\bmod n)\) implies that \(x \equiv y(\bmod n)\) .[4]
▶️Answer/Explanation
Markscheme
\(x \equiv y(\bmod n) \Rightarrow x = y + kn,{\text{ }}(k \in \mathbb{Z})\) A1
[1 mark]
\(x \equiv y(\bmod n)\)
\( \Rightarrow x = y + kn\) M1
\({x^2} = {y^2} + 2kny + {k^2}{n^2}\) A1
\( \Rightarrow {x^2} = {y^2} + (2ky + {k^2}n)n\) M1A1
\( \Rightarrow {x^2} \equiv {y^2}(\bmod n)\) AG
[4 marks]
EITHER
\({x^2} \equiv {y^2}(\bmod n)\)
\( \Rightarrow {x^2} – {y^2} = 0(\bmod n)\) M1
\( \Rightarrow (x – y)(x + y) = 0(\bmod n)\) A1
This will be the case if
\(x + y = 0(\bmod n){\text{ or }}x = – y(\bmod n)\) R1
so \(x \ne y(\bmod n)\) in general R1
[4 marks]
OR
Any counter example, e.g. \(n = 5,{\text{ }}x = 3,{\text{ }}y = 2,\) in which case R2
\({x^2} \equiv {y^2}(\bmod n)\) but \(x \ne y(\bmod n)\). (false) R1R1
[4 marks]
Examiners report
While most candidates gave a correct meaning to \(x \equiv y(\bmod n)\) , there were some incorrect statements, the most common being \(x \equiv y(\bmod n)\) means that when x is divided by n, there is a remainder y. The true statement \(8 \equiv 5(\bmod 3)\) shows that this statement is incorrect. Part (b) was solved successfully by many candidates but (c) caused problems for some candidates who thought that the result in (c) followed automatically from the result in (b).
While most candidates gave a correct meaning to \(x \equiv y(\bmod n)\) , there were some incorrect statements, the most common being \(x \equiv y(\bmod n)\) means that when x is divided by n, there is a remainder y. The true statement \(8 \equiv 5(\bmod 3)\) shows that this statement is incorrect. Part (b) was solved successfully by many candidates but (c) caused problems for some candidates who thought that the result in (c) followed automatically from the result in (b).
While most candidates gave a correct meaning to \(x \equiv y(\bmod n)\) , there were some incorrect statements, the most common being \(x \equiv y(\bmod n)\) means that when x is divided by n, there is a remainder y. The true statement \(8 \equiv 5(\bmod 3)\) shows that this statement is incorrect. Part (b) was solved successfully by many candidates but (c) caused problems for some candidates who thought that the result in (c) followed automatically from the result in (b).