Download IITian Academy App for accessing Online Mock Tests and More..
Question
(a) Show that the solution to the linear congruence \(ax \equiv b(\bmod p)\), where \(a,{\text{ }}x,{\text{ }}b,{\text{ }}p \in {\mathbb{Z}^ + },{\text{ }}p\) is prime and \(a\), \(p\) are relatively prime, is given by \(x \equiv {a^{p – 2}}b(\bmod p)\).
(b) Consider the congruences
\(7x \equiv 13(\bmod 19)\)
\(2x \equiv 1(\bmod 7)\).
(i) Use the result in (a) to solve the first congruence, giving your answer in the form \(x \equiv k(\bmod 19)\) where \(1 \leqslant k \leqslant 18\).
(ii) Find the set of integers which satisfy both congruences simultaneously.
Answer/Explanation
Markscheme
(a) using Fermat’s little theorem, (M1)
\({a^{p – 1}} \equiv 1(\bmod p)\) A1
multiplying both sides of the congruence by \({a^{p – 2}}\), (M1)
\({a^{p – 1}}x \equiv {a^{p – 2}}b(\bmod p)\) A1
\(x \equiv {a^{p – 2}}b(\bmod p)\) AG
[4 marks]
(b) (i) the solution is
\(x \equiv {7^{17}} \times 13(\bmod 19)\) A1
consider
\({7^3} = 343 \equiv 1(\bmod 19)\) (A1)
Note: Other powers are possible.
therefore
\(x \equiv {\left( {{7^3}} \right)^5} \times {7^2} \times 13(\bmod 19)\) (A1)
\( \equiv {7^2} \times 13(\bmod 19)\) (A1)
\( \equiv 10(\bmod 19)\) A1
(ii) using any method, including trial and error, the solution to the second congruence is given by \(x \equiv 32(\bmod 7)\) (or equivalent) (A1)
a simultaneous solution is \(x = 67\) (or equivalent, eg \(-66\)) A1
the full solution is \(x = 67 + 133N\) (where \(N \in \mathbb{Z}\)) (or equivalent) A1
Note: Do not FT an incorrect answer from (i).
[8 marks]
Question
Consider the linear congruence \(ax \equiv b(\bmod p)\) where \(a,{\text{ }}b \in {\mathbb{Z}^ + },{\text{ }}p\) is a prime and \(\gcd (a,{\text{ }}p) = 1\). Using Fermat’s little theorem, show that \(x \equiv {a^{p – 2}}b(\bmod p)\).
Hence find the smallest value of \(x\) greater than 100 satisfying the linear congruence \(3x \equiv 13(\bmod 19)\).
Answer/Explanation
Markscheme
multiplying both sides by \({a^{p – 2}}\), M1
\({a^{p – 1}}x \equiv {a^{p – 2}}b(\bmod p)\) A1
using \({a^{p – 1}} \equiv 1(\bmod p)\) R1
therefore, \(x \equiv {a^{p – 2}}b(\bmod p)\) AG
[3 marks]
using the above result,
\(x \equiv {3^{17}} \times 13(\bmod 19){\text{ }}\left( { \equiv 16\,7882\,2119(\bmod 19)} \right)\) A1
\( \equiv 17(\bmod 19)\) (M1)A1
\(x = 112\) A1
[4 marks]
Question
Given that \(a \equiv b(\bmod p)\) , show that \({a^n} \equiv {b^n}(\bmod p)\) for all \(n \in {\mathbb{Z}^ + }\) .
Show that \({29^{13}} + {13^{29}}\) is exactly divisible by \(7\).
Answer/Explanation
Markscheme
\(a \equiv b(\bmod p) \Rightarrow a = b + pN,N \in \mathbb{Z}\) M1
\({a^n} = {(b + pN)^n} = {b^n} + n{b^{n – 1}}pN \ldots \) M1A1
\( = {b^n} + pM\) where \(M \in \mathbb{Z}\) A1
this shows that \({a^n} \equiv {b^n}(\bmod p)\) AG
[4 marks]
\(29 \equiv 1(\bmod 7) \Rightarrow {29^{13}} \equiv {1^{13}} \equiv 1(\bmod 7)\) M1A1
\(13 \equiv – 1(\bmod 7) \Rightarrow {13^{29}} \equiv {( – 1)^{29}} \equiv – 1(\bmod 7)\) A1
therefore \({29^{13}} + {13^{29}} \equiv 1 + ( – 1) \equiv 0(\bmod 7)\) M1A1
this shows that \({29^{13}} + {13^{29}}\) is exactly divisible by \(7\) AG
[5 marks]