User interface language: English | Español

Date May 2012 Marks available 3 Reference code 12M.3dm.hl.TZ0.1
Level HL only Paper Paper 3 Discrete mathematics Time zone TZ0
Command term Find Question number 1 Adapted from N/A

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.

Syllabus sections

Topic 10 - Option: Discrete mathematics » 10.4 » Modular arithmetic.
Show 23 related questions

View options