What is the key fact behind the Euclidean algorithm?

hcf(a,b)=hcf(b,r) where a=bq+r.

How does the Euclidean algorithm give the hcf?

Repeat a=bq+r on divisor and remainder; the last non-zero remainder is the hcf.

What does coprime mean?

The hcf of the two integers is 1.

State Bezout's identity.

There are integers x,y with ax+by=hcf(a,b).

How do you find x and y in Bezout's identity?

Back substitution: write each remainder as a-bq and work upwards from the hcf.

When does ax+by=c have integer solutions?

If and only if hcf(a,b) divides c.

Why has 1547x+504y=10 no integer solutions?

The hcf is 7, so the left side is always a multiple of 7, and 7\nmid10.

Division theorem, Euclidean algorithm and Bezout's identityEdexcel A-Level Further Maths: Flashcards

Card 1 of 120 of 12 known

Question

State the division theorem.

Tap or press Space to reveal

Tap card or press Space to flip

See all 12 cards

State the division theorem.: For $b>0$ , $a=bq+r$ with unique integers $q,r$ and $0\leq r<b$ .
What is the key fact behind the Euclidean algorithm?: $\text{hcf}(a,b)=\text{hcf}(b,r)$ where $a=bq+r$ .
How does the Euclidean algorithm give the hcf?: Repeat $a=bq+r$ on divisor and remainder; the last non-zero remainder is the hcf.
What does coprime mean?: The hcf of the two integers is $1$ .
Formula for the lcm using the hcf?: $\text{lcm}(a,b)=\frac{ab}{\text{hcf}(a,b)}$ .
State Bezout's identity.: There are integers $x,y$ with $ax+by=\text{hcf}(a,b)$ .
How do you find $x$ and $y$ in Bezout's identity?: Back substitution: write each remainder as $a-bq$ and work upwards from the hcf.
hcf and lcm of $252$ and $198$ ?: hcf $18$ , lcm $2772$ .
Bezout combination for $240$ and $46$ ?: $2=47(46)-9(240)$ .
When does $ax+by=c$ have integer solutions?: If and only if $\text{hcf}(a,b)$ divides $c$ .
Why has $1547x+504y=10$ no integer solutions?: The hcf is $7$ , so the left side is always a multiple of $7$ , and $7\nmid10$ .
Write $252$ as $198q+r$ .: $252=1\times198+54$ .

Exam questions on Division theorem, Euclidean algorithm and Bezout's identity

Consider the integers $252$ and $198$ .
Find the lowest common multiple of $252$ and $198$ .2 marks
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.
Explain why $\text{hcf}(391,221)=\text{hcf}(221,170)$ .2 marks
Let $a=240$ and $b=46$ .
Use the Euclidean algorithm to find the highest common factor of $a$ and $b$ .3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).