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
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)\) .
(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\) .
Answer/Explanation
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]