Division theorem, Euclidean algorithm and Bezout's identity

Division theorem, Euclidean algorithm and Bezout's identity

Spec 5.1–2 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Division theorem: a=bq+ra=bq+r with 0≤r<b0\leq r<b, where qq is the quotient and rr the remainder.
  • Euclidean algorithm: hcf(a,b)=hcf(b,r)\text{hcf}(a,b)=\text{hcf}(b,r); the last non-zero remainder is the hcf.
  • lcm=abhcf\text{lcm}=\frac{ab}{\text{hcf}}, and integers with hcf 11 are coprime.
  • Bezout's identity: ax+by=hcf(a,b)ax+by=\text{hcf}(a,b) has integer solutions, found by back substitution.
  • ax+by=cax+by=c has integer solutions if and only if hcf(a,b)\text{hcf}(a,b) divides cc.

The division theorem

Any integer aa can be written a=bq+ra=bq+r with a unique quotient qq and remainder 0≤r<b0\leq r<b.

For integers aa and bb with b>0b>0, there are unique integers qq (the quotient) and rr (the remainder) with a=bq+ra=bq+r and 0≤r<b0\leq r<b.

Example: 252=1×198+54252=1\times198+54, so q=1q=1 and r=54r=54.

In congruence notation, a≡r(modb)a\equiv r\pmod b. Also r=0r=0 exactly when bb divides aa. The theorem is the engine of the Euclidean algorithm.

  • Division theorema=bq+r,0≤r<ba=bq+r,\quad 0\leq r<b

Write 100100 in the form 7q+r7q+r with 0≤r<70\leq r<7. What is rr?

The Euclidean algorithm

Repeat the division theorem on the divisor and remainder; the last non-zero remainder is the hcf.

The highest common factor hcf(a,b)\text{hcf}(a,b) is the largest integer dividing both.

The key fact is hcf(a,b)=hcf(b,r)\text{hcf}(a,b)=\text{hcf}(b,r): any common divisor of aa and bb divides r=a−bqr=a-bq, and any common divisor of bb and rr divides a=bq+ra=bq+r.

Repeat until the remainder is 00. Two integers with hcf 11 are coprime, and lcm=abhcf\text{lcm}=\frac{ab}{\text{hcf}}.

Write every line as a=bq+ra=bq+r in full; you need it for back substitution.

  1. 1

    Divide

    write a=bq+ra=bq+r

  2. 2

    Replace

    move on to bb and rr

  3. 3

    Repeat

    until the remainder is 0

  4. 4

    Read off

    the last non-zero remainder is the hcf

The Euclidean algorithm.

Worked example

Find hcf(252,198)\text{hcf}(252,198) and lcm(252,198)\text{lcm}(252,198).

What is hcf(48,18)\text{hcf}(48,18)?

Bezout's identity

There are always integers x,yx,y with ax+by=hcf(a,b)ax+by=\text{hcf}(a,b), found by working back up the algorithm.

Bezout's identity: for integers a,ba,b (not both zero) there exist integers x,yx,y with ax+by=hcf(a,b)ax+by=\text{hcf}(a,b).

Find xx and yy by back substitution: rearrange each step of the algorithm as r=a−bqr=a-bq, then work upwards from the line with the hcf, replacing each remainder in turn.

Keep aa and bb as unevaluated terms and collect them at the end; expanding early makes it easy to lose track of which remainder is which.

  • Bezout's identityax+by=hcf(a,b)ax+by=\text{hcf}(a,b)

Worked example

Express hcf(240,46)\text{hcf}(240,46) in the form 240x+46y240x+46y.

If hcf(a,b)=1\text{hcf}(a,b)=1, which statement must be true?

When ax + by = c is solvable

Exactly when hcf(a,b)\text{hcf}(a,b) divides cc.

Since hcf(a,b)\text{hcf}(a,b) divides ax+byax+by for all integers x,yx,y, the equation ax+by=cax+by=c has integer solutions if and only if hcf(a,b)\text{hcf}(a,b) divides cc.

If d=hcf(a,b)d=\text{hcf}(a,b) and d∣cd\mid c, multiply the Bezout solution by cd\frac cd.

In particular, aa and bb are coprime if and only if ax+by=1ax+by=1 has a solution.

To show no solution exists, state the hcf and that it does not divide cc.

hcf divides c

  • Integer solutions exist
  • Scale the Bezout solution by c/d

hcf does not divide c

  • No integer solutions

Worked example

Decide whether 1547x+504y=101547x+504y=10 and 1547x+504y=71547x+504y=7 have integer solutions.

Does 12x+18y=2012x+18y=20 have integer solutions?

Try an exam question

Use the Euclidean algorithm to find hcf(168,60)\text{hcf}(168,60), and hence find integers xx and yy such that 168x+60y=hcf(168,60)168x+60y=\text{hcf}(168,60).

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Write 252=198q+r252=198q+r with 0≤r<1980\leq r<198. Find rr.

1 mark, marked against the mark scheme

Revision notes