Euclidean Algorithm - An example ← Number Theory

1. Formula
   Observation

   The text 'Find gcd(1785, 546)' appears on screen at 00:29, and the final conclusion '$\therefore$ gcd(1785, 546) = 21' is written at 01:54.

2. Audio
   Observation

   The narrator states 'finding the greatest common divisor of two integers' at 00:01 and 'the greatest common divisor of 1,785 and 546 is 21' at 01:54.

$\gcd(a, b)$

The greatest common divisor of two integers a and b.

Integers

1. Audio
   Observation

   The narrator explains that the Euclidean algorithm is a method for finding the greatest common divisor of two integers by repeatedly performing long division until the remainder is zero.

2. Diagram
   Observation

   A visual example from 00:18 to 00:27 shows the steps of dividing 104 by 84, then 84 by 20, and finally 20 by 4 to reach a remainder of 0.

The Euclidean algorithm finds the greatest common divisor (GCD) of two integers without needing to factor them. The process involves repeatedly performing long division: divide the larger number by the smaller number, then divide the previous divisor by the remainder, and continue this process. When the remainder becomes zero, the last non-zero remainder is the GCD.

1. Applies to two integers.

2. Requires repeated long division.

3. Stops when the remainder is zero.

1. Audio
   Observation

   The narrator introduces the concept as the 'greatest common divisor of two integers' at 00:01 and concludes with the specific value for 1785 and 546 at 01:54.

2. Formula
   Observation

   The notation 'gcd(1785, 546)' is displayed on screen from 00:29 onwards.

The greatest common divisor of two integers is the largest positive integer that divides both numbers without leaving a remainder. In the video, it is found using the Euclidean algorithm.

1. Defined for two integers.

1. Audio
   Observation

   The narrator states, 'When you get a remainder of zero, you stop and the method is over. The last nonzero remainder is the greatest common divisor.'

2. Diagram
   Observation

   An arrow points to the remainder '21' in the second-to-last division step at 01:51, identifying it as the result.

In the Euclidean algorithm, when the division process yields a remainder of zero, the greatest common divisor of the original two integers is the last non-zero remainder obtained.

1. The Euclidean algorithm is applied to two integers.

2. The process of repeated long division is followed until a remainder of zero is reached.

For any two integers.

1. Diagram
   Observation

   The visual sequence shows 104 divided by 84 (quotient 1, remainder 20), then 84 divided by 20 (quotient 4, remainder 4), and finally 20 divided by 4 (quotient 5, remainder 0).

1. Expression

   $$104 \div 84 = 1 \text{ R } 20$$
   Explanation

   Divide the initial larger number by the smaller number.

   Justification

   First step of the Euclidean algorithm.

   Shown in the video
2. Expression

   $$84 \div 20 = 4 \text{ R } 4$$
   Explanation

   Divide the previous divisor (84) by the previous remainder (20).

   Justification

   Second step of the Euclidean algorithm.

   Shown in the video
3. Expression

   $$20 \div 4 = 5 \text{ R } 0$$
   Explanation

   Divide the previous divisor (20) by the previous remainder (4). The remainder is zero, so the process stops.

   Justification

   Third step of the Euclidean algorithm.

   Shown in the video

The last non-zero remainder is 4, which is the greatest common divisor of 104 and 84.

1. Diagram
   Observation

   The screen sequentially displays the long division steps: 1785 by 546, 546 by 147, 147 by 105, 105 by 42, and 42 by 21.

2. Audio
   Observation

   The narrator verbally guides through each division step, stating the quotients and remainders.

1. Expression

   $$1785 = 546 \times 3 + 147$$
   Explanation

   Divide 1785 by 546 to get a quotient of 3 and a remainder of 147.

   Justification

   First step of the Euclidean algorithm.

   Shown in the video
2. Expression

   $$546 = 147 \times 3 + 105$$
   Explanation

   Divide the previous divisor (546) by the previous remainder (147) to get a quotient of 3 and a remainder of 105.

   Justification

   Second step of the Euclidean algorithm.

   Shown in the video
3. Expression

   $$147 = 105 \times 1 + 42$$
   Explanation

   Divide the previous divisor (147) by the previous remainder (105) to get a quotient of 1 and a remainder of 42.

   Justification

   Third step of the Euclidean algorithm.

   Shown in the video
4. Expression

   $$105 = 42 \times 2 + 21$$
   Explanation

   Divide the previous divisor (105) by the previous remainder (42) to get a quotient of 2 and a remainder of 21.

   Justification

   Fourth step of the Euclidean algorithm.

   Shown in the video
5. Expression

   $$42 = 21 \times 2 + 0$$
   Explanation

   Divide the previous divisor (42) by the previous remainder (21) to get a quotient of 2 and a remainder of 0.

   Justification

   Fifth step of the Euclidean algorithm; the process stops because the remainder is zero.

   Shown in the video

The last non-zero remainder is 21, therefore $\gcd(1785, 546) = 21$.

1. Formula
   Observation

   The problem 'Find gcd(1785, 546)' is displayed at 00:29, and the final answer '$\therefore$ gcd(1785, 546) = 21' is shown at 01:54.

2. Audio
   Observation

   The narrator explicitly states the problem and the final solution.

Find the greatest common divisor of 1785 and 546 using the Euclidean algorithm.

1. $a = 1785$

2. $b = 546$

Determine $\gcd(1785, 546)$.

1. Expression

   $$1785 \div 546 = 3 \text{ R } 147$$
   Explanation

   Perform the first long division.

   Justification

   Euclidean algorithm step 1.

   Shown in the video
2. Expression

   $$546 \div 147 = 3 \text{ R } 105$$
   Explanation

   Divide the previous divisor by the previous remainder.

   Justification

   Euclidean algorithm step 2.

   Shown in the video
3. Expression

   $$147 \div 105 = 1 \text{ R } 42$$
   Explanation

   Repeat the process.

   Justification

   Euclidean algorithm step 3.

   Shown in the video
4. Expression

   $$105 \div 42 = 2 \text{ R } 21$$
   Explanation

   Repeat the process.

   Justification

   Euclidean algorithm step 4.

   Shown in the video
5. Expression

   $$42 \div 21 = 2 \text{ R } 0$$
   Explanation

   Repeat the process until the remainder is zero.

   Justification

   Euclidean algorithm step 5.

   Shown in the video

21

The last non-zero remainder in the sequence of divisions is 21.

1. Diagram
   Observation

   The title card 'Example Euclidean Algorithm' is displayed with a classical Greek border design.

1. Text 'Example Euclidean Algorithm'

2. Greek key border

1. None

1. Static image

Introduces the topic of the video.

1. Diagram
   Observation

   An illustration of Euclid appears, followed by a quick visual demonstration of the algorithm on the numbers 104 and 84.

1. Illustration of Euclid

2. Long division steps for 104 and 84

1. The long division steps appear sequentially from left to right.

1. The Euclid illustration remains static.

Provides historical context and a brief visual overview of how the algorithm operates before diving into a detailed example.

1. Diagram
   Observation

   The screen clears and the problem 'Find gcd(1785, 546)' is presented. Long division steps are animated sequentially across the screen.

1. Problem statement

2. Sequential long division calculations

3. Arrows indicating the flow of numbers

4. Final conclusion text

1. Each division step appears one by one.

2. Arrows connect the divisor and remainder of one step to become the dividend and divisor of the next.

3. The final answer is written at the bottom.

1. The problem statement remains at the top.

Visually demonstrates the step-by-step execution of the Euclidean algorithm, highlighting the recursive nature of using the previous divisor and remainder for the next calculation.

1. Audio
   Observation

   The narrator states, 'What makes this method so powerful is you don't have to factor the numbers to find the greatest common divisor.'

To find the greatest common divisor of two numbers, you must first find their prime factorizations.

The Euclidean algorithm allows you to find the GCD efficiently through repeated long division, completely bypassing the need to factor the numbers.

1. Audio
   Observation

   The narrator introduces the Euclidean algorithm specifically as a method for finding the greatest common divisor.

The Euclidean algorithm is a specific computational method used to find the greatest common divisor of two integers.

1. Diagram
   Observation

   The final step of the derivation shows a remainder of 0, and an arrow points to the previous remainder (21) as the answer, directly illustrating the claim.

The step-by-step derivation for the example serves as a practical demonstration and verification of the general rule that the last non-zero remainder is the GCD.

1. Audio
   Observation

   The entire introductory segment explains the purpose and basic mechanics of the algorithm.

1. Euclidean Algorithm Method
2. Greatest Common Divisor (GCD)

1. Audio
   Observation

   The narrator explicitly states the stopping condition and the reason for it.

1. GCD is the Last Non-Zero Remainder