Download IITian Academy App for accessing Online Mock Tests and More..
Question
The relation \(R\) is defined on the set \(\mathbb{Z}\) by \(aRb\) if and only if \(4a + b = 5n\) , where \(a,b,n \in \mathbb{Z}\).
Show that \(R\) is an equivalence relation.
State the equivalence classes of \(R\) .
Answer/Explanation
Markscheme
\(4a + b = 5n\) for \(a,b,n \in \mathbb{Z}\)
reflexive:
\(4a + a = 5a\) so \(aRa\) , and \(R\) is reflexive A1
symmetric:
\(4a + b = 5n\)
\(4b + a = 5b – b + 5a – 4a\) M1
\( = 5b + 5a – (4a + b)\) A1
\( = 5m\) so \(bRa\) , and \(R\) is symmetric A1
transitive:
\(4a + b = 5n\) M1
\(4b + c = 5k\) M1
\(4a + 5b + c = 5n + 5k\) A1
\(4a + c = 5(n + k – b)\) so \(aRc\) , and \(R\) is transitive A1
therefore \(R\) is an equivalence relation AG
[8 marks]
equivalence classes are
\(\left\{ { \ldots , – 10, – 5,0,5,10,\left. \ldots \right\}} \right.\) (M1)
\(\left\{ { \ldots , – 9, – 4,1,6,11,\left. \ldots \right\}} \right.\)
\(\left\{ { \ldots , – 8, – 3,2,7,12,\left. \ldots \right\}} \right.\)
\(\left\{ { \ldots , – 7, – 2,3,8,13,\left. \ldots \right\}} \right.\)
\(\left\{ { \ldots , – 6, – 1,4,9,14,\left. \ldots \right\}} \right.\)
or \(\left\{ {\left\langle 0 \right\rangle ,\left\langle 1 \right\rangle ,\left\langle 2 \right\rangle ,\left\langle 3 \right\rangle ,\left. {\left\langle 4 \right\rangle } \right\}} \right.\) A2
Note: Award A2 for all classes, A1 for at least 2 correct classes.
[3 marks]
Question
Let S be the set of matrices given by
\(\left[ \begin{array}{l}
a\\
c
\end{array} \right.\left. \begin{array}{l}
b\\
d
\end{array} \right]\) ; \(a,b,c,d \in \mathbb{R}\), \(ad – bc = 1\)
The relation \(R\) is defined on \(S\) as follows. Given \(\boldsymbol{A}\) , \(\boldsymbol{B} \in S\) , \(\boldsymbol{ARB}\) if and only if there exists \(\boldsymbol{X} \in S\) such that \(\boldsymbol{A} = \boldsymbol{BX}\) .
Show that \(R\) is an equivalence relation.
The relationship between \(a\) , \(b\) , \(c\) and \(d\) is changed to \(ad – bc = n\) . State, with a reason, whether or not there are any non-zero values of \(n\) , other than \(1\), for which \(R\) is an equivalence relation.
Answer/Explanation
Markscheme
since \(\boldsymbol{A} = \boldsymbol{AI}\) where \(\boldsymbol{I}\) is the identity A1
and \(\det (\boldsymbol{I}) = 1\) , A1
\(R\) is reflexive
\(\boldsymbol{ARB} \Rightarrow \boldsymbol{A} = \boldsymbol{BX}\) where \(\det (\boldsymbol{X}) = 1\) M1
it follows that \(\boldsymbol{B} = \boldsymbol{A}{\boldsymbol{X}^{ – 1}}\) A1
and \(\det ({\boldsymbol{X}^{ – 1}}) = \det{(\boldsymbol{X})^{ – 1}} = 1\) A1
\(R\) is symmetric
\(\boldsymbol{ARB}\) and \(\boldsymbol{BRC} \Rightarrow \boldsymbol{A} = \boldsymbol{BX}\) and \(\boldsymbol{B} = \boldsymbol{CY}\) where \(\det (\boldsymbol{X}) = \det (\boldsymbol{Y}) = 1\) M1
it follows that \(\boldsymbol{A} = \boldsymbol{CYX}\) A1
\(\det (\boldsymbol{YX}) = \det (\boldsymbol{Y})\det (\boldsymbol{X}) = 1\) A1
\(R\) is transitive
hence \(R\) is an equivalence relation AG
[8 marks]
for reflexivity, we require \(\boldsymbol{ARA}\) so that \(\boldsymbol{A} = \boldsymbol{AI}\) (for all \(\boldsymbol{A} \in S\) ) M1
since \(\det (\boldsymbol{I}) = 1\) and we require \(\boldsymbol{I} \in S\) the only possibility is \(n = 1\) A1
[2 marks]
Question
Prove that the number \(14 641\) is the fourth power of an integer in any base greater than \(6\).
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}.
Answer/Explanation
Markscheme
\(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
The group \(\{ G,{\text{ }} * \} \) has a subgroup \(\{ H,{\text{ }} * \} \). The relation \(R\) is defined, for \(x,{\text{ }}y \in G\), by \(xRy\) if and only if \({x^{ – 1}} * y \in H\).
(a) Show that \(R\) is an equivalence relation.
(b) Given that \(G = \{ 0,{\text{ }} \pm 1,{\text{ }} \pm 2,{\text{ }} \ldots \} \), \(H = \{ 0,{\text{ }} \pm 4,{\text{ }} \pm 8,{\text{ }} \ldots \} \) and \( * \) denotes addition, find the equivalence class containing the number \(3\).
Answer/Explanation
Markscheme
(a) \(\underline {{\text{reflexive}}} \)
\({x^{ – 1}}x = e \in H\) A1
therefore \(xRx\) and \(R\) is reflexive R1
\(\underline {{\text{symmetric}}} \)
Note: Accept the word commutative.
let \(xRy\) so that \({x^{ – 1}}y \in H\) M1
the inverse of \({x^{ – 1}}y\) is \({y^{ – 1}}x \in H\) A1
therefore \(yRx\) and \(R\) is symmetric R1
\(\underline {{\text{transitive}}} \)
let \(xRy\) and \(yRz\) so \({x^{ – 1}}y \in H\) and \({y^{ – 1}}z \in H\) M1
therefore \({x^{ – 1}}y\,{y^{ – 1}}z = {x^{ – 1}}z \in H\) A1
therefore \(xRz\) and \(R\) is transitive R1
hence \(R\) is an equivalence relation AG
[8 marks]
(b) the identity is \(0\) so the inverse of \(3\) is \(-3\) (R1)
the equivalence class of 3 contains \(x\) where \( – 3 + x \in H\) (M1)
\( – 3 + x = 4n{\text{ }}(n \in \mathbb{Z})\) (M1)
\(x = 3 + 4n{\text{ (n}} \in \mathbb{Z})\) A1
Note: Accept \(\{ \ldots – 5,{\text{ }} – 1,{\text{ }}3,{\text{ }}7,{\text{ }} \ldots \} \) or \(x \equiv 3(\bmod 4)\).
Note: If no other relevant working seen award A3 for \(\{ 3 + 4n\} \) or \(\{ \ldots – 5,{\text{ }} – 1,{\text{ }}3,{\text{ }}7,{\text{ }} \ldots \} \) seen anywhere.
[4 marks]
Question
The relations \({\rho _1}\) and \({\rho _2}\) are defined on the Cartesian plane as follows
\(({x_1},{\text{ }}{y_1}){\rho _1}({x_2},{\text{ }}{y_2}) \Leftrightarrow x_1^2 – x_2^2 = y_1^2 – y_2^2\)
\(({x_1},{\text{ }}{y_1}){\rho _2}({x_2},{\text{ }}{y_2}) \Leftrightarrow \sqrt {x_1^2 + x_2^2} \leqslant \sqrt {y_1^2 + y_2^2} \).
For \({\rho _1}\) and \({\rho _2}\) determine whether or not each is reflexive, symmetric and transitive.
For each of \({\rho _1}\) and \({\rho _2}\) which is an equivalence relation, describe the equivalence classes.
Answer/Explanation
Markscheme
\({\rho _1}\)
\(({x_1},{\text{ }}{y_1}){\rho _1}({x_1},{\text{ }}{y_1}) \Rightarrow 0 = 0\;\;\;\)hence reflexive. R1
\(({x_1},{\text{ }}{y_1}){\rho _1}({x_2},{\text{ }}{y_2}) \Rightarrow x_1^2 – x_2^2 = y_1^2 – y_2^2\)
\( \Rightarrow (x_1^2 – x_2^2) = – (y_1^2 – y_2^2)\)
\( \Rightarrow x_2^2 – x_1^2 = y_2^2 – y_1^2 \Rightarrow ({x_2},{\text{ }}{y_2}){\rho _1}({x_1},{\text{ }}{y_1})\;\;\;\)hence symmetric M1A1
\(({x_1},{\text{ }}{y_1}){\rho _1}({x_2},{\text{ }}{y_2}) \Rightarrow x_1^2 – x_2^2 = y_1^2 – y_2^2{\text{ – i}}\)
\(({x_2},{\text{ }}{y_2}){\rho _1}({x_3},{\text{ }}{y_3}) \Rightarrow x_2^2 – x_3^2 = y_2^2 – y_3^2{\text{ – ii}}\) M1
\({\text{i}} + {\text{ii}} \Rightarrow x_1^2 – x_3^2 = y_1^2 – y_3^2 \Rightarrow ({x_1},{\text{ }}{y_1}){\rho _1}({x_3},{\text{ }}{y_3})\;\;\;\)hence transitive A1
\({\rho _2}\)
\(({x_1},{\text{ }}{y_1}){\rho _2}({x_1},{\text{ }}{y_1}) \Rightarrow \sqrt {2x_1^2} \leqslant \sqrt {2y_1^2} \;\;\;\)This is not true in the case of (3,1)
hence not reflexive. R1
\(({x_1},{\text{ }}{y_1}){\rho _2}({x_2},{\text{ }}{y_2}) \Rightarrow \sqrt {x_1^2 + x_2^2} \leqslant \sqrt {y_1^2 + y_2^2} \)
\( \Rightarrow \sqrt {x_2^2 + x_1^2} \leqslant \sqrt {y_2^2\_y_1^2} \Rightarrow ({x_2},{\text{ }}{x_2}){\rho _2}({x_1},{\text{ }}{y_1})\;\;\;\)hence symmetric. A1
it is not transitive. A1
attempt to find a counterexample (M1)
for example \((1,{\text{ }}0){\rho _2}(0,{\text{ 1)}}\) and \((0,{\text{ }}1){\rho _2}(1,{\text{ 0)}}\) A1
however, it is not true that \((1,{\text{ }}0){\rho _2}(1,{\text{ 0)}}\) A1
\({\rho _1}\) is an equivalence relation A1
the equivalence classes for \({\rho _1}\) form a family of curves of the form
\({y^2} – {x^2} = k\) A1
Question
Use the Euclidean algorithm to find \(\gcd (162,{\text{ }}5982)\).
The relation \(R\) is defined on \({\mathbb{Z}^ + }\) by \(nRm\) if and only if \(\gcd (n,{\text{ }}m) = 2\).
(i) By finding counterexamples show that \(R\) is neither reflexive nor transitive.
(ii) Write down the set of solutions of \(nR6\).
Answer/Explanation
Markscheme
\(5982 = 162 \times 36 + 150\) M1A1
\(162 = 150 \times 1 + 12\) A1
\(150 = 12 \times 12 + 6\)
\(12 = 6 \times 2 + 0 \Rightarrow \gcd \) is 6 A1
[4 marks]
(i) for example, \(\gcd (4,{\text{ }}4) = 4\) A1
\(4 \ne 2\) R1
so \(R\) is not reflexive AG
for example
\(\gcd (4,{\text{ }}2) = 2\) and \(\gcd (2,{\text{ }}8) = 2\) M1A1
but \(\gcd (4,{\text{ }}8) = 4{\text{ }}( \ne 2)\) R1
so \(R\) is not transitive AG
(ii) EITHER
even numbers A1
not divisible by 6 A1
OR
\(\{ 2 + 6n:n \in \mathbb{N}\} {\text{ }} \cup \{ 4 + 6n:n \in \mathbb{N}\} \) A1A1
OR
\(2,{\text{ }}4,{\text{ }}8,{\text{ }}10,{\text{ }} \ldots \) A2
[7 marks]