FP2 5.1, 5.2 - The Euclidean algorithm and Bezout's identity

FP2 5.1, 5.2 - The Euclidean algorithm and Bezout's identity

Use division with remainder to find highest common factors and express them as integer combinations (FP2 5.1, 5.2). You will run the Euclidean algorithm forwards, then use its own equations backwards.

Division with a controlled remainder

Two lengths measure 414414 and 186186 whole units. What is the greatest whole-number length that fits exactly into both, and can you certify your answer without listing their factors? The useful move is to keep the remainder after each division.

You already know

An integer dd divides an integer aa if a=dka=dk for some integer kk. We write d∣ad\mid a. The highest common factor of two positive integers is their greatest positive common divisor; we write it as gcd⁡(a,b)\gcd(a,b). Ordinary division and rearranging an equation are all we need to begin.

The quotient counts complete groups. The division theorem chooses a remainder in one fixed interval, so that every integer has exactly one permitted quotient–remainder pair.

The division theorem

For an integer aa and a positive integer bb, there are unique integers q,rq,r such that

a=bq+r,0≤r<ba=bq+r,\qquad 0\leq r<b

Here qq is the quotient and rr the remainder. Equivalently, q=⌊a/b⌋q=\left\lfloor a/b\right\rfloor, the greatest integer no larger than a/ba/b. Two integers have the same remainder on division by bb exactly when their difference is a multiple of bb.

Not in the formula booklet: learn it.

Why insist on that interval? If a=bq+r=bq′+r′a=bq+r=bq'+r', then b(q−q′)=r′−rb(q-q')=r'-r. The right-hand side lies strictly between −b-b and bb, so its only possible multiple of bb is 00. Thus both quotients and both remainders agree. The rule works for negative dividends too: the quotient rounds down, while the remainder stays nonnegative.

Worked example 1: a positive dividend

Question. Use the division theorem to divide 239239 by 1717.

Plan. Find consecutive multiples of 1717 surrounding 239239, then measure from the lower one.

17(14)=238,17(15)=255bounding multiples239=17(14)+1difference from the lower multiple0≤1<17permitted remainder\begin{aligned} 17(14)&=238,\qquad 17(15)=255 &&\text{bounding multiples}\\ 239&=17(14)+1 &&\text{difference from the lower multiple}\\ 0&\leq1<17 &&\text{permitted remainder} \end{aligned}

Why this step? The inequalities certify the division-theorem pair, rather than merely an equation involving 239239.

Answer. q=14, r=1q=14,\ r=1.

Check. 17(14)+1=23917(14)+1=239.

Change only the sign of the dividend. The permitted remainder interval stays exactly the same.

Worked example 2: a negative dividend

Question. Use the division theorem to divide −239-239 by 1717.

Plan. Locate the negative dividend between consecutive multiples of 1717; use the lower multiple.

17(−15)=−255,17(−14)=−238bounding multiples−239=17(−15)+16move forwards from −2550≤16<17permitted remainder\begin{aligned} 17(-15)&=-255,\qquad 17(-14)=-238 &&\text{bounding multiples}\\ -239&=17(-15)+16 &&\text{move forwards from }-255\\ 0&\leq16<17 &&\text{permitted remainder} \end{aligned}

Why this step? Writing −239=17(−14)−1-239=17(-14)-1 gives an integer equality, but its negative remainder fails the division theorem's condition.

Answer. q=−15, r=16q=-15,\ r=16.

Check. −255+16=−239-255+16=-239; also −15≤−239/17<−14-15\leq-239/17<-14.

The sign of the dividend changes the quotient, not the allowed remainder interval.

Watch out

The line −239=17(−14)−1-239=17(-14)-1 is an equality, but it is not a division-theorem answer: the remainder −1-1 is negative. Use −239=17(−15)+16-239=17(-15)+16, with 0≤16<170\leq16<17.

The diagram makes the change of quotient visible: a remainder measures forwards from the lower multiple.

[DIAGRAM: asset_name: Remainders for positive and negative dividends; asset_slug: division-positive-negative; caption: Both remainders lie between zero and seventeen, although the dividends have opposite signs.; description: Two number lines show 239 one unit after 238, and minus239 sixteen units after minus255. Each adjacent pair of multiples is seventeen units apart.]
Both remainders lie between zero and seventeen, although the dividends have opposite signs.

The remainder also prepares the language of congruences. Two integers have the same remainder on division by bb exactly when their difference is a multiple of bb: subtract their division equations for one direction, or add a multiple of bb for the other.

Run the Euclidean algorithm forwards

A long factor list is unnecessary because a division step preserves every common divisor. If a=bq+ra=bq+r, any divisor of both a,ba,b divides r=a−bqr=a-bq. Conversely, any divisor of both b,rb,r divides a=bq+ra=bq+r.

The Euclidean algorithm

For positive integers a,ba,b, if a=bq+ra=bq+r with 0≤r<b0\leq r<b, then

gcd⁡(a,b)=gcd⁡(b,r)\gcd(a,b)=\gcd(b,r)

Repeat division, replacing the pair by the divisor and remainder each time. The highest common factor is the last nonzero remainder; if the first remainder is zero, it is the original divisor.

The process stops because the nonzero remainders form a strictly decreasing sequence of positive integers.

Not in the formula booklet: learn it.

Keep the final zero-remainder line. It shows that the previous remainder divides everything left in the chain; it does not make the highest common factor zero.

Worked example 3: the common unit

Question. Use the Euclidean algorithm to determine gcd⁡(414,186)\gcd(414,186).

Plan. Divide the larger integer by the smaller, then repeatedly divide by the latest nonzero remainder.

414=2(186)+42first division186=4(42)+18replace the pair by 186,4242=2(18)+6continue18=3(6)+0stop at remainder zero\begin{aligned} 414&=2(186)+42 &&\text{first division}\\ 186&=4(42)+18 &&\text{replace the pair by }186,42\\ 42&=2(18)+6 &&\text{continue}\\ 18&=3(6)+0 &&\text{stop at remainder zero} \end{aligned} gcd⁡(414,186)=gcd⁡(186,42)=gcd⁡(42,18)=gcd⁡(18,6)=6\gcd(414,186)=\gcd(186,42)=\gcd(42,18)=\gcd(18,6)=6

Why this step? Each replacement preserves the common divisors, so the last positive remainder solves the original problem.

Answer. gcd⁡(414,186)=6\gcd(414,186)=6.

Check. 414=69(6)414=69(6) and 186=31(6)186=31(6); the algorithm certifies that no larger common divisor exists.

Reduce the first integer by just 11, keeping the second fixed. A small change in the inputs can change the entire remainder chain.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account