IB DP Maths Topic 10.4 Solution of simultaneous linear congruences (Chinese remainder theorem) HL Paper 3

Question

(i)     Given that $$a \equiv d(\bmod n)$$ and $$b \equiv c(\bmod n)$$ prove that

$(a + b) \equiv (c + d)(\bmod n){\text{ .}}$

(ii)     Hence solve the system

$\left\{ {\begin{array}{*{20}{r}} {2x + 5y \equiv 1(\bmod 6)} \\ {x + y \equiv 5(\bmod 6)} \end{array}} \right.$

[11]
a.

Show that $${x^{97}} – x + 1 \equiv 0(\bmod 97)$$ has no solution.

[3]
b.

Markscheme

(i)     $$a \equiv d(\bmod n){\text{ and }}b \equiv c(\bmod n)$$

so $$a – d = pn{\text{ and }}b – c = qn$$ ,     M1A1

$$a – d + b – c = pn + qn$$

$$(a + b) – (c + d) = n(p + q)$$     A1

$$(a + b) \equiv (c + d)(\bmod n)$$     AG

(ii)     $$\left\{ {\begin{array}{*{20}{r}} {2x + 5y \equiv 1(\bmod 6)} \\ {x + y \equiv 5(\bmod 6)} \end{array}} \right.$$

adding $$3x + 6y \equiv 0(\bmod 6)$$     M1

$$6y \equiv 0(\bmod 6){\text{ so }}3x \equiv 0(\bmod 6)$$     R1

$$x \equiv 0{\text{ or }}x \equiv 2{\text{ or }}x \equiv 4(\bmod 6)$$     A1A1A1

for $$x \equiv 0,{\text{ }}0 + y \equiv 5(\bmod 6){\text{ so }}y \equiv 5(\bmod 6)$$     A1

for $$x \equiv 2,{\text{ }}2 + y \equiv 5(\bmod 6){\text{ so }}y \equiv 3(\bmod 6)$$     A1

If $$x \equiv 4(\bmod 6),{\text{ }}4 + y \equiv 5(\bmod 6){\text{ so }}y \equiv 1(\bmod 6)$$     A1

[11 marks]

a.

Suppose x is a solution

97 is prime so $${x^{97}} \equiv x(\bmod 97)$$     M1

$${x^{97}} – x \equiv 0(\bmod 97)$$     A1

$${x^{97}} – x + 1 \equiv 1 \ne 0(\bmod 97)$$

Hence there are no solutions     R1

[3 marks]

b.

Examiners report

Part (a) (i) was not found difficult but using it in part (a)(ii) resulted in two or three correct lines and then abandonment of the problem.

a.

Part (a) (i) was not found difficult but using it in part (a)(ii) resulted in two or three correct lines and then abandonment of the problem.

b.

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.

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

(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.

[8]
a.

Find the general solution to the simultaneous congruences

$x \equiv 3(\bmod 4)$

$3x \equiv 2(\bmod 5).$

[6]
b.

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]

a.

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]

b.

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.

a.

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.

b.

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$$.

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

Use the result $$2003 = 6 \times 333 + 5$$ and Fermat’s little theorem to show that $${2^{2003}} \equiv 4(\bmod 7)$$ .

[3]
a.

Find $${2^{2003}}(\bmod 11)$$ and $${2^{2003}}(\bmod 13)$$.

[3]
b.

Use the Chinese remainder theorem, or otherwise, to evaluate $${2^{2003}}(\bmod 1001)$$, noting that $$1001 = 7 \times 11 \times 13$$.

[7]
c.

Markscheme

$${2^{2003}} = {2^5} \times {({2^6})^{333}}$$     M1A1

$$\equiv 32 \times 1(\bmod 7)$$ by Fermat’s little theorem     A1

$$\equiv 4(\bmod 7)$$     AG

[3 marks]

a.

$$2003 = 3 + 10 \times 200$$     (M1)

$${2^{2003}} = {2^3} \times {({2^{10}})^{200}}\left( { \equiv 8 \times 1(\bmod 11)} \right) \equiv 8(\bmod 11)$$     A1

$${2^{2003}} = {2^{11}} \times {({2^{12}})^{166}} \equiv 7(\bmod 13)$$     A1

[3 marks]

b.

form $${M_1} = \frac{{1001}}{7} = 143;{\text{ }}{M_2} = \frac{{1001}}{{11}} = 91;{\text{ }}{M_3} = \frac{{1001}}{{13}} = 77$$     M1

solve $$143{x_1} \equiv 1(\bmod 7) \Rightarrow {x_1} = 5$$     M1A1

$${x_2} = 4;{\text{ }}{x_3} = 12$$     A1A1

$$x = 4 \times 143 \times 5 + 8 \times 91 \times 4 + 7 \times 77 \times 12 = 12240 \equiv 228(\bmod 1001)$$     M1A1

[7 marks]

c.

Examiners report

Many candidates were able to complete part (a) and then went on to part (b). Some candidates raced through part (c). Others, who attempted part (c) using the alternative strategy of repeatedly solving linear congruencies, were sometimes successful.

a.

Many candidates were able to complete part (a) and then went on to part (b). Some candidates raced through part (c). Others, who attempted part (c) using the alternative strategy of repeatedly solving linear congruencies, were sometimes successful.

b.

Many candidates were able to complete part (a) and then went on to part (b). Some candidates raced through part (c). Others, who attempted part (c) using the alternative strategy of repeatedly solving linear congruencies, were sometimes successful.

c.

Question

Solve, by any method, the following system of linear congruences

$$x \equiv 9(\bmod 11)$$

$$x \equiv 1(\bmod 5)$$

[3]
a.

Find the remainder when $${41^{82}}$$ is divided by 11.

[4]
b.

Using your answers to parts (a) and (b) find the remainder when $${41^{82}}$$ is divided by $$55$$.

[3]
c.

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]

a.

$${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]

b.

$${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]

c.

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).

a.

Time was lost here by not using Fermat’s Little Theorem as a starting point, although the ad hoc methods will work.

b.

Although it said use parts (a) and (b) not enough candidates saw the connection.

c.

Question

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]
a.

Find all the integers between 100 and 200 satisfying the simultaneous congruences $$3x \equiv 4(\bmod 5)$$ and $$5x \equiv 6(\bmod 7)$$ .

[6]
b.

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]

a.

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]

b.

[N/A]

a.

[N/A]

b.