Greatest common divisor recurrences: subtraction and Euclidean algorithms

1. Formula
   Observation

   The document repeatedly shows $\gcd(a,b)$, and the code calls $\gcd(a,b)$.

2. Audio
   Observation

   The instructor says "greatest common divisor" multiple times.

$\gcd$

The greatest common divisor function for two integers.

The video does not specify the exact domain; non-negative integers are used in the examples.

1. Formula
   Observation

   The document formula is written as $\gcd(a,b)=\gcd(b,a-k\cdot b)$.

2. Formula
   Observation

   The code declares `const int $a = 24$;` and `const int $b = 504$;`.

$a,b$

The two integers involved in finding the greatest common divisor.

Integers in the example; the video does not give general restrictions.

1. Formula
   Observation

   The document states "For any integer $k$: $\gcd(a,b)=\gcd(b,a-k\cdot b)$."

2. Audio
   Observation

   The instructor says "First let $k$ be an arbitrary integer."

3. Formula
   Observation

   The code loop is written as `for (int $k=-1024$;k<=1024;++k)`.

$k$

An arbitrary integer parameter in the recurrence formula.

Any integer.

1. Formula
   Observation

   The document writes $\gcd(a,b)=\gcd(b,a\bmod b)$.

1. The video does not explain the definition of `mod`, sign conventions, or handling when $b=0$.

$a\bmod b$

The remainder term in the Euclidean algorithm formula.

Not specified in the video.

1. Formula
   Observation

   The document writes "Let $k=\lfloor a/b\rfloor$."

1. The video does not state that this expression is undefined when $b=0$.

$\lfloor a/b\rfloor$

The integer quotient obtained by taking the floor of $a/b$.

Not specified in the video.

1. Formula
   Observation

   The code contains `const int $a = 24$;`, `const int $b = 504$;`, and `for (int $k=-1024$;k<=1024;++k)`.

`int`

The integer type used in C++ to declare the example variables.

The video does not specify the range of values.

1. Formula
   Observation

   The code writes `cout << gcd(a, b) << endl;`.

2. Audio
   Observation

   The instructor says "I directly used the gcd function here... my C++ version is relatively new now, so it comes with the gcd function built-in."

1. The video does not specify which standard library header file is used; the screen shows `#include <bits/stdc++.h>`.

`gcd(a, b)`

A call to the greatest common divisor function in C++ code.

Two `int` values are passed in the example.

1. Formula
   Observation

   Code line 6 `const int $a = 24$;`; Lecture section 1 formula $\gcd(a,b)=\gcd(b,a-k\cdot b)$ contains $a$

2. Audio
   Observation

   When deriving $k=\lfloor a/b\rfloor$, the narrator calls it “the quotient of $a$ divided by $b$.”

a

The first integer participating in the greatest common divisor calculation; takes the value 24 in the code example

Integer

1. Formula
   Observation

   Code line 7 `const int $b = 504$;`; Lecture section 1 formula $\gcd(a,b)=\gcd(b,a-k\cdot b)$ contains $b$

2. Audio
   Observation

   The narrator says "$a$ divided by $b$, rounded down"

b

The second integer participating in the greatest common divisor calculation; takes the value 504 in the code example

Integer

1. Formula
   Observation

   Code line 8 `const int c = gcd(a, b);`; Line 11 `if (c != gcd(b, $a - k * b$))`

2. Audio
   Observation

   The narrator says "if c is not equal to it"

c

Variable in the code storing the result of $\gcd(a,b)$

Integer

1. Formula
   Observation

   Code line 10 `for (int $k=-1024$; k<=1024; ++k)`; Lecture section 1 "For any integer $k$: $\gcd(a,b)=\gcd(b,a-k\cdot b)$"

2. Audio
   Observation

   The narrator says "for any $k$", "for example when $k$ equals 1", "let $k$ equal $a$ divided by $b$, rounded down"

k

Integer parameter in the recurrence formula; iteration range in code is -1024 to 1024

Integer

1. Formula
   Observation

   Code line 8 `gcd(a, b)`; Lecture section 1 formula $\gcd(a,b)=\gcd(b,a-k\cdot b)$

2. Audio
   Observation

   The narrator reads "gcd a b equals gcd b a minus k times b"

$\gcd$

Greatest common divisor function

Operates on two integers, returns an integer

1. Formula
   Observation

   The document title is "Recurrence Formula for the Greatest Common Divisor of Two Numbers".

2. Formula
   Observation

   The document body states "For any integer $k$: $\gcd(a,b)=\gcd(b,a-k\cdot b)$."

3. Audio
   Observation

   The instructor says, “This time we will discuss the recurrence formula for the greatest common divisor of two numbers,” and “First let $k$ be an arbitrary integer; then the greatest common divisor of $a$ and $b$ equals the greatest common divisor of $b, a$ minus $k$ times $b$.”

The core formula given in the video transforms $\gcd(a,b)$ into $\gcd(b,a-k\cdot b)$, where $k$ can be any integer. The instructor emphasizes that for beginners in competitive programming, mastering this single formula is sufficient.

1. $k$ is any integer.

2. The video does not specify additional restrictions on $a,b$.

1. Formula
   Observation

   The document subsection title is "1.1 Subtraction Method".

2. Formula
   Observation

   The document writes "Let $k=1$, to get the Subtraction Method: $\gcd(a,b)=\gcd(b,a-b)$."

This is a special case of the core recurrence formula when $k=1$, replacing the first parameter with the difference of the two numbers each time.

1. Derived from the core formula by letting $k=1$.

2. The video does not specify size relationships or sign restrictions for $a,b$.

1. Recurrence Formula for GCD of Two Numbers

1. Formula
   Observation

   The document subsection title is "1.2 Euclidean Algorithm".

2. Formula
   Observation

   The document writes "Let $k=\lfloor a/b\rfloor$, to get the Euclidean Algorithm: $\gcd(a,b)=\gcd(b,a\bmod b)$."

1. The video does not explain the definition of `mod`, handling of $b=0$, or the relationship between the floor quotient and remainder.

This is a special case of the core recurrence formula when $k=\lfloor a/b\rfloor$, replacing the first parameter with the remainder of $a$ divided by $b$.

1. Derived from the core formula by letting $k=\lfloor a/b\rfloor$.

2. The video does not mention the usual prerequisite $b\neq 0$.

1. Recurrence Formula for GCD of Two Numbers

1. Formula
   Observation

   The code calls `gcd(a, b)`.

2. Audio
   Observation

   The instructor says "I directly used the gcd function here because my C++ version is relatively new now, so it comes with the gcd function built-in."

3. Audio
   Observation

   The instructor also says "But during exams, the C++ compiler version might not be this new, so you may need to implement the gcd function yourself during exams. We will discuss how to implement it later."

1. The video does not specify the exact C++ standard version or header file; the screen shows `#include <bits/stdc++.h>`.

The video demonstrates calling `gcd(a,b)` directly in a newer C++ environment to calculate the greatest common divisor, while reminding that exam environments may not support this built-in function and require manual implementation.

1. The video states the current C++ version is relatively new.

2. The video does not specify the exact standard version.

1. Formula
   Observation

   Lecture title "1 Recurrence Formula for GCD of Two Numbers"; Text "For any integer $k$: $\gcd(a,b)=\gcd(b,a-k\cdot b)$"

2. Audio
   Observation

   The narrator says "For any $k$, gcd a b equals gcd b a minus $k$ times $b$, always holds", "The first systematic professional recurrence formula we need to master"

The video presents the recurrence identity for the greatest common divisor: for any integer $k$, $\gcd(a,b)=\gcd(b,a-k\cdot b)$. This formula transforms the GCD of $(a,b)$ into the GCD of $(b,a-kb)$, serving as the unified source for the subsequent subtraction-based algorithm and the Euclidean algorithm.

1. $a,b$ are integers

2. $k$ is any integer

1. Formula
   Observation

   Lecture section 1.1 "Subtraction-based Algorithm"; "Let $k=1$, we get the subtraction-based algorithm: $\gcd(a,b)=\gcd(b,a-b)$"

2. Audio
   Observation

   The narrator says "For example, when $k$ equals 1, we get gcd a b equals gcd b a minus b, this is the famous subtraction-based algorithm"

In the recurrence formula $\gcd(a,b)=\gcd(b,a-k\cdot b)$, set $k=1$ to obtain $\gcd(a,b)=\gcd(b,a-b)$. The video names this special case the subtraction-based algorithm.

1. $k=1$

2. $a,b$ are integers

1. Recurrence Formula for GCD of Two Numbers

1. Formula
   Observation

   Lecture section 1.2 "Euclidean Algorithm"; "Let $k=\lfloor a/b\rfloor$, we get the Euclidean algorithm: $\gcd(a,b)=\gcd(b,a\bmod b)$"

2. Audio
   Observation

   The narrator says "If we let $k$ equal $a$ divided by $b$, rounded down... we get gcd a b equals gcd b a modulo b remainder, this is the famous Euclidean algorithm"

In the recurrence formula $\gcd(a,b)=\gcd(b,a-k\cdot b)$, set $k=\lfloor a/b\rfloor$. Then $a-kb=a-(\lfloor a/b\rfloor)b$ is the remainder of $a$ divided by $b$, giving $\gcd(a,b)=\gcd(b,a\bmod b)$. The video names this special case the Euclidean algorithm.

1. $k=\lfloor a/b\rfloor$

2. $a,b$ are integers

3. Video does not state $b\neq 0$

1. Recurrence Formula for GCD of Two Numbers

1. Formula
   Observation

   The document writes "For any integer $k$: $\gcd(a,b)=\gcd(b,a-k\cdot b)$."

2. Audio
   Observation

   The instructor repeats the formula and says "It is this formula."

1. The video does not provide a proof.

For any integer $k$, $\gcd(a,b)=\gcd(b,a-k\cdot b)$.

1. $k$ is any integer.

2. The video does not specify additional restrictions on $a,b$.

Holds for any integer $k$.

1. Formula
   Observation

   The document writes "Let $k=1$, to get the Subtraction Method: $\gcd(a,b)=\gcd(b,a-b)$."

When $k=1$, the core recurrence formula becomes $\gcd(a,b)=\gcd(b,a-b)$.

1. The core formula holds.

2. Take $k=1$.

Direct substitution within the formula framework given in the video.

1. Formula
   Observation

   The document writes "Let $k=\lfloor a/b\rfloor$, to get the Euclidean Algorithm: $\gcd(a,b)=\gcd(b,a\bmod b)$."

1. The video does not specify $b\neq 0$ nor the precise definition of `mod`.

When $k=\lfloor a/b\rfloor$, the core recurrence formula becomes $\gcd(a,b)=\gcd(b,a\bmod b)$.

1. The core formula holds.

2. Take $k=\lfloor a/b\rfloor$.

3. Usually requires $b\neq 0$, though not stated in the video.

Direct substitution within the formula framework given in the video.

1. Formula
   Observation

   The code has `const int $a = 24$;` and `const int $b = 504$;`.

2. Formula
   Observation

   The terminal outputs `24`.

3. Audio
   Observation

   The instructor says "The result is 24" and "When $a=24, b=504$, their greatest common divisor answer is 24."

In this example, $\gcd(24,504)=24$.

1. $a=24$.

2. $b=504$.

For the given numerical instance.

1. Audio
   Observation

   The instructor says "But during exams, the C++ compiler version might not be this new, so you may need to implement the gcd function yourself during exams."

1. The video does not specify the exact exam platform or compiler version.

The video warns that the C++ compiler version in exams might be older, so one cannot assume the `gcd` function is available and must be prepared to implement it manually.

1. The C++ compiler version in the exam environment might not be as new as the demo environment.

Stated as a general warning in the video, without formal quantifiers.

1. Audio
   Observation

   The narrator says "That is to say, for any $k$, gcd a b equals gcd b a minus $k$ times $b$, always holds"

2. Formula
   Observation

   Lecture section 1 writes "For any integer $k$: $\gcd(a,b)=\gcd(b,a-k\cdot b)$"

3. Diagram
   Observation

   After running the program in the terminal, only `**********` is output, with no $k$ satisfying the condition `c != gcd(b, $a - k * b$)`

For any integer $k$, $\gcd(a,b)=\gcd(b,a-k\cdot b)$ holds.

1. $a,b$ are integers

2. $k$ is any integer

Any integer $k$

1. Formula
   Observation

   Lecture section 1.1 "Let $k=1$, we get the subtraction-based algorithm: $\gcd(a,b)=\gcd(b,a-b)$"

2. Audio
   Observation

   The narrator says "When $k$ equals 1, we get gcd a b equals gcd b a minus b, this is the famous subtraction-based algorithm"

Letting $k=1$, the recurrence formula $\gcd(a,b)=\gcd(b,a-k\cdot b)$ reduces to $\gcd(a,b)=\gcd(b,a-b)$.

1. $a,b$ are integers

2. $k=1$

Existence of specific value $k=1$

1. Formula
   Observation

   Lecture section 1.2 "Let $k=\lfloor a/b\rfloor$, we get the Euclidean algorithm: $\gcd(a,b)=\gcd(b,a\bmod b)$"

2. Audio
   Observation

   The narrator says "If we let $k$ equal $a$ divided by $b$, rounded down... we get gcd a b equals gcd b a modulo b remainder, this is the famous Euclidean algorithm"

1. Video does not explicitly state the division prerequisite $b\neq 0$

Letting $k=\lfloor a/b\rfloor$, then $a-kb=a\bmod b$, thus $\gcd(a,b)=\gcd(b,a\bmod b)$.

1. $a,b$ are integers

2. $k=\lfloor a/b\rfloor$

3. Video does not state $b\neq 0$

Existence of specific value $k=\lfloor a/b\rfloor$

1. Formula
   Observation

   The document first gives $\gcd(a,b)=\gcd(b,a-k\cdot b)$, then writes "Let $k=1$, to get the Subtraction Method: $\gcd(a,b)=\gcd(b,a-b)$."

1. Expression

   $$\gcd(a,b)=\gcd(b,a-k\cdot b)$$
   Explanation

   Start from the core recurrence formula given in the video.

   Justification

   The document directly provides this formula.

   Shown in the video
2. Expression

   $$k=1$$
   Explanation

   Set the parameter $k$ to 1.

   Justification

   The document writes "Let $k=1$."

   Shown in the video
3. Expression

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

   Substitute to get the form of the Subtraction Method.

   Justification

   Substitute $k=1$ into the equality $a-k\cdot b=a-b$.

   Derived from the video

The Subtraction Method $\gcd(a,b)=\gcd(b,a-b)$ is a special case of the core recurrence formula when $k=1$.

1. Formula
   Observation

   The document first gives $\gcd(a,b)=\gcd(b,a-k\cdot b)$, then writes "Let $k=\lfloor a/b\rfloor$, to get the Euclidean Algorithm: $\gcd(a,b)=\gcd(b,a\bmod b)$."

1. The video does not show the intermediate explanation from $a-\lfloor a/b\rfloor b$ to $a\bmod b$.

1. Expression

   $$\gcd(a,b)=\gcd(b,a-k\cdot b)$$
   Explanation

   Start from the core recurrence formula given in the video.

   Justification

   The document directly provides this formula.

   Shown in the video
2. Expression

   $$k=\lfloor a/b\rfloor$$
   Explanation

   Set the parameter $k$ to the floor of $a/b$.

   Justification

   The document writes "Let $k=\lfloor a/b\rfloor$."

   Shown in the video
3. Expression

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

   Substitute to get the form of the Euclidean Algorithm.

   Justification

   The document directly gives this conclusion; supplementary explanation: usually because $a\bmod b=a-\lfloor a/b\rfloor b$.

   Shown in the video

The Euclidean Algorithm $\gcd(a,b)=\gcd(b,a\bmod b)$ is a special case of the core recurrence formula when $k=\lfloor a/b\rfloor$.

1. Formula
   Observation

   The code sets `const int $a = 24$;` and `const int $b = 504$;`.

2. Formula
   Observation

   The terminal outputs `24`.

3. Audio
   Observation

   The instructor says "The result is 24."

1. Expression

   $$a=24,\quad b=504$$
   Explanation

   Set the example values.

   Justification

   These constants are declared in the code.

   Shown in the video
2. Expression

   $$\gcd(24,504)$$
   Explanation

   Call the greatest common divisor function to calculate the example value.

   Justification

   The code writes `cout << gcd(a, b) << endl;`.

   Shown in the video
3. Expression

   $$24$$
   Explanation

   The program output is 24.

   Justification

   The terminal displays `24`, and the instructor confirms it verbally.

   Shown in the video

For the example values $a=24, b=504$, the video verifies $\gcd(24,504)=24$ through program output.

1. Formula
   Observation

   Code lines 6-12: `const int $a = 24$; const int $b = 504$; const int c = gcd(a, b); for (int $k=-1024$; k<=1024; ++k) { if (c != gcd(b, $a - k * b$)) { cout << k << endl; } }`

2. Diagram
   Observation

   Terminal at seconds 31-33 shows compilation and execution output `**********`, with no $k$ values output

3. Audio
   Observation

   The narrator says "You will find that this program only outputs a bunch of asterisks", "That is to say, for any $k$, gcd a b equals gcd b a minus $k$ times $b$, always holds"

1. Code defines `#define int int64_t` redefining `int` as 64-bit integer, but video does not explain its impact on the example's numerical range

1. Expression

   $$a=24,\ b=504,\ c=\gcd(a,b)$$
   Explanation

   The code first fixes $a=24$, $b=504$, and stores $\gcd(a,b)$ in variable $c$.

   Justification

   Directly given by code lines 6-8 in the video.

   Shown in the video
2. Expression

   $$\text{for }k=-1024,-1023,\ldots,1024:\ \text{check } c\neq \gcd(b,a-kb)$$
   Explanation

   The program iterates integer $k$ from -1024 to 1024, checking whether $\gcd(a,b)$ is not equal to $\gcd(b,a-kb)$.

   Justification

   Directly given by code lines 10-11 in the video.

   Shown in the video
3. Expression

   $$\text{output only } **********$$
   Explanation

   The execution result shows no $k$ satisfying `c != gcd(b, $a - k * b$)`, only outputting the asterisk marker after the loop ends.

   Justification

   Terminal output at seconds 31-33 shows `**********`.

   Shown in the video
4. Expression

   $$\gcd(24,504)=\gcd(504,24-k\cdot 504)\ \text{for tested } k$$
   Explanation

   Since no counterexample was found within the test range, the narrator concludes that the recurrence equality holds for any integer $k$.

   Justification

   Narrator summarizes at seconds 39-48 "For any $k$... always holds".

   Shown in the video

Code enumeration verification supports $\gcd(a,b)=\gcd(b,a-kb)$ having no counterexamples within the test range, which the narrator generalizes to hold for any integer $k$.

1. Formula
   Observation

   Lecture section 1 $\gcd(a,b)=\gcd(b,a-k\cdot b)$; Section 1.1 "Let $k=1$, we get the subtraction-based algorithm: $\gcd(a,b)=\gcd(b,a-b)$"

2. Audio
   Observation

   The narrator says "For example, when $k$ equals 1, we get gcd a b equals gcd b a minus b, this is the famous subtraction-based algorithm"

1. Expression

   $$\gcd(a,b)=\gcd(b,a-k\cdot b)$$
   Explanation

   Start from the general recurrence formula given in the video.

   Justification

   Formula from Lecture section 1.

   Shown in the video
2. Expression

   $$k=1$$
   Explanation

   Let parameter $k$ take the value 1.

   Justification

   Lecture section 1.1 "Let $k=1$".

   Shown in the video
3. Expression

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

   Substitution yields the form of the subtraction-based algorithm.

   Justification

   Substituting $k=1$ into $a-kb$ gives $a-b$.

   Derived from the video

The subtraction-based algorithm $\gcd(a,b)=\gcd(b,a-b)$ is a special case of the general recurrence formula when $k=1$.

1. Formula
   Observation

   Lecture section 1 $\gcd(a,b)=\gcd(b,a-k\cdot b)$; Section 1.2 "Let $k=\lfloor a/b\rfloor$, we get the Euclidean algorithm: $\gcd(a,b)=\gcd(b,a\bmod b)$"

2. Audio
   Observation

   The narrator says "$a$ divided by $b$, rounded down is the quotient of $a$ divided by $b$", "Dividend minus quotient times divisor equals remainder"

3. Animation
   Observation

   At seconds 99-107, formula $a-k\cdot b$ receives the handwritten annotation $a-\lfloor a/b\rfloor b$ above it, then an arrow points to $a\bmod b$.

1. Video does not explicitly state the division prerequisite $b\neq 0$

1. Expression

   $$\gcd(a,b)=\gcd(b,a-k\cdot b)$$
   Explanation

   Start from the general recurrence formula given in the video.

   Justification

   Formula from Lecture section 1.

   Shown in the video
2. Expression

   $$k=\lfloor a/b\rfloor$$
   Explanation

   Let parameter $k$ take the floor of $a$ divided by $b$, i.e., the quotient.

   Justification

   Lecture section 1.2 "Let $k=\lfloor a/b\rfloor$"; Narrator calls it "the quotient of $a$ divided by $b$".

   Shown in the video
3. Expression

   $$a-k\cdot b=a-\lfloor a/b\rfloor b$$
   Explanation

   Substitute $k=\lfloor a/b\rfloor$ into the second argument.

   Justification

   Algebraic substitution.

   Derived from the video
4. Expression

   $$a-\lfloor a/b\rfloor b=a\bmod b$$
   Explanation

   Narrator explains that dividend minus quotient times divisor equals remainder.

   Justification

   Narrator states at seconds 107-112 "Dividend minus quotient times divisor equals remainder".

   Shown in the video
5. Expression

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

   Obtain the form of the Euclidean algorithm.

   Justification

   Formula from Lecture section 1.2.

   Shown in the video

The Euclidean algorithm $\gcd(a,b)=\gcd(b,a\bmod b)$ is a special case of the general recurrence formula when $k=\lfloor a/b\rfloor$.

1. Formula
   Observation

   The code has `const int $a = 24$;`, `const int $b = 504$;`, and `cout << gcd(a, b) << endl;`.

2. Formula
   Observation

   The terminal outputs `24`.

3. Audio
   Observation

   The instructor says "For example, let's take an example", "Let integer $a$ equal... 24", "Let integer $b$ equal... 504", "The result is 24."

Given two integers $a=24$ and $b=504$, find their greatest common divisor.

1. $a=24$.

2. $b=504$.

3. Use C++ code to call `gcd(a,b)`.

Calculate $\gcd(24,504)$ and output the result.

1. Expression

   $$const int a = 24;$$
   Explanation

   Declare the first integer in the code.

   Justification

   The code line is visible on screen.

   Shown in the video
2. Expression

   $$const int b = 504;$$
   Explanation

   Declare the second integer in the code.

   Justification

   The code line is visible on screen.

   Shown in the video
3. Expression

   $$cout << gcd(a, b) << endl;$$
   Explanation

   Call the `gcd` function and output the result.

   Justification

   The code line is visible on screen; the instructor explains using the built-in `gcd` function of C++.

   Shown in the video
4. Expression

   $$24$$
   Explanation

   The terminal displays the program output.

   Justification

   The terminal area on screen shows `24`.

   Shown in the video

$\gcd(24,504)=24$.

The video verifies the result by running the C++ program and outputting 24 in the terminal.

1. Formula
   Observation

   Code lines 6-15 fully visible: `const int $a = 24$; const int $b = 504$; const int c = gcd(a, b); for (int $k=-1024$; k<=1024; ++k) { if (c != gcd(b, $a - k * b$)) { cout << k << endl; } } cout << "**********" << endl;`

2. Diagram
   Observation

   Terminal at seconds 31-33 shows `$ $g++ a$.cpp && ./a.out` followed by output `**********`

3. Audio
   Observation

   The narrator says "You will find that this program only outputs a bunch of asterisks"

1. Video does not show the implementation of the `gcd` function, only the call result

Given $a=24$, $b=504$, let $c=\gcd(a,b)$, iterate integer $k$ from -1024 to 1024, check if there exists $c\neq\gcd(b,a-kb)$.

1. $a=24$

2. $b=504$

3. $c=\gcd(a,b)$

4. $k\in[-1024,1024]$

Determine if there is any $k$ in the test range such that $\gcd(a,b)\neq\gcd(b,a-kb)$.

1. Expression

   $$c=\gcd(24,504)$$
   Explanation

   First calculate and store $\gcd(a,b)$.

   Justification

   Code line 8 `const int c = gcd(a, b);`.

   Shown in the video
2. Expression

   $$\text{for }k=-1024\text{ to }1024:\ \text{if }(c\neq\gcd(504,24-k\cdot 504))\ \text{print }k$$
   Explanation

   For each integer $k$, check if the equality fails; if so, print $k$.

   Justification

   Code lines 10-12.

   Shown in the video
3. Expression

   $$\text{print }**********$$
   Explanation

   After the loop ends, print asterisk marker to indicate program completion.

   Justification

   Code line 15; Narrator says "To mark that my entire program has finished running, we finally output a bunch of asterisks".

   Shown in the video
4. Expression

   $$\text{terminal output: }**********$$
   Explanation

   Actual terminal only displays asterisks, no $k$ values shown.

   Justification

   Terminal output at seconds 31-33.

   Shown in the video

No counterexamples were found in the test range $k=-1024,-1023,\ldots,1024$; the program only outputs `**********`.

Terminal output contains no $k$ values, only the loop end marker `**********`.

1. Diagram
   Observation

   The screen shows a dark-background document page titled "Recurrence Formula for the Greatest Common Divisor of Two Numbers".

2. Diagram
   Observation

   The page sequentially displays the core formula, 1.1 Subtraction Method, and 1.2 Euclidean Algorithm.

3. Animation
   Observation

   The mouse moves near the formulas and selects parts of the text.