Number Theory: The Euclidean Algorithm Example 1

1. Formula
   Observation

   Left board states Suppose $a,b \in \mathbb{N}$.

2. Audio
   Observation

   The speaker says the example is to find the gcd of two natural numbers and recalls the Euclidean algorithm for two natural numbers.

a,b

Two natural-number inputs to the Euclidean algorithm; in the worked example they are instantiated as 5295 and 4321.

Natural numbers $\mathbb{N}$

1. Formula
   Observation

   Right board header reads Ex: Find $\gcd(5295,4321)$ and left board conclusion reads $gcd(a,b)$.

2. Audio
   Observation

   The narration identifies the task as finding a greatest common divisor and recalls the last-nonzero-remainder rule.

$\gcd(a,b)$

Greatest common divisor of the two input natural numbers a and b.

Defined here for natural-number inputs

1. Formula
   Observation

   Left board displays the division-algorithm chain $a=bq_1+r_1$, $b=r_1q_2+r_2$, $r_1=r_2q_3+r_3$, ..., $r_{n-2}=r_{n-1}q_n+0$.

1. The board does not explicitly write the size condition on each remainder, although the method name “division algorithm” normally includes it.

$q_i$,$r_i$

Quotients and remainders produced by successive applications of the division algorithm in the Euclidean algorithm.

Integers/natural numbers as generated by repeated division steps

1. Formula
   Observation

   Left board conclusion line reads $r_{n-1}=gcd(a,b)$.

2. Audio
   Observation

   The narration identifies the final nonzero remainder as the output of the Euclidean algorithm.

$r_{n-1}$

The last nonzero remainder in the displayed Euclidean-algorithm chain.

Remainder appearing immediately before the final zero-remainder step

1. Formula
   Observation

   Right board header reads Ex: Find $\gcd(5295,4321)$.

2. Audio
   Observation

   The narrated example uses the positive integer pair 5295 and 4321.

5295,4321

Concrete pair of natural numbers used to illustrate the Euclidean algorithm.

Natural numbers

1. Formula
   Observation

   The board heading reads "Ex: Find $\gcd(5295, 4321)$".

2. Audio
   Observation

   The narration identifies the computed greatest common divisor as 1.

$\gcd(a,b)$

Greatest common divisor of the integers a and b.

Defined for positive integers in this example; here $a=5295$ and $b=4321$.

1. Formula
   Observation

   Left board text includes "Suppose $a,b \in \mathbb{N}$" and the division-algorithm chain starts with a and b.

2. Formula
   Observation

   Right board example uses the concrete pair 5295 and 4321.

a,b

Two natural-number inputs to the Euclidean algorithm; in the worked example they are instantiated as 5295 and 4321.

Natural numbers $\mathbb{N}$.

1. Formula
   Observation

   The left board displays $r_1$,$r_2$,$r_3$,$\ldots$,$r_{n-1}$ and a terminal remainder 0.

2. Formula
   Observation

   Right board writes successive remainders 974, 425, 124, 53, 18, 17, 1, 0.

$r_i$

The remainder produced at step i of the repeated division algorithm.

Integers satisfying $0 \le$ $r_i$ < previous divisor in each division step.

1. Formula
   Observation

   Left board shows quotients $q_1$,$q_2$,$q_3$,$\ldots$,$q_{n-1}$,$q_n$ in the equations a=bq_1+$r_1$, b=$r_1q$_2+$r_2$, etc.

2. Formula
   Observation

   Right board displays explicit quotients 1,4,2,3,2,2,1,17.

$q_i$

The quotient used at step i when dividing the current dividend by the current divisor.

Nonnegative integers in the displayed divisions.

1. Formula
   Observation

   The left board states $r_{n-1}=\gcd(a,b)$ after the displayed chain whose final remainder is 0.

1. The exact index n is not instantiated numerically on the right board; it is implicit from the last nonzero remainder.

n

Index of the final division step whose remainder is 0.

Positive integer indexing the terminating step of the algorithm.

1. Formula
   Observation

   Left board title is Euclidean Algorithm with the setup Suppose $a,b \in \mathbb{N}$, if we repeatedly perform the division algorithm: followed by the chain of equations ending in $r_{n-2}=r_{n-1}q_n+0$ and $r_{n-1}=gcd(a,b)$.

2. Audio
   Observation

   The narration recalls successive divisions and the stopping rule for the Euclidean algorithm.

1. The video states the method and conclusion but does not prove why the last nonzero remainder equals the gcd within this clip.

For the positive integer inputs illustrated here, repeated division replaces the active pair by its divisor and remainder. A zero remainder stops the process; the last nonzero value gives the gcd. Editorial boundary case: if the first division is already exact, the initial divisor is the gcd. The displayed chain illustrates the case with intermediate nonzero remainders.

1. For the positive integer inputs illustrated here, every active divisor is positive; editorial clarification: use the usual remainder bound 0 ≤ remainder < divisor.

2. The division algorithm is applied repeatedly.

3. The displayed chain ends when the remainder becomes 0.

4. The conclusion identifies the last nonzero remainder $r_{n-1}$ as $\gcd(a,b)$.

1. Successive division-algorithm equations used in the example

1. Formula
   Observation

   The left board explicitly writes the sequence $a=bq_1+r_1$, $b=r_1q_2+r_2$, $r_1=r_2q_3+r_3$, continuing down to $r_{n-2}=r_{n-1}q_n+0$.

1. The board does not separately state the usual constraint $0 \le$ $r_i$ < divisor, though the phrase “division algorithm” conventionally includes it.

Each new line divides the previous divisor by the previous remainder. The previous divisor becomes the new dividend, and the previous remainder becomes the new divisor.

1. Applies to the pair of natural numbers being reduced step by step.

2. Each equation is an instance of the division algorithm.

3. The chain terminates at a zero remainder.

1. Formula
   Observation

   Left board title reads "Euclidean Algorithm".

2. Formula
   Observation

   The left board ends its division chain with $r_{n-2}$=$r_{n-1}$$q_n$+0 and then identifies $r_{n-1}$=$\gcd(a,b)$.

3. Audio
   Observation

   Throughout the clip the instructor repeatedly applies the same pattern: bring down the previous divisor, divide by the previous remainder, write quotient plus new remainder.

The video presents the Euclidean algorithm as a sequence of division-algorithm steps. Starting with two natural numbers a and b, one repeatedly divides the previous divisor by the previous remainder until a remainder of 0 is reached. The last nonzero remainder is then identified as $\gcd(a,b)$. In the worked example, the chain is 5295, 4321, 974, 425, 124, 53, 18, 17, 1, 0, so the last nonzero remainder is 1.

1. The illustrated inputs a and b are positive integers and all intermediate divisors are nonzero (editorial scope clarification).

2. Each step uses the division algorithm with remainder less than the divisor

3. The process stops when a remainder equals 0

1. Division algorithm form used in each step
2. Greatest common divisor

1. Formula
   Observation

   Left board explicitly says "if we repeatedly perform the division algorithm" and writes equations of the form dividend = divisor $\times$ quotient + remainder.

2. Audio
   Observation

   The narration completes the third division with remainder 124, matching $974 = 2 \cdot 425 + 124$.

Each line on the board has the structure current dividend = current divisor $\times$ quotient + remainder. The example uses this repeatedly: $5295 = 1\cdot 4321 + 974$, $4321 = 4\cdot 974 + 425$, $974 = 2\cdot 425 + 124$, and so on. This is the operational rule behind the Euclidean algorithm shown here.

1. x,y are positive integers in the displayed example

2. q is the integer quotient

3. r is the remainder

1. Audio
   Observation

   The narration identifies the final nonzero remainder as the gcd, giving 1.

2. Formula
   Observation

   At 158s he writes "=1" next to the original prompt "Ex: Find $\gcd(5295,4321)$".

The greatest common divisor is the largest integer dividing both input numbers. In this clip the algorithm terminates with last nonzero remainder 1, and the instructor records $\gcd(5295,4321)=1$ on the board.

1. Inputs are the specific integers 5295 and 4321

1. Audio
   Observation

   The final narration interprets gcd 1 as the two input integers being relatively prime.

After concluding that the gcd is 1, the instructor rephrases the result by saying the two numbers are relatively prime. Thus in this video, "relatively prime" is used as the verbal equivalent of having greatest common divisor 1.

1. Applies to the pair 5295 and 4321 in this example

1. Greatest common divisor

1. Formula
   Observation

   Left board concludes $r_{n-1}=gcd(a,b)$ after writing the chain ending in $r_{n-2}=r_{n-1}q_n+0$.

2. Audio
   Observation

   The narration states that the final nonzero remainder gives the original pair's greatest common divisor.

1. This clip presents the statement as a recalled fact/method rather than proving it.

If the Euclidean algorithm is performed on natural numbers a and b by repeatedly applying the division algorithm until a zero remainder occurs, then the last nonzero remainder $r_{n-1}$ equals $\gcd(a,b)$.

1. a and b are positive integers in the displayed division chain, with nonzero intermediate divisors and the usual division-algorithm remainder bounds (editorial scope clarification).

2. The division algorithm is applied repeatedly as shown.

3. The process reaches a step with remainder 0.

For the displayed finite chain of successive divisions ending in remainder 0.

1. Formula
   Observation

   The left board states $r_{n-1}=\gcd(a,b)$ after the displayed chain whose final remainder is 0.

2. Audio
   Observation

   At 143s-157s the instructor notes that the gcd should already be obvious from reaching remainder 1, then adds one more step to obtain remainder 0 before concluding gcd=1.

If the repeated division algorithm for $a,b\in\mathbb{N}$ ends with $r_n$=0, then the preceding nonzero remainder $r_{n-1}$ equals $\gcd(a,b)$.

1. a and b are positive integers with the displayed nonzero intermediate divisors (editorial scope clarification).

2. The sequence is generated by repeated application of the division algorithm

3. The final displayed remainder is 0

For the natural numbers a and b under the displayed iterative procedure.

1. Audio
   Observation

   The narration concludes that the greatest common divisor of the input pair is 1.

2. Formula
   Observation

   At 158s the board is completed as "Ex: Find $\gcd(5295,4321)=1$".

$\gcd(5295,4321)=1$.

1. The displayed Euclidean-algorithm chain has been carried out correctly on the board

Specific claim about the two integers 5295 and 4321.

1. Audio
   Observation

   The closing narration describes the input pair as relatively prime.

The integers 5295 and 4321 are relatively prime.

1. $\gcd(5295,4321)=1$ as concluded from the worked algorithm

Specific claim about the pair (5295,4321).

1. Audio
   Observation

   The narration accompanies the two completed divisions, with quotients 1 and 4 and remainders 974 and 425, and explains carrying the prior divisor and remainder into the next line.

2. Formula
   Observation

   Right board shows $5295 = 1 \cdot 4321 + 974$ and then $4321 = 4 \cdot 974 + 425$.

3. Animation
   Observation

   After the first line is written, arrows are drawn from 4321 and 974 downward to indicate the next dividend/divisor pair.

1. Expression

   $$5295 = 1\cdot 4321 + 974$$
   Explanation

   Apply the division algorithm to the initial pair (5295,4321), obtaining quotient 1 and remainder 974.

   Justification

   Direct computation shown on the board and stated aloud.

   Shown in the video
2. Expression

   $$4321 = 4\cdot 974 + 425$$
   Explanation

   Shift downward in the Euclidean chain: the previous divisor 4321 becomes the new dividend and the previous remainder 974 becomes the new divisor, giving quotient 4 and remainder 425.

   Justification

   Matches the general pattern $b=r_1q_2+r_2$ from the left-board method and the spoken instruction to move the previous remainder into the next line.

   Shown in the video

After two Euclidean steps, the pair has been reduced from (5295,4321) to (974,425), with remainders 974 and then 425.

1. Audio
   Observation

   The narration starts the next division with dividend 974 and quotient 2; the 82-second segment ends while this line is being written.

2. Formula
   Observation

   By 01:21 the right board shows $974 = 2$ with the rest of the line not yet completed.

1. The third division is only begun in this clip; the full expression and remainder are not visible or audible before cutoff.

2. The exact continuation beyond 2 times 4... cannot be confirmed from the provided segment.

1. Expression

   $$974 = 2\cdots$$
   Explanation

   Start the next division by moving 974 to the left-hand side and beginning the quotient as 2.

   Justification

   Visible board writing and spoken setup indicate the next line of the Euclidean algorithm, but the line is incomplete in this clip.

   Shown in the video

The example proceeds to a third division step, but this clip ends before that step is completed.

1. Formula
   Observation

   The right board accumulates the full chain of divisions from 5295 down to $17=17\cdot1+0$.

2. Audio
   Observation

   The narration follows the written divisions, including completion of the third division and the final division with remainder 0.

1. The first two lines were already present at the start of the clip; only their continuation is directly observed here.

1. Expression

   $$5295 = 1\cdot 4321 + 974$$
   Explanation

   Initial division of the larger number by the smaller one.

   Justification

   Already written on the board at the start of the clip.

   Shown in the video
2. Expression

   $$4321 = 4\cdot 974 + 425$$
   Explanation

   Next division uses the previous divisor 4321 and previous remainder 974.

   Justification

   Already written on the board at the start of the clip.

   Shown in the video
3. Expression

   $$974 = 2\cdot 425 + 124$$
   Explanation

   The instructor completes the third division during this portion, obtaining remainder 124.

   Justification

   Visible completion on the board and spoken narration at 82s-90s.

   Shown in the video
4. Expression

   $$425 = 3\cdot 124 + 53$$
   Explanation

   Bring down 425 and divide by 124 to get quotient 3 and remainder 53.

   Justification

   Written on the board around 95s-106s and spoken aloud.

   Shown in the video
5. Expression

   $$124 = 2\cdot 53 + 18$$
   Explanation

   Bring down 124 and divide by 53 to get quotient 2 and remainder 18.

   Justification

   Written on the board around 109s-121s and spoken aloud.

   Shown in the video
6. Expression

   $$53 = 2\cdot 18 + 17$$
   Explanation

   Bring down 53 and divide by 18 to get quotient 2 and remainder 17.

   Justification

   Written on the board around 125s-133s and spoken aloud.

   Shown in the video
7. Expression

   $$18 = 1\cdot 17 + 1$$
   Explanation

   Bring down 18 and divide by 17 to get quotient 1 and remainder 1.

   Justification

   Written on the board around 135s-142s and spoken aloud.

   Shown in the video
8. Expression

   $$17 = 17\cdot 1 + 0$$
   Explanation

   One final division is added to force the remainder to be 0, matching the stated stopping condition.

   Justification

   Spoken at 143s-157s and written on the board.

   Shown in the video
9. Expression

   $$\gcd(5295,4321)=1$$
   Explanation

   Since the last nonzero remainder is 1, the gcd is 1.

   Justification

   Follows from the left-board rule $r_{n-1}$=$\gcd(a,b)$; the instructor states this verbally and writes "=1" at 158s.

   Shown in the video

The repeated division chain terminates with last nonzero remainder 1, so $\gcd(5295,4321)=1$ and the numbers are relatively prime.

1. Formula
   Observation

   Right board header reads Ex: Find $\gcd(5295,4321)$.

2. Audio
   Observation

   Speaker introduces the example verbally as finding the GCD of 5,295 and 4,321.

3. Formula
   Observation

   Board work shows $5295 = 1 \cdot 4321 + 974$, then $4321 = 4 \cdot 974 + 425$, then the start of $974 = 2...$.

1. The example is unfinished in this clip; no final gcd value is reached before the cutoff.

Find $\gcd(5295,4321)$ using the Euclidean algorithm.

1. $a=5295$

2. $b=4321$

3. Use repeated division as in the displayed Euclidean algorithm.

Reduce the pair step by step until the last nonzero remainder is found.

1. Expression

   $$5295 = 1\cdot 4321 + 974$$
   Explanation

   First division of the larger number by the smaller gives remainder 974.

   Justification

   Shown on the board and stated aloud.

   Shown in the video
2. Expression

   $$4321 = 4\cdot 974 + 425$$
   Explanation

   Second division uses the previous divisor and remainder, producing remainder 425.

   Justification

   Shown on the board and stated aloud.

   Shown in the video
3. Expression

   $$974 = 2\cdots$$
   Explanation

   Third division is started by moving 974 down as the new dividend.

   Justification

   Visible partial board writing and spoken setup, but the line is incomplete in this clip.

   Shown in the video

No final answer is given within this clip; the worked example stops after beginning the third division.

The clip itself does not reach a zero remainder, so the final gcd cannot be verified from this segment alone.

1. Formula
   Observation

   Right board heading reads "Ex: Find $\gcd(5295,4321)$".

2. Formula
   Observation

   Full worked chain is visible by the end of the clip, ending with $17=17\cdot1+0$ and the appended result =1.

3. Audio
   Observation

   The instructor narrates the computations and concludes at 160s that the numbers are relatively prime.

1. The first two division lines predate the clip start, but their content is fully visible.

Compute $\gcd(5295,4321)$ by repeated division.

1. $a=5295$

2. $b=4321$

3. Use the Euclidean algorithm / division algorithm repeatedly until remainder 0

Determine the greatest common divisor of 5295 and 4321.

1. Expression

   $$5295 = 1\cdot 4321 + 974$$
   Explanation

   Start with the given pair.

   Justification

   Visible on the board at the beginning of the clip.

   Shown in the video
2. Expression

   $$4321 = 4\cdot 974 + 425$$
   Explanation

   Divide the previous divisor by the previous remainder.

   Justification

   Visible on the board at the beginning of the clip.

   Shown in the video
3. Expression

   $$974 = 2\cdot 425 + 124$$
   Explanation

   Continue the same pattern.

   Justification

   Completed on screen and spoken during 82s-90s.

   Shown in the video
4. Expression

   $$425 = 3\cdot 124 + 53$$
   Explanation

   Next remainder is 53.

   Justification

   Written and narrated around 95s-106s.

   Shown in the video
5. Expression

   $$124 = 2\cdot 53 + 18$$
   Explanation

   Next remainder is 18.

   Justification

   Written and narrated around 109s-121s.

   Shown in the video
6. Expression

   $$53 = 2\cdot 18 + 17$$
   Explanation

   Next remainder is 17.

   Justification

   Written and narrated around 125s-133s.

   Shown in the video
7. Expression

   $$18 = 1\cdot 17 + 1$$
   Explanation

   Next remainder is 1.

   Justification

   Written and narrated around 135s-142s.

   Shown in the video
8. Expression

   $$17 = 17\cdot 1 + 0$$
   Explanation

   Add one final step to reach remainder 0.

   Justification

   Explicitly stated by the instructor at 143s-157s.

   Shown in the video
9. Expression

   $$\gcd(5295,4321)=1$$
   Explanation

   The last nonzero remainder is 1.

   Justification

   Uses the left-board rule $r_{n-1}$=$\gcd(a,b)$; also written beside the example heading at 158s.

   Shown in the video

$\gcd(5295,4321)=1$

The final line $17=17\cdot1+0$ has remainder 0. The preceding nonzero remainder 1 gives the gcd, so the two input integers are relatively prime.

1. Diagram
   Observation

   A single blackboard is split conceptually into two regions: left side contains the general Euclidean algorithm statement, right side contains the worked example header and computations.

2. Animation
   Observation

   The instructor points to the left-side general formula while recalling the method, then turns to the right side to write the concrete example.

1. Left column: Euclidean Algorithm general statement

2. Right column: Ex: Find $\gcd(5295,4321)$ worked example

3. Instructor standing beside the board

1. Attention shifts from the general left-side formula to the right-side numerical example.

2. New equations are added sequentially beneath the example header.

1. The left-side general method remains visible throughout the clip.

2. The example header Ex: Find $\gcd(5295,4321)$ stays fixed at the top right.

The visual layout separates theory from practice: the left side supplies the algorithm template, and the right side instantiates it on specific numbers.

1. Animation
   Observation

   After writing $5295 = 1 \cdot 4321 + 974$, arrows are drawn from 4321 and 974 downward toward the next line.

2. Audio
   Observation

   The narration explains reusing the previous divisor and remainder for the next division; the arrows show their new roles.

1. Downward arrows from 4321 and 974

2. Next line $4321 = 4 \cdot 974 + 425$

1. The previous divisor 4321 is moved to become the new dividend.

2. The previous remainder 974 is moved to become the new divisor.

1. The overall Euclidean pattern remains the same from one line to the next.

The arrows visually encode the recurrence in the Euclidean algorithm: each step reuses the prior divisor and remainder as the next pair.

1. Diagram
   Observation

   The blackboard is split into a left theoretical panel titled "Euclidean Algorithm" and a right worked-example panel titled "Ex: Find $\gcd(5295,4321)$".

2. Diagram
   Observation

   Curved arrows on the right connect each remainder to the next line's divisor position.

1. Left panel: general Euclidean algorithm statement

2. Right panel: numerical example $\gcd(5295,4321)$

3. Curved arrows linking successive lines

1. The right panel grows downward as new division equations are written.

2. By the end, the example heading is extended with "=1".

1. The left panel remains unchanged throughout the clip.

2. The right panel always preserves the same dividend = divisor $\times$ quotient + remainder format.

The visual layout separates theory from computation: the left side states the algorithm and termination rule, while the right side instantiates it on concrete integers and uses arrows to show how each remainder becomes the next divisor.

1. Diagram
   Observation

   During the opening of this continuation, a curved arrow carries 425 from the preceding line into the next divisor position.

2. Diagram
   Observation

   Similar arrows appear between 124 and the next line, 53 and the next line, 18 and the next line, and 17 and the next line.

1. Curved arrows between successive equations

2. Numerals 425, 124, 53, 18, 17

1. Each arrow visually transfers the previous divisor or remainder into the next division step.

2. The chain proceeds downward line by line until the final zero remainder.

1. Every new line begins with the quantity carried down from the previous line.

2. The remainder from one line becomes the divisor in the next line.

The arrows encode the recurrence of the Euclidean algorithm: after writing x=yq+r, the next line starts with y and divides by r. This makes the iterative substitution explicit without restating the general formula each time.

1. Diagram
   Observation

   At 158s the instructor writes "=1" immediately after the heading "Ex: Find $\gcd(5295,4321)$".

1. Heading "Ex: Find $\gcd(5295,4321)$"

2. Added "=1"

1. The problem statement is transformed into a solved statement by appending the result.

1. The underlying division chain remains unchanged once completed.

The final annotation records the outcome of the algorithm at the top of the example, linking the computed last nonzero remainder back to the original question.

1. Audio
   Observation

   The 0–82-second portion ends while the third division is being started.

2. Formula
   Observation

   Only $974 = 2$ is visible by the end; no zero-remainder terminating line has been written.

One might think the example has already determined $\gcd(5295,4321)$ because several remainders have been computed.

At this point the division process is still in progress. Continue until a remainder of 0 appears; the last nonzero value then gives the gcd.

1. Audio
   Observation

   The instructor identifies gcd 1 and still writes the final zero-remainder division to make the displayed stopping rule explicit.

Any intermediate nonzero remainder can be accepted as the gcd.

An arbitrary intermediate remainder is not enough. Reaching 1 does establish gcd 1, so early exit is valid in that special case. The video also writes $17=17\cdot1+0$ to display the standard zero-remainder stopping rule.

1. Diagram
   Observation

   Left board gives the general Euclidean algorithm; right board applies it to $gcd(5295,4321)$.

2. Audio
   Observation

   The narration moves from the general algorithm statement to a concrete pair of positive integers.

The worked example is a direct instantiation of the general Euclidean-algorithm procedure stated on the left side of the board.

1. Formula
   Observation

   The left board writes the division chain and then concludes $r_{n-1}=gcd(a,b)$.

The claim about the last nonzero remainder depends on the displayed repeated division-algorithm chain as its setup.

1. Formula
   Observation

   The method summary and the concluding line appear together on the left board.

2. Audio
   Observation

   Speaker states the method and conclusion in one sentence.

The Euclidean-algorithm method includes the proposition that the last nonzero remainder is the gcd.

1. Formula
   Observation

   Left board says "if we repeatedly perform the division algorithm" and then lists the Euclidean chain.

The Euclidean algorithm shown here is built by iterating the division-algorithm identity x=yq+r at each step.

1. Formula
   Observation

   The left board states $r_{n-1}=\gcd(a,b)$ after the displayed chain whose final remainder is 0.

2. Audio
   Observation

   At 143s-160s the instructor applies this rule to conclude $\gcd(5295,4321)=1$.

The algorithm is used as a method for computing the greatest common divisor of two natural numbers.

1. Audio
   Observation

   The closing narration connects gcd 1 with relative primality of the input pair.

In this clip, having gcd equal to 1 is presented as equivalent to the two numbers being relatively prime.

1. Diagram
   Observation

   The right panel instantiates the left-panel algorithm on the concrete pair 5295 and 4321.

The worked example is a direct application of the Euclidean algorithm described on the left side of the board.

1. Audio
   Observation

   Speaker recalls the Euclidean algorithm for two natural numbers.

2. Formula
   Observation

   Left board displays the full method statement.

1. Euclidean algorithm as repeated division
2. Successive division-algorithm equations used in the example
3. Last nonzero remainder equals the gcd

1. Audio
   Observation

   The narration recalls the terminal-remainder rule without presenting its general proof.

2. Formula
   Observation

   Left board concludes $r_{n-1}=gcd(a,b)$.

1. This clip states the result but does not prove it.

1. Last nonzero remainder equals the gcd
2. Euclidean algorithm as repeated division

1. Animation
   Observation

   Arrows show 4321 and 974 being carried down to form the next equation.

2. Audio
   Observation

   The narration and arrows show the previous divisor becoming the next dividend and the previous remainder becoming the next divisor.

1. Successive division-algorithm equations used in the example
2. Worked reduction of $\gcd(5295,4321)$ through the first two Euclidean steps
3. Arrows showing how the next Euclidean line is formed

1. Formula
   Observation

   Right board shows the example header and the first two completed divisions, then a partial third line.

1. The final gcd is not reached in this clip.

1. Partial worked example: $\gcd(5295,4321)$
2. Worked reduction of $\gcd(5295,4321)$ through the first two Euclidean steps
3. Beginning of the third Euclidean step

1. Formula
   Observation

   Left board uses $a,b,q_i,r_i,r_{n-1}$ in the displayed chain.

1. a,b
2. $q_i$,$r_i$
3. $r_{n-1}$
4. Successive division-algorithm equations used in the example

1. Formula
   Observation

   Left board title and general chain define the method.

1. Euclidean algorithm via repeated division
2. Division algorithm form used in each step
3. Termination rule of the Euclidean algorithm

1. Formula
   Observation

   The left board states $r_{n-1}=\gcd(a,b)$ after the displayed chain whose final remainder is 0.

1. Termination rule of the Euclidean algorithm
2. Euclidean algorithm via repeated division

1. Formula
   Observation

   Right board heading asks for $\gcd(5295,4321)$ and later appends =1.

1. Find $\gcd(5295,4321)$ using the Euclidean algorithm
2. Worked Euclidean algorithm for $\gcd(5295,4321)$
3. Greatest common divisor

1. Audio
   Observation

   At 160s the instructor says the numbers are relatively prime after finding gcd 1.

1. Relatively prime interpretation of gcd equal to 1
2. Greatest common divisor
3. Relatively prime conclusion for the example

1. Audio
   Observation

   At 143s-157s the speaker adds one last step to get remainder 0 even though gcd 1 is already obvious.

1. Stopping before the zero-remainder line
2. Termination rule of the Euclidean algorithm
3. Find $\gcd(5295,4321)$ using the Euclidean algorithm