Loading [MathJax]/jax/output/CommonHTML/fonts/TeX/fontdata.js

User interface language: English | Español

Date May 2016 Marks available 4 Reference code 16M.3dm.hl.TZ0.1
Level HL only Paper Paper 3 Discrete mathematics Time zone TZ0
Command term Show that Question number 1 Adapted from N/A

Question

Use the Euclidean algorithm to show that 1463 and 389 are relatively prime.

[4]
a.

Find positive integers a and b such that 1463a389b=1.

[5]
b.

Markscheme

1463=3×389+296    M1A1

389=1×296+93

296=3×93+17    A1

93=5×17+8

17=2×8+1 which shows that the gcd is 1     A1

hence 1463 and 389 are relatively prime     AG

[4 marks]

a.

EITHER

1=172×8    (M1)

=172×(935×17)=11×172×93    (A1)

=11×(2963×93)2×93=11×29635×93    (A1)

=11×29635×(389296)=46×29635×389

=46×(14633×389)35×389    (A1)

=46×1463173×389    A1

(a=46, b=173)

OR

method of keeping track of the linear combinations from the beginning (could be seen alongside the working in (a))

(1, 0)   (0, 1)
    3(1, 0)
    (3, 1)

     (M1)(A1)

(3, 1)    
(4, 1)    
    3(4, 1)
    (15, 4)

     (A1)

5(15, 4)

(79, 21)    (A1)

    2(79, 21)
               (173, 46)

so 173×389+46×1463=1 giving 46×1463173×389=1     A1

(a=46, b=173)

 

Note:     Accept any positive answers of the form a=46+389t, b=173+1463t, t an integer.

 

[5 marks]

b.

Examiners report

Very well answered. Some candidates lost the final mark by not saying that their working showed that the greatest common divisor (gcd) was 1.

a.

The working backwards method was generally well known but there were arithmetic mistakes. Some candidates did not realise that their aim was to keep 1 as a combination of two remainders. The final answer could have been checked with the calculator as could intermediary steps. What was sadly less well known was the linear combinations format of laying the work out. See the OR method in the mark scheme. This makes the numerical work much less tedious and deserves to be better known.

b.

Syllabus sections

Topic 10 - Option: Discrete mathematics
Show 214 related questions

View options