Download IITian Academy App for accessing Online Mock Tests and More..
Question
Two mathematicians are planning their wedding celebration and are trying to arrange the seating plan for the guests. The only restriction is that all tables must seat the same number of guests and each table must have more than one guest. There are fewer than 350 guests, but they have forgotten the exact number. However they remember that when they try to seat them with two at each table there is one guest left over. The same happens with tables of 3, 4, 5 and 6 guests. When there were 7 guests per table there were none left over. Find the number of guests.
Answer/Explanation
Markscheme
let x be the number of guests
\(x \equiv 1(\bmod 2)\)
\(x \equiv 1(\bmod 3)\)
\(x \equiv 1(\bmod 4)\)
\(x \equiv 1(\bmod 5)\)
\(x \equiv 1(\bmod 6)\)
\(x \equiv 0(\bmod 7)\) congruence (i) (M1)(A2)
the equivalent of the first five lines is
\(x \equiv 1\left( {\bmod ({\text{lcm of 2, 3, 4, 5, 6}})} \right) \equiv 1(\bmod 60)\) A1
\( \Rightarrow x = 60t + 1\)
from congruence (i) \(60t + 1 \equiv 0(\bmod 7)\) M1A1
\(60t \equiv – 1(\bmod 7)\)
\(60t \equiv 6(\bmod 7)\)
\(4t \equiv 6(\bmod 7)\)
\(2t \equiv 3(\bmod 7)\) A1
\( \Rightarrow t = 7u + 5\,\,\,\,\,{\text{(or equivalent)}}\) A1
hence \(x = 420u + 300 + 1\) A1
\( \Rightarrow x = 420u + 301\)
smallest number of guests is 301 A1 N6
Note: Accept alternative correct solutions including exhaustion or formula from Chinese remainder theorem.
[10 marks]
Examiners report
There were a number of totally correct solutions to this question, but many students were unable to fully justify the result. Some candidates had learnt a formula to apply to the Chinese remainder theorem, but could not apply it well in this situation. Many worked with the conditions for divisibility but did not make much progress with the justification.
Question
Question
(i) One version of Fermat’s little theorem states that, under certain conditions,
\[{a^{p – 1}} \equiv 1(\bmod p).\]
Show that this result is not valid when a = 4, p = 9 and state which
condition is not satisfied.
(ii) Given that \({5^{64}} \equiv n(\bmod 7)\), where \(0 \leqslant n \leqslant 6\), find the value of n.
Find the general solution to the simultaneous congruences
\[x \equiv 3(\bmod 4)\]
\[3x \equiv 2(\bmod 5).\]
▶️Answer/Explanation
Markscheme
(i) \({4^8} = 65536 \equiv 7(\bmod 9)\) A1
not valid because 9 is not a prime number R1
Note: The R1 is independent of the A1.
(ii) using Fermat’s little theorem M1
\({5^6} \equiv 1(\bmod 7)\) A1
therefore
\({({5^6})^{10}} = {5^{60}} \equiv 1(\bmod 7)\) A1
also, \({5^4} = 625\) M1
\( \equiv 2(\bmod 7)\) A1
therefore
\({5^{64}} \equiv 1 \times 2 \equiv 2(\bmod 7)\,\,\,\,\,{\text{(so }}n = 2)\) A1
Note: Accept alternative solutions not using Fermat.
[8 marks]
EITHER
solutions to \(x \equiv 3(\bmod 4)\) are
3, 7, 11, 15, 19, 23, 27, … A1
solutions to \(3x \equiv 2(\bmod 5).\) are
4, 9, 14, 19 … (M1)A1
so a solution is x =19 A1
using the Chinese remainder theorem (or otherwise) (M1)
the general solution is \(x = 19 + 20n{\text{ }}(n \in \mathbb{Z})\) A1
\(\left( {{\text{accept }}19(\bmod 20)} \right)\)
OR
\(x = 3 + 4t \Rightarrow 9 + 12t \equiv 2(\bmod 5)\) M1A1
\( \Rightarrow 2t \equiv 3(\bmod 5)\) A1
\( \Rightarrow 6t \equiv 9(\bmod 5)\)
\( \Rightarrow t \equiv 4(\bmod 5)\) A1
so \(t = 4 + 5n{\text{ and }}x = 19 + 20n{\text{ }}(n \in \mathbb{Z})\) M1A1
\(\left( {{\text{accept }}19(\bmod 20)} \right)\)
Note: Also accept solutions done by formula.
[6 marks]
Examiners report
Part (a) was generally well answered with a variety of methods seen in (a)(ii). This was set with Fermat’s Little Theorem in mind but in the event many candidates started off with many different powers of 5, eg \({5^4} \equiv 2,{\text{ }}{5^8} \equiv 4\) and \({5^3}\equiv- 1(\bmod 7)\) were all seen. A variety of methods was also seen in (b), ranging from use of the Chinese Remainder Theorem, finding tables of numbers congruent to \(3(\bmod 4)\)and \(4(\bmod 5)\) and the use of an appropriate formula.
Part (a) was generally well answered with a variety of methods seen in (a)(ii). This was set with Fermat’s Little Theorem in mind but in the event many candidates started off with many different powers of 5, eg \({5^4} \equiv 2,{\text{ }}{5^8} \equiv 4\) and \({5^3}\equiv – 1(\bmod 7)\) were all seen. A variety of methods was also seen in (b), ranging from use of the Chinese Remainder Theorem, finding tables of numbers congruent to \(3(\bmod 4)\)and \(4(\bmod 5)\) and the use of an appropriate formula.
Question
(a) Find the general solution for the following system of congruences.
\(N \equiv 3(\bmod 11)\)
\(N \equiv 4(\bmod 9)\)
\(N \equiv 0(\bmod 7)\)
(b) Find all values of N such that \(2000 \leqslant N \leqslant 4000\).
▶️Answer/Explanation
Markscheme
(a) \(N = 3 + 11t\) M1
\(3 + 11t \equiv 4(\bmod 9)\)
\(2t \equiv 1(\bmod 9)\) (A1)
multiplying by 5, \(10t \equiv 5(\bmod 9)\) (M1)
\(t \equiv 5(\bmod 9)\) A1
\(t = 5 + 9s\) M1
\(N = 3 + 11(5 + 9s)\)
\(N = 58 + 99s\) A1
\(58 + 99s \equiv 0(\bmod 7)\)
\(2 + s \equiv 0(\bmod 7)\)
\(s \equiv 5(\bmod 7)\) A1
\(s = 5 + 7u\) M1
\(N = 58 + 99(5 + 7u)\)
\(N = 553 + 693u\) A1
Note: Allow solutions that are done by formula or an exhaustive, systematic listing of possibilities.
[9 marks]
(b) u = 3 or 4
hence N = 553 + 2079 = 2632 or N = 553 + 2772 = 3325 A1A1
[2 marks]
Total [11 marks]
Examiners report
This was a standard Chinese remainder theorem problem that many candidates gained good marks on. Some candidates employed a formula, which was fine if they remembered it correctly (but not all did), although it did not always show good understanding of the problem.
Question
a.Solve, by any method, the following system of linear congruences
\(x \equiv 9(\bmod 11)\)
\(x \equiv 1(\bmod 5)\)[3]
b.Find the remainder when \({41^{82}}\) is divided by 11.[4]
c.Using your answers to parts (a) and (b) find the remainder when \({41^{82}}\) is divided by \(55\).[3]
▶️Answer/Explanation
Markscheme
METHOD 1
listing \(9,{\rm{ }}20,{\rm{ }}31\), \( \ldots \) and \(1,{\rm{ }}6,11,16,{\rm{ }}21,{\rm{ }}26,{\rm{ }}31\), \( \ldots \) M1
one solution is \(31\) (A1)
by the Chinese remainder theorem the full solution is
\(x \equiv 31(\bmod 55)\) A1 N2
METHOD 2
\(x \equiv 9(\bmod 11) \Rightarrow x = 9 + 11t\) M1
\( \Rightarrow 9 + 11t \equiv 1(\bmod 5)\)
\( \Rightarrow t \equiv 2(\bmod 5)\) A1
\( \Rightarrow t = 2 + 5s\)
\( \Rightarrow x = 9 + 11(2 + 5s)\)
\( \Rightarrow x = 31 + 55s{\text{ }}\left( { \Rightarrow x \equiv 31(\bmod 55)} \right)\) A1
Note: Accept other methods eg formula, Diophantine equation.
Note: Accept other equivalent answers e.g. \( – 79(\bmod 55)\).
[3 marks]
\({41^{82}} \equiv {8^{82}}(\bmod 11)\)
by Fermat’s little theorem \({8^{10}} \equiv 1(\bmod 11)\;\;\;\left( {{\text{or }}{{41}^{10}} \equiv 1(\bmod 11)} \right)\) M1
\({8^{82}} \equiv {8^2}(\bmod 11)\) M1
\( \equiv 9(\bmod 11)\) (A1)
remainder is \(9\) A1
Note: Accept simplifications done without Fermat.
[4 marks]
\({41^{82}} \equiv {1^{82}} \equiv 1(\bmod 5)\) A1
so \({41^{82}}\) has a remainder \(1\) when divided by \(5\) and a remainder \(9\) when divided by \(11\) R1
hence by part (a) the remainder is \(31\) A1
[3 marks]
Total [10 marks]
Examiners report
A variety of methods were used here. The Chinese Remainder Theorem method (Method 2 on the mark-scheme) is probably the most instructive. Candidates who tried to do it by formula often (as usual) made mistakes and got it wrong. Marks were lost by just saying 31 and not giving mod (55).
Time was lost here by not using Fermat’s Little Theorem as a starting point, although the ad hoc methods will work.
Although it said use parts (a) and (b) not enough candidates saw the connection.
Question
b.One version of Fermat’s little theorem states that, under certain conditions, \({a^{p – 1}} \equiv 1(\bmod p)\) .
(i) Show that this result is not true when a = 2, p = 9 and state which of the conditions is not satisfied.
(ii) Find the smallest positive value of k satisfying the congruence \({2^{45}} \equiv k(\bmod 9)\) .[6]
b.Find all the integers between 100 and 200 satisfying the simultaneous congruences \(3x \equiv 4(\bmod 5)\) and \(5x \equiv 6(\bmod 7)\) .[6]
▶️Answer/Explanation
Markscheme
(i) \({2^8} = 256 \equiv 4(\bmod 9)\) (so not true) A1
9 is not prime A1
(ii) consider various powers of 2, e.g. obtaining M1
\({2^6} = 64 \equiv 1(\bmod 9)\) A1
therefore
\({2^{45}} = {({2^6})^7} \times {2^3}\) M1
\( \equiv 8(\bmod 9){\text{ (so }}k = 8)\) A1
[6 marks]
EITHER
the solutions to \(3x \equiv 4(\bmod 5)\) are 3, 8, 13, 18, 23,… M1A1
the solutions to \(5x \equiv 6(\bmod 7)\) are 4, 11, 18,… A1
18 is therefore the smallest solution A1
the general solution is
\(18 + 35n{\text{ , }}n \in \mathbb{Z}\) M1
the required solutions are therefore 123, 158, 193 A1
OR
\(3x \equiv 4(\bmod 5) \Rightarrow 2 \times 3x \equiv 2 \times 4(\bmod 5) \Rightarrow x \equiv 3(\bmod 5)\) A1
\( \Rightarrow x = 3 + 5t\) M1
\( \Rightarrow 15 + 25t \equiv 6(\bmod 7) \Rightarrow 4t \equiv 5(\bmod 7) \Rightarrow 2 \times 4t \equiv 2 \times 5(\bmod 7) \Rightarrow t \equiv 3(\bmod 7)\) A1
\( \Rightarrow t = 3 + 7n\) A1
\( \Rightarrow x = 3 + 5(3 + 7n) = 18 + 35n\) M1
the required solutions are therefore 123, 158, 193 A1
OR
using the Chinese remainder theorem formula method
first convert the congruences to \(x \equiv 3(\bmod 5)\) and \(x \equiv 4(\bmod 7)\) A1A1
\(M = 35{\text{, }}{M_1} = 7{\text{, }}{M_2} = 5{\text{, }}{m_1} = 5,{\text{ }}{m_2} = 7,{\text{ }}{a_1} = 3,{\text{ }}{a_2} = 4\)
\({x_1}\) is the solution of \({M_2}{x_2} \equiv 1(\bmod {m_1})\) , i.e. \(7{x_1} \equiv 1(\bmod 5)\) so \({x_1} = 3\)
\({x_2}\) is the solution of \({M_2}{x_2} \equiv 1(\bmod {m_2})\) , i.e. \(5{x_2} \equiv 1(\bmod 7)\) so \({x_2} = 3\)
a solution is therefore
\(x = {a_1}{M_1}{x_1} + {a_2}{M_2}{x_2}\) M1
\( = 3 \times 7 \times 3 + 4 \times 5 \times 3 = 123\) A1
the general solution is \(123 + 35n\) , \(n \in \mathbb{Z}\) M1
the required solutions are therefore 123, 158, 193 A1
[6 marks]
Examiners report
[N/A]
[N/A]
Question
b.One version of Fermat’s little theorem states that, under certain conditions, \({a^{p – 1}} \equiv 1(\bmod p)\) .
(i) Show that this result is not true when a = 2, p = 9 and state which of the conditions is not satisfied.
(ii) Find the smallest positive value of k satisfying the congruence \({2^{45}} \equiv k(\bmod 9)\) .[6]
b.Find all the integers between 100 and 200 satisfying the simultaneous congruences \(3x \equiv 4(\bmod 5)\) and \(5x \equiv 6(\bmod 7)\) .[6]
▶️Answer/Explanation
Markscheme
(i) \({2^8} = 256 \equiv 4(\bmod 9)\) (so not true) A1
9 is not prime A1
(ii) consider various powers of 2, e.g. obtaining M1
\({2^6} = 64 \equiv 1(\bmod 9)\) A1
therefore
\({2^{45}} = {({2^6})^7} \times {2^3}\) M1
\( \equiv 8(\bmod 9){\text{ (so }}k = 8)\) A1
[6 marks]
EITHER
the solutions to \(3x \equiv 4(\bmod 5)\) are 3, 8, 13, 18, 23,… M1A1
the solutions to \(5x \equiv 6(\bmod 7)\) are 4, 11, 18,… A1
18 is therefore the smallest solution A1
the general solution is
\(18 + 35n{\text{ , }}n \in \mathbb{Z}\) M1
the required solutions are therefore 123, 158, 193 A1
OR
\(3x \equiv 4(\bmod 5) \Rightarrow 2 \times 3x \equiv 2 \times 4(\bmod 5) \Rightarrow x \equiv 3(\bmod 5)\) A1
\( \Rightarrow x = 3 + 5t\) M1
\( \Rightarrow 15 + 25t \equiv 6(\bmod 7) \Rightarrow 4t \equiv 5(\bmod 7) \Rightarrow 2 \times 4t \equiv 2 \times 5(\bmod 7) \Rightarrow t \equiv 3(\bmod 7)\) A1
\( \Rightarrow t = 3 + 7n\) A1
\( \Rightarrow x = 3 + 5(3 + 7n) = 18 + 35n\) M1
the required solutions are therefore 123, 158, 193 A1
OR
using the Chinese remainder theorem formula method
first convert the congruences to \(x \equiv 3(\bmod 5)\) and \(x \equiv 4(\bmod 7)\) A1A1
\(M = 35{\text{, }}{M_1} = 7{\text{, }}{M_2} = 5{\text{, }}{m_1} = 5,{\text{ }}{m_2} = 7,{\text{ }}{a_1} = 3,{\text{ }}{a_2} = 4\)
\({x_1}\) is the solution of \({M_2}{x_2} \equiv 1(\bmod {m_1})\) , i.e. \(7{x_1} \equiv 1(\bmod 5)\) so \({x_1} = 3\)
\({x_2}\) is the solution of \({M_2}{x_2} \equiv 1(\bmod {m_2})\) , i.e. \(5{x_2} \equiv 1(\bmod 7)\) so \({x_2} = 3\)
a solution is therefore
\(x = {a_1}{M_1}{x_1} + {a_2}{M_2}{x_2}\) M1
\( = 3 \times 7 \times 3 + 4 \times 5 \times 3 = 123\) A1
the general solution is \(123 + 35n\) , \(n \in \mathbb{Z}\) M1
the required solutions are therefore 123, 158, 193 A1
[6 marks]
Examiners report
[N/A]
[N/A]