Question
The graph \(G\) has the following cost adjacency matrix.
Draw \(G\) in planar form.
Given that \(ax \equiv b(\bmod p)\) where \(a,b,p,x \in {\mathbb{Z}^ + }\) , \(p\) is prime and \(a\) is not a multiple of \(p\), use Fermat’s little theorem to show that
\(x \equiv {a^{p – 2}}b(\bmod p)\) .
Hence solve the simultaneous linear congruences\[3x \equiv 4(\bmod 5)\]\[5x \equiv 6(\bmod 7)\]giving your answer in the form \(x \equiv c(\bmod d)\) .
Answer/Explanation
Markscheme
A2
[2 marks]
Note: The weights are not required for this A2.
Multiply through by \({a^{p – 2}}\) .
\({a^{p – 1}}x \equiv {a^{p – 2}}b(\bmod p)\) M1A1
Since, by Fermat’s little theorem, \({a^{p – 1}} \equiv 1(\bmod p)\) , R1
\(x \equiv {a^{p – 2}}b(\bmod p)\) AG
[3 marks]
Using the result from (a),
\(x \equiv {3^3} \times 4(\bmod 5) \equiv 3(\bmod 5)\) M1A1
\( = 3\), \(8\), \(13\), \(18\), \(23\),… (A1)
and \(x \equiv {5^5} \times 6(\bmod 7) \equiv 4(\bmod 7)\) M1A1
\( = 4\), \(11\), \(18\), \(25\),… (A1)
The general solution is
\(x = 18 + 35n\) M1
i.e. \(x \equiv 18(\bmod 35)\) A1
[8 marks]
Question
Use Kruskal’s algorithm to find a minimum spanning tree for the weighted graph shown below. State the weight of the tree.[5]
For the travelling salesman problem defined by this graph, find
(i) an upper bound;
(ii) a lower bound.[8]
Given that the integers \(m\) and \(n\) are such that \(3|({m^2} + {n^2})\) , prove that \(3|m\) and \(3|n\) .[7]
Hence show that \(\sqrt 2 \) is irrational.[5]
Answer/Explanation
Markscheme
Start at an edge with weight \(2\), say BH, add other edges of weight \(2\) such that a cycle is not formed. Continue to add edges of increasing weight until all vertices have been included. M1
thus the minimum spanning tree is
\({\rm{BH + HC + GK + KH + KE + EF + GA + CD}}\) A3
total weight \( = 2 + 2 + 3 + 4 + 4 + 4 + 5 + 5 = 29\) A1
Note: GB may replace KH and other orders are possible.[5 marks]
(i) upper bound \( = 2 \times \) weight of minimum spanning tree M1
\( = 58\) A1
(ii) deleting vertex F M1
the minimum spanning tree is
\({\rm{BH + HC + GK + KE + KH + GA + CD}}\) A2
total weight \( = 2 + 2 + 3 + 4 + 4 + 5 + 5 = 25\) A1
adding the two edges of least weight from F M1
lower bound \( = 25 + 4 + 6 = 35\) A1
Note: Alternative solutions may be given by deleting a different vertex. [8 marks]
EITHER
\(3|m \Rightarrow m \equiv 0(\bmod 3)\) (R1)
if this is false then \(m \equiv 1\) or \(2(\bmod 3)\) and \({m^2} \equiv 1\) or \(4(\bmod 3)\) R1A1
since \(4 \equiv 1(\bmod 3)\) then \({m^2} \equiv 1(\bmod 3)\) A1
similarly \({n^2} \equiv 1(\bmod 3)\) A1
hence \({m^2} + {n^2} \equiv 2(\bmod 3)\)
but \({m^2} + {n^2} \equiv 0(\bmod 3)\) (R1)
this is a contradiction so \(3|m\) and \(3|n\) R1AG
OR
\(m \equiv 0\) , 1 or \(2(\bmod 3)\) and \(n \equiv 0\) , 1 or \(2(\bmod 3)\) M1R1
\( \Rightarrow {m^2} \equiv 0\) or \(1(\bmod 3)\) and \({n^2} \equiv 0\) or \(1(\bmod 3)\) A1A1
so \({m^2} + {n^2} \equiv 0,1,2(\bmod 3)\) A1
but \(3|{m^2} + {n^2}\) so \({m^2} + {n^2} \equiv 0(\bmod 3)\) R1
\(m \equiv 0(\bmod 3)\) and \(n \equiv 0(\bmod 3)\) R1
\( \Rightarrow 3|m\) and \(3|n\) AG[7 marks]
suppose \(\sqrt 2 = \frac{a}{b}\) , where \(a,b \in \mathbb{Z}\) and \(a\) and \(b\) are coprime M1
then
\(2{b^2} = {a^2}\) A1
\({a^2} + {b^2} = 3{b^2}\) A1
\(3{b^2} \equiv 0(\bmod 3)\) A1
but by (a) \(a\) and \(b\) have a common factor so \(\sqrt 2 \ne \frac{a}{b}\) R1
\( \Rightarrow \sqrt 2 \) is irrational AG[5 marks]
Question
Given the linear congruence \(ax \equiv b({\rm{mod}}p)\) , where \(a\) , \(b \in \mathbb{Z} \) , \(p\) is a prime and \({\rm{gcd}}(a,p) = 1\) , show that \(x \equiv {a^{p – 2}}b({\rm{mod}}p)\) .[4]
(i) Solve \(17x \equiv 14(\bmod 21)\) .
(ii) Use the solution found in part (i) to find the general solution to the Diophantine equation \(17x + 21y = 14\) .[10]
Answer/Explanation
Markscheme
\(ax \equiv b({\rm{mod}}p)\)
\( \Rightarrow {a^{p – 2}} \times ax \equiv {a^{p – 2}} \times b({\rm{mod}}p)\) M1A1
\( \Rightarrow {a^{p – 1}}x \equiv {a^{p – 2}} \times b({\rm{mod}}p)\) A1
but \({a^{p – 1}} \equiv 1({\rm{mod}}p)\) by Fermat’s little theorem R1
\( \Rightarrow x \equiv {a^{p – 2}} \times b({\rm{mod}}p)\) AG
Note: Award M1 for some correct method and A1 for correct statement.
[4 marks]
(i) \(17x \equiv 14(\bmod 21)\)
\( \Rightarrow x \equiv {17^{19}} \times 14(\bmod 21)\) M1A1
\({17^6} \equiv 1(\bmod21)\) A1
\( \Rightarrow x \equiv {(1)^3} \times 17 \times 14(\bmod 21)\) A1
\( \Rightarrow x \equiv 7(\bmod21)\) A1
(ii) \(x \equiv 7(mod21)\)
\( \Rightarrow x = 7 + 21t\) , \(t \in \mathbb{Z}\) M1A1
\( \Rightarrow 17(7 + 21t) + 21y = 14\) A1
\( \Rightarrow 119 + 357t + 21y = 14\)
\( \Rightarrow 21y = – 105 – 357t\) A1
\( \Rightarrow y = – 5 – 17t\) A1
[10 marks]
Question
The graph \(H\) has the following adjacency matrix.
(i) Show that \(H\) is bipartite.
(ii) Draw \(H\) as a planar graph.
(i) Explain what feature of \(H\) guarantees that it has an Eulerian circuit.
(ii) Write down an Eulerian circuit in \(H\) .
(i) Find the number of different walks of length five joining A to B.
(ii) Determine how many of these walks go through vertex F after passing along two edges.
Find the maximum number of extra edges that can be added to \(H\) while keeping it simple, planar and bipartite.
Find the smallest positive integer \(m\) such that \({3^m} \equiv 1(\bmod 22)\) .
Given that \({3^{49}} \equiv n(\bmod 22)\) where \(0 \le n \le 21\) , find the value of \(n\) .
Solve the equation \({3^x} \equiv 5(\bmod 22)\) .
Answer/Explanation
Markscheme
(i) using any method, (M1)
find that \(\left\{ {{\rm{A,C,D,F}}} \right\}\) and \(\left\{ {{\rm{B,E,G}}} \right\}\) are disjoint sets of vertices A1
so that \(H\) is bipartite AG
(ii)
A1
[3 marks]
(i) all vertices are of even degree A1
(ii) DECBAGFBD A2
[3 marks]
(i)
M1
number of walks \( = 36\) A1
(ii) recognition of the need to find walks of length \(2\) and walks of length \(3\) (M1)
number of walks of length \(2\) from A to F \( = 2\) A1
number of walks of length \(3\) from F to B \( = 6\) A1
required number of walks \( =12\) A1
[6 marks]
for a simple, bipartite graph to be planar,
\(e \le 2v – 4 = 10\) M1
at the moment, \(e = 8\) which means that we cannot add more than \(2\) edges A1
we see that we can add \(2\) edges, e.g. EA and EF A1
the maximum number of edges we can add is therefore \(2\) A1
[4 marks]
evaluating successive powers of \(3\) (M1)
\({3^1} \equiv 3(\bmod 22)\) , \({3^2} \equiv 9(\bmod 22)\) , \({3^3} \equiv 5(\bmod 22)\)
\({3^4} \equiv 15(\bmod 22)\) , \({3^5} \equiv 1(\bmod 22)\) so \(m = 5\) A1
[2 marks]
since \({3^5} \equiv 1(\bmod 22)\) , \({3^{45}} = {({3^5})^9} \equiv 1(\bmod 22)\) M1A1
consider \({3^{49}} = {3^{45}} \times {3^4} \equiv 1 \times 15(\bmod 22)\) so \(n = 15\) M1A1
[4 marks]
from (a), \(x = 3\) is a solution A1
since \({3^5} \equiv 1(\bmod 22)\) , the complete solution is \(x = 3 + 5N\) where \(N \in \bullet \) (M1)A1
[3 marks]