輾轉相除法完整解析｜原理＋實作步驟＋範例教學｜最大公因數 GCD 快速求法

1. Formula
   Observation

   The whiteboard displays a ÷ $b = q$ ... r and a = bq + r

a

Dividend

Positive integer

1. Formula
   Observation

   The whiteboard displays a ÷ $b = q$ ... r and a = bq + r

b

Divisor

Positive integer

1. Formula
   Observation

   The whiteboard displays a ÷ $b = q$ ... r

q

Quotient

Non-negative integer

1. Formula
   Observation

   The whiteboard displays a ÷ $b = q$ ... r and a = bq + r

r

Remainder

Non-negative integer

1. Formula
   Observation

   The whiteboard displays (a, b) = (b, r)

(a, b)

Greatest common divisor of a and b

Pair of positive integers

1. Formula
   Observation

   The whiteboard displays Let (a, b) = m

m

Assumed greatest common divisor of a and b

Positive integer

1. Formula
   Observation

   The whiteboard displays a = mk_1

$k_1$

Integer factor after dividing a by m

Integer

1. Formula
   Observation

   The whiteboard displays b = mk_2

$k_2$

Integer factor after dividing b by m

Integer

1. Audio
   Observation

   The speaker explains that the Euclidean algorithm is used to find the greatest common divisor of two numbers, by repeatedly dividing the larger number by the smaller one until one side becomes zero.

2. Diagram
   Observation

   The left side of the screen shows the numbers 4369 and 5911, with lines drawn to separate columns.

The Euclidean algorithm is a method for calculating the greatest common divisor (GCD) of two positive integers. Its core operation involves dividing the larger number by the smaller number to obtain a remainder, then using the original divisor and the new remainder as the dividend and divisor for the next round. This process repeats until the remainder is zero. At this point, the last non-zero divisor is the GCD of the two numbers.

1. Applicable to two positive integers

2. Each division yields a non-negative remainder

3. Termination condition is when the remainder equals zero

1. Audio
   Observation

   The speaker mentions that the Euclidean algorithm is based on the Division Principle.

2. Formula
   Observation

   The whiteboard displays a ÷ $b = q$ ... r and a = bq + r.

For any integer a and positive integer b, there exist unique integers q and r such that a = bq + r and $0 \le r < b$. Here, q is called the quotient and r is called the remainder. This is the mathematical basis for each step of the Euclidean algorithm.

1. b is a positive integer

2. r is a non-negative integer less than b

1. Audio
   Observation

   The speaker explains that the GCD of a and b is equal to the GCD of b and r, and provides a proof.

2. Formula
   Observation

   The whiteboard displays (a, b) = (b, r), and derives $r = m(k_1 - k_2q)$.

1. The video only proves that m is also a divisor of r, thereby concluding that the GCD of (b, r) is at least m, but it does not strictly prove that no common divisor larger than m exists (i.e., the reverse inclusion is not proven).

If a = bq + r, then the GCD of a and b is equal to the GCD of b and r. This means that when finding the GCD, the larger pair (a, b) can be replaced by the smaller pair (b, r), thereby gradually reducing the problem size.

1. a, b, q, r are integers

2. a = bq + r

1. Division Principle

1. Audio
   Observation

   The speaker asserts that the GCD of a and b is equal to the GCD of b and r.

2. Formula
   Observation

   The whiteboard displays (a, b) = (b, r).

1. The proof in the video only shows that common divisors of (a,b) are also divisors of (b,r), without fully proving the equality of the sets in both directions, but the conclusion itself is a correct standard theorem.

For integers a, b, q, r satisfying a = bq + r, gcd(a, b) = gcd(b, r).

1. a = bq + r

For all integers a, b, q, r satisfying the condition

1. Formula
   Observation

   The whiteboard sequentially writes: Let (a,b)=m, a=mk_1, b=mk_2, substituting into a=bq+r gives mk_1 = mk_2q + r, rearranging gives $r = m(k_1 - k_2q)$.

1. The proof is incomplete, showing only m | r, not gcd(b,r) | m.

1. Expression

   $$\text{設 } (a, b) = m$$
   Explanation

   Assume the greatest common divisor of a and b is m.

   Justification

   Definition

   Shown in the video
2. Expression

   $$a = mk_1, \quad b = mk_2$$
   Explanation

   According to the definition of GCD, both a and b are divisible by m.

   Justification

   Definition of divisibility

   Shown in the video
3. Expression

   $$a = bq + r \implies mk_1 = mk_2q + r$$
   Explanation

   Substitute the expressions for a and b into the Division Principle equation.

   Justification

   Substitution

   Shown in the video
4. Expression

   $$r = mk_1 - mk_2q = m(k_1 - k_2q)$$
   Explanation

   Rearrange terms and factor out m.

   Justification

   Algebraic manipulation

   Shown in the video
5. Expression

   $$m \mid r$$
   Explanation

   Since $k_1$, $k_2$, and q are integers, ($k_1 - k_2q$) is an integer, so m divides r.

   Justification

   Definition of divisibility

   Shown in the video

The video concludes that m is also a divisor of r, therefore the GCD of b and r includes at least m (the video states 'it will be m', omitting the rigorous two-way argument).

1. Diagram
   Observation

   The whiteboard displays the complete long division process: 5911÷4369 remainder 1542, 4369÷1542 remainder 1285, 1542÷1285 remainder 257, 1285÷257 remainder 0.

2. Audio
   Observation

   The speaker reads out the result of each division step synchronously.

Calculate gcd(5911, 4369).

1. $a = 5911$

2. $b = 4369$

Find the greatest common divisor of the two numbers.

1. Expression

   $$5911 = 4369 \times 1 + 1542$$
   Explanation

   Divide the larger number by the smaller number, quotient 1, remainder 1542.

   Justification

   Division Principle

   Shown in the video
2. Expression

   $$4369 = 1542 \times 2 + 1285$$
   Explanation

   Divide the previous divisor 4369 by the remainder 1542, quotient 2, remainder 1285.

   Justification

   Division Principle

   Shown in the video
3. Expression

   $$1542 = 1285 \times 1 + 257$$
   Explanation

   Divide the previous divisor 1542 by the remainder 1285, quotient 1, remainder 257.

   Justification

   Division Principle

   Shown in the video
4. Expression

   $$1285 = 257 \times 5 + 0$$
   Explanation

   Divide the previous divisor 1285 by the remainder 257, quotient 5, remainder 0.

   Justification

   Division Principle

   Shown in the video

gcd(5911, 4369) = 257

When the remainder is 0, the divisor 257 is the greatest common divisor.

1. Formula
   Observation

   The whiteboard displays (5911, 4369) = (4369, 1542) = (1542, 1285) = (1285, 257) = 257.

2. Audio
   Observation

   The speaker explains how to apply the theory to the specific numbers from earlier, replacing pairs step by step.

Explain why the above long division calculation yields the correct greatest common divisor.

1. Previous long division results

2. Theorem (a, b) = (b, r)

Establish the equivalence chain between number pairs.

1. Expression

   $$(5911, 4369) = (4369, 1542)$$
   Explanation

   Because $5911 = 4369\times 1 + 1542$.

   Justification

   GCD Reduction Property

   Shown in the video
2. Expression

   $$(4369, 1542) = (1542, 1285)$$
   Explanation

   Because $4369 = 1542\times 2 + 1285$.

   Justification

   GCD Reduction Property

   Shown in the video
3. Expression

   $$(1542, 1285) = (1285, 257)$$
   Explanation

   Because $1542 = 1285\times 1 + 257$.

   Justification

   GCD Reduction Property

   Shown in the video
4. Expression

   $$(1285, 257) = 257$$
   Explanation

   Because $1285 = 257\times 5 + 0$, 257 divides 1285.

   Justification

   Divisibility Property

   Shown in the video

257

The final result matches the long division calculation.

1. Diagram
   Observation

   Displays the title "Euclidean Algorithm" and a cartoon character.

1. Text: Euclidean Algorithm

2. Cartoon character

1. Static image

Introduction to the topic.

1. Animation
   Observation

   As the speaker explains, the numbers for the long division appear sequentially on the whiteboard: 1, 4369, 1542; 2, 3084, 1285; 1, 1285, 257; 5, 1285, 0.

1. Numbers 5911, 4369

2. Long division structure

1. Remainder changes from 1542 to 1285, then to 257, and finally to 0

2. Divisor updates to the previous remainder

1. Each operation is Larger Number ÷ Smaller Number

Visually demonstrates the iterative process of the algorithm until the remainder is zero.

1. Animation
   Observation

   The whiteboard writes out the Division Principle formula and the derivation of GCD equality line by line.

1. Variables a, b, q, r, m, $k_1$, $k_2$

2. Equations

1. Transition from concrete calculations to abstract symbolic derivation

1. Logical order: Definition -> Assumption -> Substitution -> Conclusion

Shows the number theory foundation behind the algorithm.

1. Audio
   Observation

   The speaker says, 'So m is also one of the divisors of r... the GCD of b and r will be m'.

Believing that proving only that divisors of gcd(a,b) are also divisors of gcd(b,r) implies they are equal.

A rigorous proof requires bidirectional deduction: proving both gcd(a,b) | gcd(b,r) and gcd(b,r) | gcd(a,b) to establish equality. The video only shows the former (m | r); although the conclusion is correct, the argument is mathematically incomplete.

1. Audio
   Observation

   The speaker explicitly states that the Euclidean algorithm is based on the Division Principle.

The Division Principle provides the mathematical legitimacy and uniqueness guarantee for each step of 'dividing the larger by the smaller to get the remainder' in the Euclidean algorithm.

1. Formula
   Observation

   The (a,b)=(b,r) on the whiteboard directly supports the iterative logic of the algorithm.

The reduction property of the GCD is the fundamental reason why the Euclidean algorithm can solve the problem by continuously reducing the size of the number pairs.

1. Audio
   Observation

   Detailed explanation of operational steps and example calculation.

1. Definition and Operational Steps of the Euclidean Algorithm
2. Using the Euclidean Algorithm to Find GCD of 5911 and 4369

1. Formula
   Observation

   Derivation of the Division Principle and GCD properties.

1. Division Principle
2. Reduction Property of Greatest Common Divisor
3. Proof of GCD Reduction Property (One-way)