Euclidean algorithm: finding the greatest common divisor

1. Diagram
   Observation

   Whiteboard shows "gcd(10;45)" and "gcd(1701;3768)".

2. Audio
   Observation

   Speaker says he will show how to find the greatest common denominator by using the Euclidean algorithm.

1. The spoken phrase is "greatest common denominator", but the written notation is gcd, which conventionally denotes greatest common divisor.

gcd(a;b)

Function notation for the greatest common divisor of two integers a and b.

Integers; in this 0–83-second source interval the examples use positive integers.

1. Formula
   Observation

   The board writes "$45 = 10 \cdot q + r$" and then "$45 = 10 \cdot 4 + 5$".

2. Audio
   Observation

   Speaker explains that q is how many times 10 goes into 45.

q

Quotient in the division step of the Euclidean algorithm.

Nonnegative integer in this example.

1. Formula
   Observation

   The board writes "$45 = 10 \cdot q + r$" and then "$45 = 10 \cdot 4 + 5$".

2. Audio
   Observation

   Speaker explains that r is the remainder of that result.

r

Remainder after dividing the larger number by the smaller number.

Integer remainder; in this example it is 5.

1. Diagram
   Observation

   The first worked example on the board is gcd(10;45).

2. Audio
   Observation

   The first worked pair introduced in the narration is 10 and 45.

10, 45

The pair of integers used in the first worked example.

Positive integers.

1. Diagram
   Observation

   The second expression visible on the board is gcd(1701;3768).

1. This second example is only shown on the board in this 0–83-second source interval; no computation for it is performed within the provided duration.

1701, 3768

A second pair of integers written on the board as another gcd example.

Positive integers.

1. Formula
   Observation

   The board shows gcd(10;45) and gcd(1701;3768).

2. Audio
   Observation

   The speaker refers to the result as the greatest common denominator for the original two numbers.

1. The spoken phrase 'greatest common denominator' conflicts with the written notation gcd, which conventionally means greatest common divisor.

gcd(a;b)

Greatest common divisor of the two integers a and b, as indicated by the written notation.

Positive integers.

1. Formula
   Observation

   The board shows $45 = 10 \times q + r$.

q, r

Quotient and remainder in the division step of the Euclidean algorithm.

Integers with $0 \le r$ < divisor in the standard algorithm.

1. Formula
   Observation

   The board shows $45 = 10 \times 4 + 5$ and $10 = 5 \times 2 + 0$.

45, 10, 4, 5, 2, 0

Concrete integers used in the worked example for gcd(10;45).

Nonnegative integers.

1. Formula
   Observation

   The board shows $3768 = 1701 \times 2 + 366$, then $1701 = 366 \times 4 + 237$, then $366 = 237 \times 1$.

1. The final remainder for the third displayed line is not completed within this 83–166-second source interval.

3768, 1701, 2, 366, 4, 237, 1

Concrete integers used in the larger worked example for gcd(1701;3768).

Nonnegative integers.

1. Formula
   Observation

   gcd(10; 45) and gcd(1701; 3768) written at the top of the whiteboard.

$\gcd(a, b)$

Greatest common divisor of two integers a and b.

Positive integers in this lesson.

1. Formula
   Observation

   The specific numbers 1701 and 3768 are used as the inputs to the gcd function.

a, b

The two positive integers for which the greatest common divisor is being calculated (specifically, $a=1701$, $b=3768$).

Positive integers

1. Audio
   Observation

   Speaker states that the greatest common denominator is going to be the largest number that divides both 10 and 45 evenly.

2. Diagram
   Observation

   The board shows gcd(10;45).

1. The speaker says "denominator" while the notation gcd normally means "divisor".

For the pair 10 and 45, the video defines the target quantity as the largest number that divides both numbers evenly. In standard terminology this is the greatest common divisor.

1. Applies here to two positive integers.

2. The term divisor is the standard terminology.

1. Audio
   Observation

   Speaker says he will show how to find the greatest common denominator by using the Euclidean algorithm.

2. Diagram
   Observation

   Title on board reads "THE EUCLIDIAN ALGORITHM".

1. The board title spells "EUCLIDIAN"; standard English spelling is usually "Euclidean".

The 0–83-second source interval presents the Euclidean algorithm as a method for computing gcd(10;45), especially when the answer is not immediately obvious by inspection.

1. Used here for the gcd of two positive integers.

1. Definition of gcd in the example

1. Audio
   Observation

   Speaker says to take the larger of the two numbers, set it equal to the smaller number times some number q plus some number r.

2. Formula
   Observation

   The board writes "$45 = 10 \cdot q + r$" and then "$45 = 10 \cdot 4 + 5$".

The algorithm begins by expressing the larger integer as the smaller integer multiplied by a quotient plus a remainder. In this example, 45 is rewritten in terms of 10, q, and r.

1. Use the larger number on the left-hand side.

2. Use the smaller number as the multiplier base.

3. q is the quotient and r is the remainder.

1. Purpose of the Euclidean algorithm

1. Audio
   Observation

   Speaker says q is how many times 10 goes into 45 and r is the remainder of that result.

2. Formula
   Observation

   The completed line is "$45 = 10 \cdot 4 + 5$".

In the worked example, q counts how many whole times the smaller number fits into the larger one, and r is what is left over after that multiplication.

1. Specific to the division 45 by 10 in this 0–83-second source interval.

1. First division equation in the Euclidean algorithm

1. Audio
   Observation

   Speaker says that in all remaining steps, take the number in this position and move it to where the left-hand-side number was, then take the remainder and move it to where the smaller number was.

2. Diagram
   Observation

   Arrows are drawn under the previous line to show 10 moving left and 5 moving into the next divisor position.

3. Formula
   Observation

   A new line begins with "10 =".

1. The next full equation after "10 =" is not completed within the provided 0–83-second source interval.

After one division step, the previous divisor becomes the new dividend, and the previous remainder becomes the new divisor. The process repeats until the remainder reaches zero.

1. Continue the pattern until a remainder of 0 is obtained.

1. First division equation in the Euclidean algorithm
2. Meaning of q and r in the example

1. Formula
   Observation

   The board displays $45 = 10 \times q + r$ and then substitutes $q=4$, $r=5$.

2. Audio
   Observation

   The speaker describes asking how many times one number goes into another and what the remainder is.

Repeated division uses dividend = divisor × quotient + remainder. For the small example, 45 divided by 10 gives quotient 4 and remainder 5; then 10 divided by 5 gives quotient 2 and remainder 0.

1. Applied to positive integers in the examples shown.

2. The 83–166-second source interval does not explicitly state the formal bound $0 \le r < b$, although the worked values are consistent with it.

1. Audio
   Observation

   The narration selects the preceding nonzero remainder after the new remainder becomes zero.

2. Formula
   Observation

   The board shows $10 = 5 \times 2 + 0$, and the earlier remainder 5 is boxed.

1. The spoken term 'greatest common denominator' is likely a slip; the written notation is gcd.

In this example, $10=5\cdot2+0$, so the terminal divisor 5 is the gcd of (10,45). It is also the preceding nonzero remainder. Editorial scope: the terminal-divisor formulation works even when the first division already has zero remainder.

1. The inputs here are two positive integers.

2. The 83–166-second source interval demonstrates the rule on a concrete example rather than proving it.

1. Division-with-remainder step of the Euclidean algorithm

1. Audio
   Observation

   The narration starts the larger calculation with 3768 divided by 1701, then carries the new remainders forward.

2. Formula
   Observation

   The board shows $3768 = 1701 \times 2 + 366$, then $1701 = 366 \times 4 + 237$, then $366 = 237 \times 1$.

1. The third line is incomplete by the end of the 83–166-second source interval.

The presenter repeats the same Euclidean-algorithm procedure on gcd(1701;3768), beginning with the larger number 3768 divided by the smaller number 1701, then carrying each remainder forward to the next line. The 83–166-second source interval shows the first two full divisions and the start of the third.

1. The method is shown for positive integers.

2. The final remainder in the last displayed line is not reached within this 83–166-second source interval.

1. Division-with-remainder step of the Euclidean algorithm

1. Audio
   Observation

   Speaker explains the process of repeatedly dividing and moving remainders to find the greatest common denominator.

2. Formula
   Observation

   A sequence of division equations is written on the board, ending with a remainder of 0.

For positive integers, repeatedly write $a=bq+r$ with an integer quotient and $0\le r<b$, then use the pair (b,r) when r is positive. At a zero remainder return the divisor of that terminal division. In the two examples this equals the last nonzero remainder; if the first division is exact, return its divisor without requiring an earlier nonzero remainder. This general scope is an editorial clarification of the worked procedure.

1. a and b are integers

2. $b > 0$

3. 0 <= $r < b$

1. Audio
   Observation

   The narration identifies 5 as the answer for the first integer pair.

2. Diagram
   Observation

   The example being discussed is gcd(10;45).

1. The value 5 is stated verbally in this 0–83-second source interval; it is not yet boxed or derived to completion before the 0–83-second source interval ends.

For the pair 10 and 45, the greatest common divisor is 5.

1. The numbers under consideration are 10 and 45.

Specific numerical claim for the given pair.

1. Audio
   Observation

   Speaker says to follow the pattern all the way down until we get a remainder of 0.

1. The 0–83-second source interval does not prove why stopping at remainder 0 yields the gcd; it only states the procedure.

In the Euclidean algorithm as presented here, continue the shift-and-divide pattern until the remainder is 0.

1. The algorithm is applied to two positive integers.

General procedural claim stated for the algorithm.

1. Audio
   Observation

   The narration chooses the preceding nonzero remainder when the final remainder becomes zero.

2. Formula
   Observation

   The board shows $45 = 10 \times 4 + 5$ and $10 = 5 \times 2 + 0$, with 5 boxed.

1. The spoken wording says 'denominator' while the written notation is gcd.

For the pair (10,45), after obtaining $10 = 5 \times 2 + 0$, the previous remainder 5 is the gcd of the original two numbers.

1. The Euclidean algorithm has been applied to 45 and 10.

2. A division step has produced remainder 0.

For the specific integers 10 and 45 shown in the example.

1. Formula
   Observation

   The board shows $3768 = 1701 \times 2 + 366$ and $1701 = 366 \times 4 + 237$.

2. Audio
   Observation

   The narration describes 3768 divided by 1701 with quotient 2 and remainder 366, followed by 1701 divided by 366 with quotient 4 and remainder 237.

In the larger example, $3768 = 1701 \times 2 + 366$ and $1701 = 366 \times 4 + 237$.

1. The integers are 3768 and 1701.

2. The Euclidean algorithm is being applied by successive division.

For the specific integers 3768 and 1701 shown in the example.

1. Audio
   Observation

   The narration concludes that the gcd of 1701 and 3768 is 3, referring to the last positive remainder.

2. Diagram
   Observation

   The speaker draws an arrow from the final remainder '0' to the previous remainder '3', and boxes the '3'.

For two positive integers, correctly performed Euclidean division terminates with a zero remainder. Its terminal divisor is their gcd; where earlier nonzero remainders exist, this is the last such remainder. The source example gives $\gcd(1701,3768)=3$.

1. The Euclidean algorithm has been applied correctly to the two numbers.

2. The algorithm has terminated with a remainder of 0.

For any two positive integers.

1. Audio
   Observation

   Speaker explains taking the larger number 45 and setting it equal to the smaller number 10 times q plus r.

2. Formula
   Observation

   The board shows "$45 = 10 \cdot q + r$" and then "$45 = 10 \cdot 4 + 5$".

1. Expression

   $$45 = 10 \cdot q + r$$
   Explanation

   Start with the larger number 45 and express it in terms of the smaller number 10, an unknown quotient q, and an unknown remainder r.

   Justification

   This is the division-with-remainder setup described by the speaker for the Euclidean algorithm.

   Shown in the video
2. Expression

   $$q = 4$$
   Explanation

   Determine how many whole times 10 fits into 45.

   Justification

   The speaker explicitly says q is how many times 10 goes into 45.

   Shown in the video
3. Expression

   $$r = 5$$
   Explanation

   Compute the leftover amount after subtracting 4 copies of 10 from 45.

   Justification

   The speaker identifies r as the remainder of that result.

   Shown in the video
4. Expression

   $$45 = 10 \cdot 4 + 5$$
   Explanation

   Substitute the found quotient and remainder back into the division equation.

   Justification

   Direct substitution of $q = 4$ and $r = 5$ into the initial form.

   Shown in the video

The first Euclidean reduction for the example is $45 = 10\cdot 4 + 5$.

1. Audio
   Observation

   Speaker says to move the number in the divisor position to the left-hand side and move the remainder into the next smaller-number position.

2. Diagram
   Observation

   Arrows under the completed line indicate the movement of 10 and 5 into the next step.

3. Formula
   Observation

   A new line starts with "10 =".

1. The next full equation is not finished within the 0–83-second source interval, so the exact next quotient and remainder are not shown here.

1. Expression

   $$45 = 10 \cdot 4 + 5$$
   Explanation

   Begin from the completed first division line.

   Justification

   This line is already written on the board.

   Shown in the video
2. Expression

   $$10 = \ldots$$
   Explanation

   Move the previous divisor 10 to the left-hand side of the next equation.

   Justification

   The speaker describes this shift as the rule for all remaining steps.

   Shown in the video
3. Expression

   $$10 = 5 \cdot q' + r'$$
   Explanation

   The previous remainder 5 becomes the new divisor position in the next line.

   Justification

   This follows the arrow pattern and the verbal instruction to move the remainder into the smaller-number position.

   Derived from the video

The algorithm proceeds to a new line beginning with 10, using 5 as the next divisor; the rest of that line is not shown within the 0–83-second source interval.

1. Formula
   Observation

   The board shows $45 = 10 \times q + r$, then $45 = 10 \times 4 + 5$, then $10 = 5 \times 2 + 0$.

2. Audio
   Observation

   The narration replaces the divisor by the preceding remainder and reaches an exact division, then identifies the answer.

1. Expression

   $$45 = 10 \cdot q + r$$
   Explanation

   Begin with the larger number 45 expressed in terms of the smaller number 10.

   Justification

   Setup of the division-with-remainder step shown on the board.

   Shown in the video
2. Expression

   $$45 = 10 \cdot 4 + 5$$
   Explanation

   Compute the quotient and remainder for 45 divided by 10.

   Justification

   Arithmetic evaluation of the division step.

   Shown in the video
3. Expression

   $$10 = 5 \cdot 2 + 0$$
   Explanation

   Move the previous remainder 5 into the divisor position and divide the previous divisor 10 by it.

   Justification

   The narration moves the preceding remainder into the divisor position before the next division.

   Shown in the video
4. Expression

   $$\gcd(10,45)=5$$
   Explanation

   Because the new remainder is 0, take the previous nonzero remainder 5 as the gcd.

   Justification

   Termination rule stated verbally and visually emphasized by boxing 5.

   Shown in the video

The Euclidean algorithm yields gcd(10;45)=5.

1. Formula
   Observation

   The board shows $3768 = 1701 \times 2 + 366$, then $1701 = 366 \times 4 + 237$, then $366 = 237 \times 1$.

2. Audio
   Observation

   The narration performs two completed divisions and starts the third division of the larger example.

1. The 83–166-second source interval ends before the remainder on the third line is written or the algorithm terminates.

1. Expression

   $$3768 = 1701 \cdot 2 + 366$$
   Explanation

   Start the larger example by dividing 3768 by 1701.

   Justification

   Explicitly written on the board and stated in the audio.

   Shown in the video
2. Expression

   $$1701 = 366 \cdot 4 + 237$$
   Explanation

   Replace the divisor by the previous remainder 366 and divide 1701 by it.

   Justification

   The narration carries the previous divisor and remainder into the next written line.

   Shown in the video
3. Expression

   $$366 = 237 \cdot 1 + \cdots$$
   Explanation

   Replace the divisor by the previous remainder 237 and begin dividing 366 by it.

   Justification

   The source interval shows the start of the next division, with the remainder completed later in the full video.

   Shown in the video

Within this 83–166-second source interval, the larger example is carried through two complete Euclidean steps and the beginning of a third; the final gcd is not reached on screen.

1. Formula
   Observation

   The step-by-step division equations are written on the whiteboard.

2. Audio
   Observation

   The speaker narrates each step of the calculation.

1. Expression

   $$3768 = 1701 \cdot 2 + 366$$
   Explanation

   Divide 3768 by 1701. The quotient is 2 and the remainder is 366.

   Justification

   Division algorithm.

   Shown in the video
2. Expression

   $$1701 = 366 \cdot 4 + 237$$
   Explanation

   Move 1701 to the left side and 366 to the right. Divide 1701 by 366. The quotient is 4 and the remainder is 237.

   Justification

   Division algorithm.

   Shown in the video
3. Expression

   $$366 = 237 \cdot 1 + 129$$
   Explanation

   Move 366 to the left side and 237 to the right. Divide 366 by 237. The quotient is 1 and the remainder is 129.

   Justification

   Division algorithm.

   Shown in the video
4. Expression

   $$237 = 129 \cdot 1 + 108$$
   Explanation

   Move 237 to the left side and 129 to the right. Divide 237 by 129. The quotient is 1 and the remainder is 108.

   Justification

   Division algorithm.

   Shown in the video
5. Expression

   $$129 = 108 \cdot 1 + 21$$
   Explanation

   Move 129 to the left side and 108 to the right. Divide 129 by 108. The quotient is 1 and the remainder is 21.

   Justification

   Division algorithm.

   Shown in the video
6. Expression

   $$108 = 21 \cdot 5 + 3$$
   Explanation

   Move 108 to the left side and 21 to the right. Divide 108 by 21. The quotient is 5 and the remainder is 3.

   Justification

   Division algorithm.

   Shown in the video
7. Expression

   $$21 = 3 \cdot 7 + 0$$
   Explanation

   Move 21 to the left side and 3 to the right. Divide 21 by 3. The quotient is 7 and the remainder is 0.

   Justification

   Division algorithm.

   Shown in the video

The process terminates because the remainder is 0. The last non-zero remainder is 3.

1. Diagram
   Observation

   The board shows gcd(10;45) and the worked lines $45 = 10 \cdot q + r$, $45 = 10 \cdot 4 + 5$, and the start of 10 = .

2. Audio
   Observation

   Speaker introduces 10 and 45 as the first example and narrates the Euclidean steps.

1. Only the first reduction and the setup of the second line are completed in this 0–83-second source interval.

Find gcd(10;45) using the Euclidean algorithm.

1. The two integers are 10 and 45.

2. The method to use is the Euclidean algorithm.

Reduce the pair step by step until the remainder becomes 0, thereby identifying the gcd.

1. Expression

   $$45 = 10 \cdot q + r$$
   Explanation

   Write the larger number as the smaller number times an unknown quotient plus an unknown remainder.

   Justification

   This is the first step of the Euclidean algorithm as explained in the 0–83-second source interval.

   Shown in the video
2. Expression

   $$45 = 10 \cdot 4 + 5$$
   Explanation

   Evaluate the division of 45 by 10 to get quotient 4 and remainder 5.

   Justification

   The speaker explicitly identifies q as how many times 10 goes into 45 and r as the remainder.

   Shown in the video
3. Expression

   $$10 = \ldots$$
   Explanation

   Begin the next line by moving the old divisor 10 to the left-hand side and preparing to use the old remainder 5 as the new divisor.

   Justification

   The arrows and narration describe the recursive shift pattern of the algorithm.

   Shown in the video

The 0–83-second source interval establishes the first reduction $45 = 10\cdot 4 + 5$ and starts the next line with 10 = ; the final gcd value 5 is stated verbally earlier but the full algorithm is not completed on screen within this segment.

Within this 0–83-second source interval, verification is partial: the speaker states the answer is 5, and the first division step is consistent with $45 = 10\cdot 4 + 5$.

1. Formula
   Observation

   The board shows gcd(10;45), $45 = 10 \times q + r$, $45 = 10 \times 4 + 5$, and $10 = 5 \times 2 + 0$.

2. Audio
   Observation

   The narration identifies the preceding nonzero remainder as the answer after the final zero remainder.

1. The spoken term 'denominator' conflicts with the written gcd notation.

Find gcd(10;45) using the Euclidean algorithm.

1. The pair is 10 and 45.

2. The larger number is placed on the left in the division statement.

Determine the greatest common divisor of 10 and 45.

1. Expression

   $$45 = 10 \cdot 4 + 5$$
   Explanation

   Divide 45 by 10 to obtain quotient 4 and remainder 5.

   Justification

   Direct arithmetic step shown on the board.

   Shown in the video
2. Expression

   $$10 = 5 \cdot 2 + 0$$
   Explanation

   Bring the remainder 5 forward as the new divisor and divide 10 by 5.

   Justification

   The speaker explicitly moves 5 into the position previously occupied by 10.

   Shown in the video
3. Expression

   $$\gcd(10,45)=5$$
   Explanation

   Since the remainder is now 0, use the previous nonzero remainder 5 as the answer.

   Justification

   Termination rule stated verbally and reinforced by boxing 5.

   Shown in the video

5

The result matches the standard value of gcd(10,45), and the board visually marks 5 as the final selected remainder.

1. Formula
   Observation

   The board shows gcd(1701;3768), $3768 = 1701 \times 2 + 366$, $1701 = 366 \times 4 + 237$, and $366 = 237 \times 1$.

2. Audio
   Observation

   The narration works through the first two divisions of the larger example and begins the third.

1. The example is unfinished in this 83–166-second source interval; the last remainder and final gcd are not shown.

Apply the Euclidean algorithm to gcd(1701;3768).

1. The pair is 1701 and 3768.

2. The larger number 3768 is used first on the left-hand side.

Carry out successive division steps to find the gcd.

1. Expression

   $$3768 = 1701 \cdot 2 + 366$$
   Explanation

   Divide 3768 by 1701 to get quotient 2 and remainder 366.

   Justification

   Written on the board and stated in the audio.

   Shown in the video
2. Expression

   $$1701 = 366 \cdot 4 + 237$$
   Explanation

   Use 366 as the new divisor and divide 1701 by it to get quotient 4 and remainder 237.

   Justification

   Written on the board and stated in the audio.

   Shown in the video
3. Expression

   $$366 = 237 \cdot 1 + \cdots$$
   Explanation

   Use 237 as the new divisor and begin dividing 366 by it.

   Justification

   The board shows $366 = 237 \times 1$, but the remainder is not completed before the 83–166-second source interval ends.

   Shown in the video

Not completed within this 83–166-second source interval.

The first two displayed equations are arithmetically correct: $1701\times 2+366=3768$ and $366\times 4+237=1701$.

1. Formula
   Observation

   gcd(1701; 3768) is written on the board.

2. Audio
   Observation

   The speaker states the problem and solves it step-by-step.

Find the greatest common divisor of 1701 and 3768 using the Euclidean algorithm.

1. $a = 1701$

2. $b = 3768$

Calculate gcd(1701, 3768).

1. Expression

   $$3768 = 1701 \cdot 2 + 366$$
   Explanation

   First division step.

   Justification

   Division algorithm.

   Shown in the video
2. Expression

   $$1701 = 366 \cdot 4 + 237$$
   Explanation

   Second division step.

   Justification

   Division algorithm.

   Shown in the video
3. Expression

   $$366 = 237 \cdot 1 + 129$$
   Explanation

   Third division step.

   Justification

   Division algorithm.

   Shown in the video
4. Expression

   $$237 = 129 \cdot 1 + 108$$
   Explanation

   Fourth division step.

   Justification

   Division algorithm.

   Shown in the video
5. Expression

   $$129 = 108 \cdot 1 + 21$$
   Explanation

   Fifth division step.

   Justification

   Division algorithm.

   Shown in the video
6. Expression

   $$108 = 21 \cdot 5 + 3$$
   Explanation

   Sixth division step.

   Justification

   Division algorithm.

   Shown in the video
7. Expression

   $$21 = 3 \cdot 7 + 0$$
   Explanation

   Seventh division step, resulting in a remainder of 0.

   Justification

   Division algorithm.

   Shown in the video
8. Expression

   $$\gcd(1701, 3768) = 3$$
   Explanation

   The last non-zero remainder is the GCD.

   Justification

   Property of the Euclidean algorithm.

   Shown in the video

3

The video does not show a verification step, such as checking if 3 divides both 1701 and 3768 without a remainder.

1. Diagram
   Observation

   At the start, the whiteboard shows the title "THE EUCLIDIAN ALGORITHM" and two expressions: gcd(10;45) and gcd(1701;3768).

1. Title text "THE EUCLIDIAN ALGORITHM"

2. Expression gcd(10;45)

3. Expression gcd(1701;3768)

1. No writing changes yet; the board presents the topic and two example pairs.

1. The 0–83-second source interval is framed around gcd computations.

2. The first example is 10 and 45.

The visual opening establishes that the lesson is about computing greatest common divisors using the Euclidean algorithm, with one small example and one larger example written in advance.

1. Animation
   Observation

   A hand writes $45 = 10 \cdot q + r$ and then fills in 4 and 5 to make $45 = 10 \cdot 4 + 5$.

2. Audio
   Observation

   The speaker explains the meaning of q and r while writing.

1. Equation $45 = 10 \cdot q + r$

2. Completed equation $45 = 10 \cdot 4 + 5$

1. The symbolic line progresses from unknown q and r to explicit values 4 and 5.

1. The left-hand side remains 45.

2. The divisor remains 10 throughout this first line.

The animation shows the concrete division step that initiates the Euclidean algorithm for the pair (10,45).

1. Diagram
   Observation

   Arrows are drawn beneath the completed line to indicate moving 10 leftward and 5 into the next divisor position.

2. Audio
   Observation

   The speaker describes taking the number in one position and moving it to the left-hand side, then moving the remainder to the smaller-number position.

3. Formula
   Observation

   A new line begins with 10 = .

1. The next equation is not completed before the 0–83-second source interval ends.

1. Underline/arrows below $45 = 10 \cdot 4 + 5$

2. New line starting with 10 =

1. The previous divisor 10 is promoted to the new left-hand side.

2. The previous remainder 5 is prepared to become the next divisor.

1. The pattern is iterative: each step uses the previous divisor and remainder.

2. The process continues until remainder 0.

The visual arrows encode the recurrence relation of the Euclidean algorithm more clearly than the algebra alone.

1. Diagram
   Observation

   The number 5 from $45 = 10 \times 4 + 5$ is boxed, and an arrow links the zero remainder line back to it.

1. The boxed 5 in $45 = 10 \times 4 + 5$

2. The line $10 = 5 \times 2 + 0$

3. Arrows between lines

1. After the remainder 0 appears, attention shifts back to the previous remainder 5.

2. The 5 is enclosed in a box to mark it as the answer.

1. The original pair gcd(10;45) remains written at the top.

2. The earlier division equations remain visible while the answer is selected.

The boxing and backward arrow visually encode the stop rule: when a remainder becomes 0, the preceding nonzero remainder is the gcd.

1. Animation
   Observation

   The lower work for the small example is wiped away, leaving the headings gcd(10;45) and gcd(1701;3768), and new writing begins under the larger example.

1. Whiteboard eraser/cloth

2. The two gcd headings

3. New writing area under gcd(1701;3768)

1. The completed small-example calculations are removed.

2. The presenter starts a fresh sequence of division lines for the larger pair.

1. The two problem headings remain on the board.

2. The method stays the same even though the numbers change.

The visual reset signals that the same algorithm is being reused on a harder numerical instance.

1. Animation
   Observation

   The speaker draws an arrow from the final '0' remainder up to the previous '3' remainder, and then draws a box around the '3'.

1. Remainder 0

2. Remainder 3

3. Arrow

4. Box

1. An arrow is drawn from 0 to 3.

2. A box is drawn around 3.

1. The sequence of equations remains unchanged.

This visual action emphasizes that the last non-zero remainder (3) is the result of the algorithm, i.e., the greatest common divisor.

1. Audio
   Observation

   The speaker repeatedly says "greatest common denominator".

2. Diagram
   Observation

   The board writes gcd(10;45) and gcd(1701;3768).

The spoken phrase "greatest common denominator" may suggest a fraction-related concept rather than the intended greatest common divisor.

The notation gcd and the worked division steps indicate the topic is the greatest common divisor, not a common denominator of fractions.

1. Diagram
   Observation

   The title on the board reads "THE EUCLIDIAN ALGORITHM".

The board spelling "EUCLIDIAN" differs from the standard spelling "Euclidean".

The mathematical content still corresponds to the Euclidean algorithm for gcd computation.

1. Audio
   Observation

   The narrator uses the word denominator for the quantity computed by the gcd procedure.

2. Formula
   Observation

   The board writes gcd(10;45) and gcd(1701;3768).

The speaker says 'greatest common denominator' while the board uses gcd notation.

In this context gcd denotes greatest common divisor. The written notation and the procedure match the divisor interpretation, so the spoken word appears to be a verbal slip.

1. Audio
   Observation

   Speaker says the Euclidean algorithm will be used to find the greatest common denominator/divisor.

2. Diagram
   Observation

   The board title and gcd notation appear together.

The definition of gcd motivates the need for the Euclidean algorithm as a computational method.

1. Formula
   Observation

   The equation $45 = 10 \cdot q + r$ is introduced and then instantiated as $45 = 10 \cdot 4 + 5$.

2. Audio
   Observation

   The speaker defines q and r while writing the equation.

The general division step contains the specific meanings of quotient and remainder used in the example.

1. Audio
   Observation

   After explaining q and r, the speaker says to move the divisor and remainder into the next line.

2. Diagram
   Observation

   Arrows show 10 and 5 shifting positions for the next step.

Understanding what the divisor and remainder are is required before applying the recursive shift rule of the Euclidean algorithm.

1. Formula
   Observation

   The board first shows division steps and then boxes the previous remainder once 0 appears.

2. Audio
   Observation

   The narration stops the procedure at a zero remainder and chooses the preceding nonzero value.

The termination rule is applied after the repeated division-with-remainder steps produce a zero remainder.

1. Audio
   Observation

   The narration applies the same procedure to the larger integer pair.

2. Formula
   Observation

   The same line format $a = b \times q + r$ is reused for 3768 and 1701.

The larger example is a direct reuse of the same Euclidean-algorithm method on bigger integers.

1. Formula
   Observation

   The headings gcd(10;45) and gcd(1701;3768) frame both worked examples.

The written gcd notation identifies the target quantity that the division algorithm is being used to compute.

1. Audio
   Observation

   The speaker explains the general method while performing the specific example.

The example demonstrates the application of the Euclidean algorithm method.

1. Audio
   Observation

   Speaker explains taking the larger number and writing it as the smaller number times q plus r.

2. Formula
   Observation

   The board shows $45 = 10 \cdot q + r$ and then $45 = 10 \cdot 4 + 5$.

1. First division equation in the Euclidean algorithm
2. Meaning of q and r in the example

1. Audio
   Observation

   Speaker says q is how many times 10 goes into 45 and r is the remainder.

1. Meaning of q and r in the example

1. Audio
   Observation

   Speaker describes moving the divisor to the left-hand side and the remainder to the smaller-number position.

2. Diagram
   Observation

   Arrows illustrate the shift into the next line.

1. Recursive shift pattern of the Euclidean algorithm

1. Audio
   Observation

   Speaker says the greatest common denominator/divisor is the largest number that divides both 10 and 45 evenly.

1. The spoken term is denominator, but the mathematical context is divisor.

1. Definition of gcd in the example

1. Diagram
   Observation

   The 5 is boxed after the line $10 = 5 \times 2 + 0$ appears.

2. Audio
   Observation

   The narrator chooses the preceding nonzero remainder after the final exact division.

1. Termination rule for the Euclidean algorithm
2. Derivation of gcd(10;45) by the Euclidean algorithm
3. Visual emphasis of the final remainder

1. Audio
   Observation

   The narration sets up 3768 as 1701 times an integer quotient plus a remainder.

2. Formula
   Observation

   $3768 = 1701 \times 2 + 366$

1. Applying the same method to a larger pair of integers
2. Partial derivation for gcd(1701;3768)
3. Worked example: gcd(1701;3768), partial

1. Audio
   Observation

   The narration describes carrying each divisor and remainder into the next division.

2. Formula
   Observation

   Successive lines replace the old divisor by the previous remainder.

1. Division-with-remainder step of the Euclidean algorithm
2. Derivation of gcd(10;45) by the Euclidean algorithm
3. Partial derivation for gcd(1701;3768)

1. Audio
   Observation

   The narration uses the term denominator while discussing gcd.

2. Formula
   Observation

   gcd(10;45)

1. Spoken 'denominator' versus written gcd
2. gcd(a;b)

1. Audio
   Observation

   The entire video is a demonstration of this process.

1. Euclidean Algorithm
2. Finding gcd(1701, 3768)

1. Audio
   Observation

   The narration selects the preceding positive remainder at the end of the calculation.

1. Result of the Euclidean Algorithm