Division theorem, Euclidean algorithm and Bezout's identity

Division theorem, Euclidean algorithm and Bezout's identity Test

Spec 5.1–2 · Edexcel A-Level Further Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

Edexcel A-Level Further Maths

Division theorem, Euclidean algorithm and Bezout's identity

Total 27 marks

Name

Class

Date

  1. 1
    Consider the integers 252252 and 198198.
    (a)
    Write 252=198q+r252=198q+r with 0≤r<1980\leq r<198. Find rr.
    [1 mark]
    • A5454
    • B11
    • C1818
    • D3636
    Show the mark scheme

    Mark scheme

    Answer: A
    (b)
    Use the Euclidean algorithm to find the highest common factor of 252252 and 198198.
    [1 mark]
    • A66
    • B99
    • C3636
    • D1818
    Show the mark scheme

    Mark scheme

    Answer: D
    (c)
    Find the lowest common multiple of 252252 and 198198.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: lcm=252×198hcf=4989618\text{lcm}=\frac{252\times198}{\text{hcf}}=\frac{49896}{18}
    A1:
    27722772
    Accept: follow-through from their hcf in part (b)

    Total for question 1: 4 marks

  2. 2
    A florist has 391 roses and 221 lilies. She makes identical bouquets, using every flower, with each bouquet containing the same number of roses and the same number of lilies.
    (a)
    Find the largest number of bouquets she can make.
    [1 mark]
    • A5151
    • B170170
    • C1717
    • D1313
    Show the mark scheme

    Mark scheme

    Answer: C
    (b)
    How many roses are in each bouquet when she makes the largest possible number of bouquets?
    [1 mark]
    • A1313
    • B2323
    • C1717
    • D170170
    Show the mark scheme

    Mark scheme

    Answer: B
    (c)
    Explain why hcf(391,221)=hcf(221,170)\text{hcf}(391,221)=\text{hcf}(221,170).
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: any common divisor of 391 and 221 also divides 391−221=170391-221=170
    B1: any common divisor of 221 and 170 also divides
    221+170=391221+170=391, so both pairs have exactly the same common divisors
    Accept:
    391=1×221+170391=1\times221+170, so a divisor of two of the three terms divides the third

    Total for question 2: 4 marks

  3. 3
    Let a=240a=240 and b=46b=46.
    (a)
    Use the Euclidean algorithm to find the highest common factor of aa and bb.
    [3 marks]
    Show the mark scheme

    Mark scheme

    M1: division algorithm applied at least twice, 240=5(46)+10240=5(46)+10 and 46=4(10)+646=4(10)+6
    A1:
    10=1(6)+410=1(6)+4, 6=1(4)+26=1(4)+2, 4=2(2)+04=2(2)+0
    A1: hcf
    =2=2
    (b)
    Hence find integers xx and yy such that 240x+46y=2240x+46y=2.
    [4 marks]
    Show the mark scheme

    Mark scheme

    M1: start the back substitution, 2=6−42=6-4
    M1: replace
    4=10−64=10-6, 6=46−4(10)6=46-4(10) and 10=240−5(46)10=240-5(46) in turn
    A1:
    2=47(46)−9(240)2=47(46)-9(240)
    A1:
    x=−9x=-9, y=47y=47
    Accept: any valid pair
    x=−9+23kx=-9+23k, y=47−120ky=47-120k

    Total for question 3: 7 marks

  4. 4
    A rectangular patio measures 1547 cm by 504 cm. It is to be covered exactly with identical square tiles, with no tile cut.
    (a)
    Use the Euclidean algorithm to find the side length of the largest square tile that can be used. Find the number of tiles this needs.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: 1547=3(504)+351547=3(504)+35
    A1:
    504=14(35)+14504=14(35)+14 and 35=2(14)+735=2(14)+7
    A1:
    14=2(7)+014=2(7)+0, so the hcf is 77
    B1: the largest tile has side
    77 cm (the side must divide both lengths)
    M1:
    15477×5047=221×72\frac{1547}{7}\times\frac{504}{7}=221\times72
    A1:
    15 91215\,912 tiles
    (b)
    (i) Find integers xx and yy such that 1547x+504y=71547x+504y=7.
    (ii) Explain why there are no integers
    xx and yy such that 1547x+504y=101547x+504y=10.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: (i) back substitution starting 7=35−2(14)7=35-2(14)
    M1: (i) substitute
    14=504−14(35)14=504-14(35) giving 7=29(35)−2(504)7=29(35)-2(504)
    A1: (i) substitute
    35=1547−3(504)35=1547-3(504) giving 7=29(1547)−89(504)7=29(1547)-89(504)
    A1: (i)
    x=29x=29, y=−89y=-89
    Accept: any valid pair, e.g.
    x=29+72kx=29+72k, y=−89−221ky=-89-221k
    B1: (ii) hcf of
    15471547 and 504504 is 77, so 1547x+504y1547x+504y is always a multiple of 7
    R1: (ii)
    1010 is not a multiple of 77, so there is no solution

    Total for question 4: 12 marks

End of questions

Subtopic tests