Division theorem, Euclidean algorithm and Bezout's identity

Division theorem, Euclidean algorithm and Bezout's identity Flashcards

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

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

12 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

See all 12 cards
State the division theorem.
For b>0b>0, a=bq+ra=bq+r with unique integers q,rq,r and 0≤r<b0\leq r<b.
What is the key fact behind the Euclidean algorithm?
hcf(a,b)=hcf(b,r)\text{hcf}(a,b)=\text{hcf}(b,r) where a=bq+ra=bq+r.
How does the Euclidean algorithm give the hcf?
Repeat a=bq+ra=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 11.
Formula for the lcm using the hcf?
lcm(a,b)=abhcf(a,b)\text{lcm}(a,b)=\frac{ab}{\text{hcf}(a,b)}.
State Bezout's identity.
There are integers x,yx,y with ax+by=hcf(a,b)ax+by=\text{hcf}(a,b).
How do you find xx and yy in Bezout's identity?
Back substitution: write each remainder as a−bqa-bq and work upwards from the hcf.
hcf and lcm of 252252 and 198198?
hcf 1818, lcm 27722772.
Bezout combination for 240240 and 4646?
2=47(46)−9(240)2=47(46)-9(240).
When does ax+by=cax+by=c have integer solutions?
If and only if hcf(a,b)\text{hcf}(a,b) divides cc.
Why has 1547x+504y=101547x+504y=10 no integer solutions?
The hcf is 77, so the left side is always a multiple of 77, and 7∤107\nmid10.
Write 252252 as 198q+r198q+r.
252=1×198+54252=1\times198+54.

Flashcards