Question
a.Prove that the number \(14 641\) is the fourth power of an integer in any base greater than \(6\).[3]
b.For \(a,b \in \mathbb{Z}\) the relation \(aRb\) is defined if and only if \(\frac{a}{b} = {2^k}\) , \(k \in \mathbb{Z}\) .
(i) Prove that \(R\) is an equivalence relation.
(ii) List the equivalence classes of \(R\) on the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.[8]
▶️Answer/Explanation
Markscheme
a.\(14641\) (base \(a > 6\) ) \( = {a^4} + 4{a^3} + 6{a^2} + 4a + 1\) , M1A1
\( = {(a + 1)^4}\) A1
this is the fourth power of an integer AG
[3 marks]
(i) \(aRa\) since \(\frac{a}{a} = 1 = {2^0}\) , hence \(R\) is reflexive A1
\(aRb \Rightarrow \frac{a}{b} = {2^k} \Rightarrow \frac{b}{a} = {2^{ – k}} \Rightarrow bRa\)
so R is symmetric A1
\(aRb\) and \(bRc \Rightarrow \frac{a}{b} = {2^m}\), \(m \in \mathbb{Z}\) and \(bRc \Rightarrow \frac{b}{c} = {2^n}\) , \(n \in \mathbb{Z}\) M1
\( \Rightarrow \frac{a}{b} \times \frac{b}{c} = \frac{a}{c} = {2^{m + n}}\) , \(m + n \in \mathbb{Z}\) A1
\( \Rightarrow aRc\) so transitive R1
hence \(R\) is an equivalence relation AG
(ii) equivalence classes are {1, 2, 4, 8} , {3, 6} , {5, 10} , {7} , {9} A3
Note: Award A2 if one class missing, A1 if two classes missing, A0 if three or more classes missing.
[8 marks]
Question
a.Using mathematical induction or otherwise, prove that the number \({(1020)_n}\) , that is the number \(1020\) written with base \(n\) , is divisible by \(3\) for all values of \(n\) greater than \(2\).[8]
b.Explain briefly why the case \(n = 2\) has to be excluded.[1]
▶️Answer/Explanation
Markscheme
\({(1020)_n} = {n^3} + 2n\) (R1)
so we are required to prove that \({n^3} + 2n\) is divisible by \(3\) for \(n \ge 3\) (R1)
EITHER
when \(n = 3\) , \({n^3} + 2n = 33\) which is divisible by \(3\) so the result is true for \(n = 3\) A1
assume the result is true for \(n = k\) , i.e. \({k^3} + 2k\) is divisible by \(3\) M1
for \(n = k + 1\) ,
\({(k + 1)^3} + 2(k + 1) = {k^3} + 3{k^2} + 3k + 1 + 2k + 2\) M1
\( = ({k^3} + 2k) + 3({k^2} + k + 1)\) A1
the second term is clearly divisible by \(3\) and the first term is divisible by \(3\) by hypothesis A1
therefore true for \(n = k \Rightarrow \) true for \(n = k + 1\) and since shown true for \(n = 3\) ,
the result is proved by induction R1
Note: Award the final R1 only if the two M1 marks have been awarded.
OR
there are three cases to consider, let \(N\) be a positive integer
case 1: \(n = 3N\) , in this case
\(n({n^2} + 2) = 3N(9{N^2} + 2)\) which is divisible by \(3\) M1A1
case 2: \(n = 3N + 1\) , in this case,
\(n({n^2} + 2) = (3N + 1)(9{N^2} + 6N + 3)\) which is divisible by \(3\) M1A1
case 3: \(n = 3N + 2\) , in this case,
\(n({n^2} + 2) = (3N + 2)(9{N^2} + 12N + 6)\) which is divisible by \(3\) M1A1
this proves the required result for all \(n > 2\)
[8 marks]
numbers to base \(2\) do not use the digit \(2\) or equivalent R1
[1 mark]
Question
a.(i) Use the Euclidean algorithm to find gcd(\(6750\), \(144\)) .
(ii) Express your answer in the form \(6750r + 144s\) where r , \(s \in \mathbb{Z}\) .[6]
b.Consider the base \(15\) number CBA, where A, B, C represent respectively the digits ten, eleven, twelve.
(i) Write this number in base \(10\).
(ii) Hence express this number as a product of prime factors, writing the factors in base 4.[6]
▶️Answer/Explanation
Markscheme
(i) \(6750 = 46 \times 144 + 126\) M1A1
\(144 = 1 \times 126 + 18\) A1
\(126 = 7 \times 18\)
\(\gcd(6750,144) = 18\) A1 N0
(ii) \(18 = 144 – 1 \times 126\) (M1)
\( = 144 – (6750 – 46 \times 144)\)
\( = 47 \times 144 + ( – 1) \times 6750\) A1
[6 marks]
(i) \(n = 10 + 11 \times 15 + 12 \times {15^2}\) (M1)(A1)
\( = 2875\) A1
(ii) \(2875 = {5^3} \times 23\) A1
\( = 11 \times 11 \times 11 \times 113\) in base \(4\) A1A1
Note: A1 for \(11 \times 11 \times 11\) , A1 for \(113\) .
[6 marks]
Question
Find the positive square root of the base 7 number \({(551662)_7}\), giving your answer as a base 7 number.
▶️Answer/Explanation
Markscheme
converting to base 10
\({(551662)_7} = 2 + 6 \times 7 + 6 \times {7^2} + 1 \times {7^3} + 5 \times {7^4} + 5 \times {7^5}\) (M1)
\( = 96721\) (A1)
\(\sqrt {96721} = 311\) A1
converting back to base 7
\(7)\underline {311} \) (M1)
\()\underline {44} (3\)
\()\underline 6 (2\) (A1)
it follows that \(\sqrt {{{(551662)}_7}} = {(623)_7}\) A1
Note: Accept \(623\).
[6 marks]
Question
a.Show that \({2^n} \equiv {( – 1)^n}(\bmod 3)\), where \(n \in \mathbb{N}\).[3]
b.Hence show that an integer is divisible by 3 if and only if the difference between the sum of its binary (base 2) digits in even-numbered positions and the sum of its binary digits in odd-numbered positions is divisible by 3.[3]
c.Express the hexadecimal (base 16) number \({\text{ABB}}{{\text{A}}_{{\text{16}}}}\) in binary.[4]
▶️Answer/Explanation
Markscheme
METHOD 1
\({2^n} = {(3 – 1)^n}\) M1
\( = {3^n} + n{3^{n – 1}}( – 1) + \frac{{n(n – 1)}}{2}{3^{n – 2}}{( – 1)^2} + {\text{ }} \ldots {\text{ }} + {( – 1)^n}\) A1
since all terms apart from the last one are divisible by 3 R1
\({2^n} \equiv {( – 1)^n}(\bmod 3)\) AG
METHOD 2
attempt to reduce the powers of \(2(\bmod 3)\) M1
\({2^0} = 1(\bmod 3);{\text{ }}{2^1} = – 1(\bmod 3);{\text{ }}{2^2} = 1(\bmod 3);{\text{ }}{2^3} = – 1(\bmod 3){\text{ }} \ldots \) A1
since \(1(\bmod 3) \times 2 = – 1(\bmod 3)\) and \( – 1(\bmod 3) \times 2 = 1(\bmod 3)\) the result can be generalized R1
\(2n \equiv {( – 1)^n}(\bmod 3)\) AG
[3 marks]
the binary number \(N = {({a_n}{a_{n – 1}} \ldots {a_2}{a_1}{a_0})_2}\) has numerical value
\({a_0} \times 1 + {a_1} \times 2 + {a_2} \times {2^2} + \ldots + {a_n} \times {2^n}\) A1
\(N = \left( {{a_0} – {a_1} + {a_2} – \ldots {{( – 1)}^n}{a_n}} \right)(\bmod 3)\) M1A1
hence divisibility of \(N\) by 3 coincides with statement of question AG
[3 marks]
\({\text{ABB}}{{\text{A}}_{16}} = 10 \times {16^3} + 11 \times {16^2} + 11 \times 16 + 10 \times 1\) (A1)
\(N = {(1010)_2} \times {2^{12}} + {(1011)_2} \times {2^8} + {(1011)_2} \times {2^4} + {(1010)_2} \times {2^0}\) (M1)(A1)
Note: Award M1 for expressing A and B in binary.
\(N = {(1010101110111010)_2}\) A1
[4 marks]