IB DP Maths Topic 10.4 The solution of linear congruences HL Paper 3

Question

Convert the decimal number 51966 to base 16.

[4]
a.

(i)     Using the Euclidean algorithm, find the greatest common divisor, d , of 901 and 612.

(ii)     Find integers p and q such that 901p + 612q = d .

(iii)     Find the least possible positive integers s and t such that 901s − 612t = 85.

[10]
b.

In each of the following cases find the solutions, if any, of the given linear congruence.

(i)     $$9x \equiv 3(\bmod 18)$$

(ii)     $$9x \equiv 3(\bmod 15)$$

[5]
c.

Markscheme

the relevant powers of 16 are 16, 256 and 4096

then

$$51966 = 12 \times 4096{\text{ remainder }}2814$$     M1A1

$$2814 = 10 \times 256{\text{ remainder }}254$$

$$254 = 15 \times 16{\text{ remainder }}14$$     A1

the hexadecimal number is CAFE     A1

Note: CAFE is produced using a standard notation, accept explained alternative notations.

[4 marks]

a.

(i)     using the Euclidean Algorithm     (M1)

$$901 = 612 + 289$$     (A1)

$$612 = 2 \times 289 + 34$$

$$289 = 8 \times 34 + 17$$

$$\gcd (901,{\text{ }}612) = 17$$     A1

(ii)     working backwards     (M1)

$$17 = 289 – 8 \times 34$$

$$= 289 – 8 \times (612 – 2 \times 289)$$

$$= 17 \times (901 – 612) – 8 \times 612$$

$$= 27 \times 901 – 25 \times 612$$

$${\text{so }}p = 17,{\text{ }}q = – 25$$     A1A1

(iii)     a particular solution is

$$s = 5p = 85,{\text{ }}t = – 5q = 125$$     (A1)

the general solution is

$$s = 85 + 36\lambda ,{\text{ }}t = 125 + 53\lambda$$     M1A1

by inspection the solution satisfying all conditions is

$$(\lambda = – 2),{\text{ }}s = 13,{\text{ }}t = 19$$     A1

[10 marks]

b.

(i)     the congruence is equivalent to $$9x = 3 + 18\lambda$$     (A1)

this has no solutions as 9 does not divide the RHS     R1

(ii)     the congruence is equivalent to $$3x = 1 + 5\lambda ,{\text{ }}\left( {3x \equiv 1(\bmod 5)} \right)$$     A1

one solution is $$x = 2$$ , so the general solution is $$x = 2 + 5n\,\,\,\,\,\left( {x \equiv 2(\bmod 5)} \right)$$     M1A1

[5 marks]

c.

Examiners report

Many did not seem familiar with hexadecimal notation and often left their answer as 12101514 instead of CAFE.

a.

The Euclidean algorithm was generally found to be easy to deal with but getting a general solution in part (iii) eluded many candidates.

b.

Rewriting the congruence in the form $$9x = 3 + 18\lambda$$ for example was not often seen but should have been the first thing thought of.

c.

Question

Use the Euclidean algorithm to express gcd (123, 2347) in the form 123p + 2347q, where $$p,{\text{ }}q \in \mathbb{Z}$$.

[8]
a.

Find the least positive solution of $$123x \equiv 1(\bmod 2347)$$ .

[3]
b.

Find the general solution of $$123z \equiv 5(\bmod 2347)$$ .

[3]
c.

State the solution set of $$123y \equiv 1(\bmod 2346)$$ .

[1]
d.

Markscheme

$$2347 = 19 \times 123 + 10$$     M1A1

$$(123 = 12 \times 10 + 3)$$

$$10 = 3 \times 3 + 1$$     A1

$$1(\gcd ) = 10 – 3 \times 3 = 10 – 3 \times (123 – 12 \times 10)$$     M1A1

$$= 37 \times 10 – 3 \times 123$$     A1

$$= 37 \times (2347 – 19 \times 123) – 3 \times 123$$ (for continuation)     M1

$$= 37 \times 2347 – 706 \times 123$$     A1

[8 marks]

a.

EITHER

$$1(\bmod 2347) = ( – 706 \times 123)(\bmod 2347)$$     M1A1

OR

$$x = – 706 + 2347n$$     M1A1

solution: 1641     A1

[3 marks]

b.

$$5(\bmod 2347) = ( – 3530 \times 123)(\bmod 2347)$$     (M1)

$${\text{GS}}:z = – 3530 + k2347$$     A1A1

Note: Other common possibilities include $$1164 + k2347$$ and $$8205 + k2347$$ .

[3 marks]

c.

empty set (123 and 2346 both divisible by 3)     A1

[1 mark]

d.

Examiners report

The majority of candidates were successful in parts (a) and (b). In part (c), some candidates failed to understand the distinction between a particular solution and a general solution. Part (d) was a 1 mark question that defeated all but the few who noticed that the gcd of the numbers concerned was 3.

a.

The majority of candidates were successful in parts (a) and (b). In part (c), some candidates failed to understand the distinction between a particular solution and a general solution. Part (d) was a 1 mark question that defeated all but the few who noticed that the gcd of the numbers concerned was 3.

b.

The majority of candidates were successful in parts (a) and (b). In part (c), some candidates failed to understand the distinction between a particular solution and a general solution. Part (d) was a 1 mark question that defeated all but the few who noticed that the gcd of the numbers concerned was 3.

c.

The majority of candidates were successful in parts (a) and (b). In part (c), some candidates failed to understand the distinction between a particular solution and a general solution. Part (d) was a 1 mark question that defeated all but the few who noticed that the gcd of the numbers concerned was 3.

d.

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

Let the greatest common divisor of 861 and 957 be h .

Using the Euclidean algorithm, find h .

[4]
a.

Hence find integers A and B such that 861+ 957B = h .

[3]
b.

Using part (b), solve $$287w \equiv 2(\bmod 319$$) , where $$w \in \mathbb{N},{\text{ }}w < 319$$ .

[5]
c.

Find the general solution to the diophantine equation $$861x + 957y = 6$$ .

[6]
d.

Markscheme

METHOD 1

by the above working on the left (or similar)     M1A1A1

Note: Award A1 for 96 and A1 for 93.

h = 3 (since 3 divides 93)     A1

[4 marks]

METHOD 2

$$957 = 861 + 96$$     M1A1

$$861 = 8 \times 96 + 93$$     A1

$$96 = 93 + 3$$

so h = 3 (since 3 divides 93)     A1

[4 marks]

a.

METHOD 1

if method 1 was used for part (a)

by the above working on the right (or equivalent)     M1

$$– 10 \times 861 + 9 \times 957 = 3$$

so A = –10 and B = 9     A1A1

[3 marks]

METHOD 2

$$3 = 96 – 93$$

$$= 96 – (861 – 8 \times 96) = 9 \times 96 – 861$$     M1

$$= 9 \times (957 – 861) – 861$$

$$= – 10 \times 861 + 9 \times 957$$

so A = –10 and B = 9     A1A1

[3 marks]

b.

from (b) $$– 10 \times 287 + 9 \times 319 = 1$$ so     A1

$$– 10 \times 287 \equiv 1(\bmod 319)$$     A1

$$287w \equiv 2(\bmod 319) \Rightarrow – 10 \times 287w \equiv – 10 \times 2(\bmod 319)$$     M1

$$\Rightarrow w \equiv – 20(\bmod 319)$$     A1

so $$w = 299$$     A1

[5 marks]

c.

from (b) $$– 10 \times 861 + 9 \times 957 = 3 \Rightarrow – 20 \times 861 + 18 \times 957 = 6$$     M1A1

so general solution is $$x = – 20 + 319t$$     A1A1

$$y = 18 – 287t\,\,\,\,\,(t \in \mathbb{Z})$$     A1A1

[6 marks]

d.

Examiners report

The Euclidean algorithm was well applied. If it is done in the format shown in the mark scheme then the keeping track method of the linear combinations of the 2 original numbers makes part (b) easier.

a.

Again well answered but not quite as good as (a).

b.

Surprisingly, since it is basic bookwork, this part was answered very badly indeed. Most candidates did not realise that $$– 10$$ was the number to multiply by. Sadly, of the candidates that did do it, some did not read the question carefully enough to see that a positive integer answer was required.

c.

Again this is standard bookwork. It was answered better than part (c). There were the usual mistakes in the final answer e.g. not having the two numbers, with the parameter, co-prime.

d.

Question

Using the Euclidean algorithm, show that $$\gcd (99,{\text{ }}332) = 1$$.

[4]
a.

(i)     Find the general solution to the diophantine equation $$332x – 99y = 1$$.

(ii)     Hence, or otherwise, find the smallest positive integer satisfying the congruence $$17z \equiv 1(\bmod 57)$$.

[11]
b.

Markscheme

using the Euclidean Algorithm,

$$332 = 3 \times 99 + 35{\text{ }}$$     M1

$$99 = 2 \times 35 + 29$$     A1

$$35 = 1 \times 29 + 6$$

$$29 = 4 \times 6 + 5$$     A1

$$6 = 1 \times 5 + 1$$     A1

hence 332 and 99 have a gcd of 1     AG

Note: For both (a) and (b) accept layout in tabular form, especially the brackets method of keeping track of the linear combinations as the method proceeds.

[4 marks]

a.

(i)     working backwards,     (M1)

$$6 – 5 = 1$$

$$6 – (29 – 4 \times 6) = 1{\text{ or }}5 \times 6 – 29 = 1$$     A1

$$5 \times (35-29)-29 = 1{\text{ or }}5 \times 35-6 \times 29 = 1$$     A1

$$5 \times 35-6 \times (99-2 \times 35) = 1{\text{ or }}17 \times 35-6 \times 99 = 1$$

$$17 \times (332-3 \times 99)-6 \times 99 = 1{\text{ or }}17 \times 332-57 \times 99 = 1$$     A1

a solution to the Diophantine equation is therefore

$$x = 17,{\text{ }}y = 57$$     (A1)

the general solution is

$$x = 17 + 99N,{\text{ }}y = 57 + 332N$$     A1A1

Note: If part (a) is wrong it is inappropriate to give FT in (b) as the numbers will contradict, however the M1 can be given.

(ii)     it follows from previous work that

$$17 \times 332 = 1 + 99 \times 57$$     (M1)

$$\equiv 1(\bmod 57)$$     (A1)

z = 332 is a solution to the given congruence     (A1)

the general solution is 332 + 57N so the smallest solution is 47     A1

[11 marks]

b.

Examiners report

Part (a) was well answered and (b) fairly well answered. There were problems with negative signs due to the fact that there was a negative in the question, so candidates had to think a little, rather than just remembering formulae by rote. The lay-out of the algorithm that keeps track of the linear combinations of the first 2 variables is recommended to teachers.

a.

Part (a) was well answered and (b) fairly well answered. There were problems with negative signs due to the fact that there was a negative in the question, so candidates had to think a little, rather than just remembering formulae by rote. The lay-out of the algorithm that keeps track of the linear combinations of the first 2 variables is recommended to teachers.

b.

Question

Consider the linear congruence $$ax \equiv b\left( {{\text{mod}}\,p} \right)$$ where $$a,\,b,\,p,\,x \in {\mathbb{Z}^ + }$$, $$p$$ is prime and $$a$$ is not a multiple of $$p$$.

State Fermat’s little theorem.

[2]
a.

Use Fermat’s little theorem to show that $$x \equiv {a^{p – 2}}b\left( {{\text{mod}}\,p} \right)$$.

[3]
b.i.

Hence solve the linear congruence $$5x \equiv 7\left( {{\text{mod}}\,13} \right)$$.

[3]
b.ii.

Markscheme

EITHER

if $$p$$ is prime (and $$a$$ is any integer) then $${a^p} \equiv a\left( {{\text{mod}}\,p} \right)$$    A1A1

Note: Award A1 for $$p$$ prime and A1 for the congruence or for stating that $$p\left| {{a^p} – a} \right.$$.

OR

A1A1

Note: Award A1 for $$p$$ prime and A1 for the congruence or for stating that $$p\left| {{a^{p – 1}} – 1} \right.$$.

Note: Condone use of equals sign provided $$\left( {{\text{mod}}\,p} \right)$$ is seen.

[2 marks]

a.

multiplying both sides of the linear congruence by $${a^{p – 2}}$$     (M1)

$${a^{p – 1}}x \equiv {a^{p – 2}}b\left( {{\text{mod}}\,p} \right)$$      A1

as $${a^{p – 1}} \equiv 1\left( {{\text{mod}}\,p} \right)$$     R1

$$x \equiv {a^{p – 2}}b\left( {{\text{mod}}\,p} \right)$$     AG

[3 marks]

b.i.

$$x \equiv {5^{11}} \times 7\left( {{\text{mod}}\,13} \right)$$     (M1)

$$\equiv 341796875\left( {{\text{mod}}\,13} \right)$$     (A1)

Note: Accept equivalent calculation eg, using $${5^2} \equiv – 1\,{\text{mod}}\,13$$.

$$\equiv 4\left( {{\text{mod}}\,13} \right)$$     A1

[3 marks]

b.ii.

[N/A]

a.

[N/A]

b.i.

[N/A]

b.ii.