Euclidean Algorithm: Explanation, Proof and C++ Implementation

1. Formula
   Observation

   The slide displays $\gcd(a, b) =$ max {k | k|a and k|b} as well as $\gcd(a, b) = \gcd(|a|, |b|)$.

2. Audio
   Observation

   The narrator mentions the "greatest common divisor" and reads out the equivalent definition.

gcd(a, b)

the greatest common divisor of a and b

integer inputs not both zero; greatest common divisors and common factors are treated as positive integers (explicit scope of this site)

1. Formula
   Observation

   The slide definition uses letters a, b, c to represent integers and their common divisors.

a, b, c

a and b are the integers whose greatest common divisor is sought, and c is a candidate for their greatest common divisor

integer inputs not both zero; greatest common divisors and common factors are treated as positive integers (explicit scope of this site)

1. Formula
   Observation

   The slide uses k|a and k|b to denote divisibility relations.

2. Audio
   Observation

   The narrator specifically explains which term is the divisor and which is the dividend in the divisibility notation.

|

divisibility symbol; k|a means k divides a

divisibility relation between integers

1. Formula
   Observation

   The equivalent definition is written as max {k | k|a and k|b}.

k

a common divisor that divides both a and b

integer inputs not both zero; greatest common divisors and common factors are treated as positive integers (explicit scope of this site)

1. Formula
   Observation

   The slide gives $\gcd(a, b) = \gcd(|a|, |b|)$.

|a|, |b|

the absolute values of a and b

absolute value on real numbers/integers

1. Formula
   Observation

   The slide body writes $\gcd(a,b)$, and the Notes write k | a and $a = mk$.

2. Audio
   Observation

   Original audio explanation: k divides a is equivalent to a being equal to m times k.

a, b

The two integers whose greatest common divisor is being discussed.

Integers; further restricted to $a ≥ b > 0$ in subsequent proof pages.

1. Formula
   Observation

   The definition sentence on the first page states that c is called the greatest common divisor of a and b.

c

Candidate for the greatest common divisor.

Positive integer; integer inputs not both zero (scope explicitly stated on this site)

1. Formula
   Observation

   The page writes $\gcd(a,b)=$max{k, where k|a and k|b}, and the Notes also write k|a.

2. Audio
   Observation

   The narrator explains the roles of the left and right terms in the divisibility symbol |.

k

Candidate for a common divisor that divides both a and b.

Common positive divisor; integer inputs not both zero (scope explicitly stated on this site)

1. Formula
   Observation

   The Notes provide $a = mk$.

2. Audio
   Observation

   The narrator reads k|a as 'a equals m times k'.

m

The multiplier such that $a = mk$ holds.

Integer.

1. Formula
   Observation

   The second page writes let d be the greatest common divisor of a and b, and lists $d = \gcd(a,b)$.

2. Audio
   Observation

   Original audio states: Let d be the greatest common divisor of a and b.

d

The greatest common divisor of a and b.

Positive integer.

1. Formula
   Observation

   The page writes $a = q_1·b + r_1$, and $q_1 =$ floor($a / b$).

2. Audio
   Observation

   Original audio states: $q_1$ is called the quotient.

3. Animation
   Observation

   At 152 seconds, a quotient label points to $q_1$.

q₁

The quotient in division with remainder.

Integer.

1. Formula
   Observation

   The page writes $0 ≤ r_1 < b$.

2. Audio
   Observation

   Original audio states: The value of $r_1$ is between 0 and b; $r_1$ is called the remainder.

3. Animation
   Observation

   At 157 seconds, the remainder label points to $r_1$.

r₁

The remainder when a is divided by b.

Integer, satisfying $0 ≤ r_1 < b$.

1. Formula
   Observation

   The slide title is "1. Definition of Greatest Common Divisor", listing two determining conditions.

2. Audio
   Observation

   The narrator explains condition one and condition two item by item.

3. Formula
   Observation

   This site clarifies the common factor, positive number convention, and the non-zero input scope; supplementary conditions are not attributed to the original video's exact words.

$c$ must be a common divisor of $a,b$, and any common divisor of the two numbers must divide $c$. This distinguishes whether it is a common divisor and whether it satisfies maximality; numbers dividing only one of the inputs are not included in the second condition. This site supplements the explicit scope of $c>0$ and inputs not both zero.

1. Integers $a,b$ are not both zero (scope note by this site)

2. $c$ is a positive integer and divides both $a,b$

3. Any common positive divisor divides $c$

1. gcd(a, b)
2. a, b, c
3. |

1. Formula
   Observation

   The slide writes $\gcd(a, b) =$ max {k | k|a and k|b}, and further writes $\gcd(a, b) = \gcd(|a|, |b|)$.

2. Audio
   Observation

   The narrator explains that because the greatest common divisor sought is positive, it can be reduced to the absolute value form.

3. Formula
   Observation

   This site clarifies the common factor, positive number convention, and the non-zero input scope; supplementary conditions are not attributed to the original video's exact words.

Defining $\gcd(a,b)$ as the maximum of the common positive divisors shows that changing the sign of the inputs does not affect the structure of common divisors; thus taking absolute values preserves the greatest common divisor. This site explicitly limits the inputs to not both zero.

1. Integers $a,b$ are not both zero (this site explicitly excludes the case where the maximum cannot be taken)

2. $k$ is a positive integer dividing both $a,b$

1. Definition of the Greatest Common Divisor
2. k
3. |a|, |b|

1. Formula
   Observation

   The Notes at the bottom of the slide explain that the divisibility notation "|" distinguishes which is the dividend and which is the divisor, giving the example that k|a is equivalent to $a = mk$.

2. Audio
   Observation

   The narrator verbally emphasizes the roles of the left and right terms in the divisibility notation.

The video specifically explains the direction of the divisibility notation "|": the left side is the divisor, and the right side is the dividend. Taking k|a as an example, it is equivalent to the existence of an integer m such that $a = mk$.

1. Used for divisibility relations between integers

2. The left side is the divisor, and the right side is the dividend

1. |
2. k

1. Formula
   Observation

   The title of the first page is '1. Definition of Greatest Common Divisor'.

2. Formula
   Observation

   The body lists two conditions: 1. c is a divisor of a and b; 2. Any divisor of a and b is a divisor of c.

A positive integer $c$ is a common divisor of the two inputs, and any common positive divisor of them divides $c$. A common divisor is not just a divisor of one of the numbers; this site explicitly states that the inputs are integers not both zero.

1. Integer inputs not both zero; the greatest common divisor takes a positive value (site scope statement).

2. The second condition quantifies over common positive divisors of the two inputs.

1. Reading and roles of the divisibility notation

1. Formula
   Observation

   The page writes: The following is an equivalent definition: $\gcd(a, b) =$ max {k, where k | a and k | b}.

The greatest common divisor is the maximum value among the common positive divisors. This site explicitly states that the inputs are not both zero, avoiding the case where the set has no maximum when both are zero.

1. Integer inputs not both zero (explicit scope of this site).

2. Candidates are common positive divisors.

1. Two-condition definition of the greatest common divisor

1. Formula
   Observation

   Yellow text on the first page writes $\gcd(a,b)=\gcd(a,-b)=\gcd(-a,b)=\gcd(-a,-b)=\gcd(|a|,|b|)$.

The video directly gives a chain of properties: changing the signs of a and b does not change the greatest common divisor, so the discussion can be reduced to the non-negative absolute value case.

1. Integer inputs not both zero (site scope statement).

1. Two-condition definition of the greatest common divisor
2. Set maximum definition of the greatest common divisor

1. Formula
   Observation

   The Notes write that the divisibility symbol '|' distinguishes who is the dividend and who is the divisor. For example, k | a is equivalent to $a = mk$.

2. Audio
   Observation

   Original audio states: k divides a is equivalent to a being equal to m times k. Thus, the left term is the divisor, and the right term is the dividend.

The video specifically explains the directionality of the vertical bar symbol: the left side is the divisor, and the right side is the dividend; k|a means there exists an integer m such that $a=mk$.

1. k, a, and m are integers.

2. The video emphasizes this is a memory point, not a derivation.

1. Formula
   Observation

   The title of the second page is '2. Proof of Euclidean Algorithm'.

2. Formula
   Observation

   The body writes: To find the greatest common divisor of integers a and b, without loss of generality assume $a ≥ b > 0$, and let d be the greatest common divisor of a and b.

3. Audio
   Observation

   Original audio states: Now we formally begin the proof of the Euclidean algorithm... without loss of generality assume a is greater than or equal to b, which is greater than 0.

When entering the proof, the video first fixes the goal: to find the greatest common divisor of integers a and b; then makes a sorting assumption without loss of generality $a ≥ b > 0$, and denotes the greatest common divisor as d.

1. a and b are integers.

2. The proof page explicitly assumes $a ≥ b > 0$.

1. Two-condition definition of the greatest common divisor
2. Set maximum definition of the greatest common divisor

1. Formula
   Observation

   The page writes: By the definition of division, we can obtain: $a = q_1 · b + r_1$. ($q_1 =$ floor($a / b$), $0 ≤ r_1 < b$.)

2. Audio
   Observation

   The narration explains the division identity, the floor quotient and the nonnegative remainder bound.

3. Animation
   Observation

   From 149 to 158 seconds, the dividend, quotient, divisor and remainder labels appear in order.

The video defines the key tool in the proof as division with remainder: a is written as $q_1b+r_1$, where $q_1$ is the quotient, $r_1$ is the remainder, and the remainder is strictly less than the divisor b. The screen also uses label boxes to name a, $q_1$, b, and $r_1$ as Dividend, Quotient, Divisor, and Remainder respectively.

1. Used in the context of integer division where $a ≥ b > 0$.

2. The video does not separately prove this division definition, but cites it directly.

1. Initial setup for the proof of the Euclidean algorithm

1. Formula
   Observation

   The slide title is "2. Proof of Euclidean Algorithm." The text begins with "To find the greatest common divisor of integers a and b, without loss of generality assume $a ≥ b > 0$. Let d be the greatest common divisor of a and b."

2. Audio
   Observation

   The narrator discusses the divisibility of a and b by d and subsequent derivations in this section.

This segment enters the "Proof of Euclidean Algorithm" section. It first sets up the problem: given integers a and b, assume without loss of generality that $a ≥ b > 0$. Let d be the greatest common divisor of a and b. Then, using the division algorithm, introduce quotient $q_1$ and remainder $r_1$ to establish the relationship between a, b, and $r_1$, preparing to prove $\gcd(a,b)=\gcd(b,r_1)$.

1. a and b are integers

2. The video explicitly assumes $a ≥ b > 0$

3. $q_1$ and $r_1$ are defined by the division algorithm

1. Formula
   Observation

   The slide states "∵ Equations ① and ②, ∴ $d | (a - q_1·b) = d | r_1$ …④" and "∵ Equations ② and ④, ∴ d is simultaneously a common factor of b and $r_1$."

2. Audio
   Observation

   The audio applies the divisibility of the GCD to the linear combination of the difference, concluding it divides the remainder, and thus is a common factor of the new pair.

This method first uses $d=\gcd(a,b)$ to obtain $d\mid a$ and $d\mid b$. Then, utilizing the property that divisibility is closed under linear combinations, it derives $d\mid(a-q_1b)$. Since $a-q_1b=r_1$, it follows that $d\mid r_1$. Combining this with $d\mid b$, we conclude that d is a common factor of both b and $r_1$. This step proves the direction that "an element d from the set of common factors of (a,b) belongs to the set of common factors of (b,$r_1$)."

1. $d=\gcd(a,b)$ has been established

2. $a=q_1b+r_1$ has been used

3. Property that divisibility is closed under linear combinations is used

1. Initial Setup for the Correctness Proof of the Euclidean Algorithm

1. Formula
   Observation

   The lower half of the proof takes an arbitrary common factor c of the new pair, uses $q_1b+r_1=a$ to restore c's divisibility of a; since c is also a common factor of the original pair, $c≤d$. Combined with d itself dividing b and $r_1$, it concludes the GCD of the new pair equals d.

2. Audio
   Observation

   The narrator sequentially explains taking an arbitrary c, restoring c|a via linear combination of sum, comparing c with the original GCD d, and finally merging with the first half to get the same GCD.

After completing the proof that "d is a common factor of b and $r_1$, " the video proceeds to prove maximality: take any common factor c of b and $r_1$. Then $c\mid b$ and $c\mid r_1$, so c divides their linear combination $q_1b+r_1$. Since $q_1b+r_1=a$, we get $c\mid a$. Given $c\mid b$, c is also a common factor of a and b. Because $d=\gcd(a,b)$, any common factor of a and b cannot exceed d, so $c\le d$. Combining this with the previously proven fact that d itself is a common factor of b and $r_1$, we know the greatest common divisor of b and $r_1$ is exactly d.

1. c is taken as an arbitrary common factor of b and $r_1$

2. $a=q_1b+r_1$ is used

3. Maximality definition of $d=\gcd(a,b)$ is used

1. Initial Setup for the Correctness Proof of the Euclidean Algorithm
2. From $\gcd(a,b)$ to d dividing b and $r_1$

1. Formula
   Observation

   New yellow text on the page writes: Boldly hypothesize: the greatest common divisor of a and b is equivalent to the greatest common divisor of b and $r_1$.

2. Audio
   Observation

   Original audio states: Next, let us boldly hypothesize that the greatest common divisor of a and b is equivalent to the greatest common divisor of b and $r_1$.

1. At the end of the clip, only this proposition to be proved is proposed, without a complete proof.

Under the current setup, the video proposes the proposition to be proved: $\gcd(a,b)$ is equivalent to $\gcd(b,r_1)$.

1. a and b are integers.

2. $a ≥ b > 0$.

3. $a = q_1·b + r_1$, and $0 ≤ r_1 < b$.

For integers a and b satisfying the above conditions and their remainder $r_1$ from division with remainder.

1. Formula
   Observation

   The slide first states "Bold Hypothesis: The greatest common divisor of a and b is equivalent to the greatest common divisor of b and $r_1$, " then through two parts of argument concludes "c_max = $d = \gcd(b, r_1)$. Q.E.D."

2. Audio
   Observation

   The narrator explicitly states at the end, "c_max is the greatest common divisor of b and $r_1$. Q.E.D."

For integers a, b satisfying $a ≥ b > 0$, and $a=q_1b+r_1$ with $0≤r_1<b$, it holds that $\gcd(a,b)=\gcd(b,r_1)$.

1. a and b are integers

2. $a ≥ b > 0$

3. $a=q_1b+r_1$

4. $q_1=\lfloor a/b\rfloor$

5. $0≤r_1<b$

Holds for integers a, b, $q_1$, $r_1$ satisfying the above conditions; the proof uses universal quantification over "any common factor c."

1. Formula
   Observation

   Left side explicitly writes $\gcd(a,b) = \gcd(b, a$ mod b).

2. Audio
   Observation

   The narrator verbally restates it as "the greatest common divisor of a and b equals the greatest common divisor of b and the remainder".

In the context of this segment, $\gcd(a,b)=\gcd(b, a\bmod b)$.

1. Integers $a\ge b>0$, following the proof conditions from the previous part of the original video.

2. Remainder is determined by division with a positive divisor.

3. The previous bidirectional common factor and maximality proof supports this invariant summary.

For the pair of integer inputs a,b discussed in the video.

1. Formula
   Observation

   Last row on the right writes $d = \gcd(a,b) = r_n$, and the row above is $r_{n-1}=q_{n+1}r_n+0$.

2. Audio
   Observation

   The narrator says, "and r n minus 1 and r n can be divisible. Then d, i.e., the greatest common divisor, is denoted as r n."

If consecutive divisions with remainder proceed to $r_{n-1}=q_{n+1}r_n+0$, then $\gcd(a,b)=r_n$.

1. There exists a chain of consecutive divisions with remainder as shown.

2. $r_n$ is the last non-zero remainder.

3. $r_{n-1}$ is divisible by $r_n$.

For the situation at the termination of this remainder chain.

1. Audio
   Observation

   The original audio clearly distinguishes between the terminating zero remainder and the last positive divisor that gives the answer.

2. Formula
   Observation

   The formula page states $r_{n-1}=q_{n+1}r_n+0$ and $d=\gcd(a,b)=r_n$.

In the sequence of successive divisions of the Euclidean algorithm, when the remainder of a certain step is 0, the smaller number $r_n$ from the previous step equals the greatest common divisor of the original two numbers.

1. Successive divisions with remainder have been performed according to the Euclidean algorithm

2. $r_n$ is the last non-zero remainder

Holds for integers a, b satisfying the algorithm process

1. Formula
   Observation

   The text on the left states $\gcd(a,b)=\gcd(b,a\bmod b)$.

2. Formula
   Observation

   The code comment states // successive division $\gcd(a,b)=\gcd(b,r)$.

Finding the greatest common divisor of a and b can be transformed into finding the greatest common divisor of b and the remainder of a divided by b.

1. a, b are integers

2. The video's code page requires $a \ge b > 0$

Holds for applicable inputs

1. Formula
   Observation

   The actual final frame table starts from $a=q_1b+r_1$, with a total of 10 rows of division; the last row is $r_8=q_{10}r_9+r_{10}$, where $r_{10}=0$ and $r_9=1078$.

2. Audio
   Observation

   The original audio counts ten rounds of calculation and gives the result 1078.

For the example inputs $a=1160718174$ and $b=316258250$, the manual calculation process shown in the video performs a total of 10 rounds of division with remainder, ultimately yielding the greatest common divisor 1078.

1. Using this specific test sample

Holds for this numerical example

1. Formula
   Observation

   The page lists: From the known conditions, we can obtain: d | a ...①, d | b ...②, $d = \gcd(a,b)$ ...③.

2. Audio
   Observation

   The narrator reads these three items one by one.

1. Expression

   $$d\mid a$$
   Explanation

   Since d is denoted as the greatest common divisor of a and b, d must first be a divisor of a.

   Justification

   Using the 'common divisor' condition from the previously given definition of the greatest common divisor.

   Shown in the video
2. Expression

   $$d\mid b$$
   Explanation

   Similarly, d must also be a divisor of b.

   Justification

   Using the 'common divisor' condition from the definition of the greatest common divisor.

   Shown in the video
3. Expression

   $$d=\gcd(a,b)$$
   Explanation

   The page lists this notation itself as item ③, serving as the starting point for subsequent arguments.

   Justification

   From the proof setup 'let d be the greatest common divisor of a and b'.

   Shown in the video

Obtain three numbered facts ① d|a, ② d|b, ③ $d=\gcd(a,b)$, preparing for the subsequent comparison of $\gcd(a,b)$ and $\gcd(b,r_1)$.

1. Formula
   Observation

   Under 'Careful Argument', the page writes: ∵ Equations ① and ②, ∴ $d | (a - q_1 · b) = d | r_1$ ...④.

2. Formula
   Observation

   The next line writes: ∵ Equations ② and ④, ∴ d is simultaneously a common divisor of b and $r_1$.

3. Audio
   Observation

   The narration begins the argument using the first numbered premise as the current interval ends.

1. The clip only shows the beginning of this half-direction, without showing the complete conclusion, nor the reverse direction argument.

1. Expression

   $$d\mid a,\ d\mid b$$
   Explanation

   First cite the previously established ① and .

   Justification

   From the definition of the greatest common divisor.

   Shown in the video
2. Expression

   $$d\mid (a-q_1\cdot b)$$
   Explanation

   Since d divides both a and b, it also divides the linear combination of a minus $q_1$ times b.

   Justification

   Using the standard property that divisibility is closed under linear combinations; the video does not verbally expand on the name of this principle.

   Shown in the video
3. Expression

   $$a-q_1\cdot b=r_1$$
   Explanation

   From the definition of division with remainder $a=q_1·b+r_1$, rearranging gives $a-q_1·b=r_1$.

   Justification

   Using the division definition given earlier.

   Shown in the video
4. Expression

   $$d\mid r_1$$
   Explanation

   Substituting the previous step, we get that d divides $r_1$, which is item ④ on the page.

   Justification

   Substitution of equals.

   Shown in the video
5. Expression

   $$d\mid b\land d\mid r_1$$
   Explanation

   Combining ② and the newly obtained ④, it shows that d is simultaneously a common divisor of b and $r_1$.

   Justification

   Definition of common divisor.

   Shown in the video

The visible conclusion within the clip stops at 'd is simultaneously a common divisor of b and $r_1$'; to completely prove $\gcd(a,b)=\gcd(b,r_1)$, it is still necessary to continue arguing maximality and the other direction, which do not appear in this clip.

1. Formula
   Observation

   The upper half of the proof lists d|a, d|b, $d=\gcd(a,b)$, and $a=q_1b+r_1$, using the linear combination of the difference to transfer divisibility to $r_1$; then states d divides both b and $r_1$.

2. Audio
   Observation

   The narrator verbally recites these steps, describing $a-q_1b$ as a linear combination of a and b.