Calculate Greatest Common Divisors via the Euclidean Algorithm

1. Audio
   Observation

   The introduction explains the greatest common divisor and illustrates it with integer pairs.

2. Formula
   Observation

   The introduction explains the greatest common divisor and illustrates it with integer pairs.

gcd(a,b)

The greatest integer that divides both integers a and b without a remainder.

Integers a and b, not both zero; GCD is taken positive.

1. Formula
   Observation

   The lemma on the board uses integer variables for its symmetry, divisibility and congruence statements.

a, b, c

Integer variables used to state the properties of the GCD and the Euclidean algorithm.

Integers

1. Formula
   Observation

   The board expresses the divisible difference as an integer multiple of the modulus.

2. Audio
   Observation

   The board expresses the divisible difference as an integer multiple of the modulus.

y

An integer such that by = a - c, derived from the divisibility condition b | (a - c).

Integers

1. Formula
   Observation

   The board carries the same GCD through several equivalent pairs.

2. Audio
   Observation

   The board carries the same GCD through several equivalent pairs.

$\gcd(\cdot,\cdot)$

Greatest common divisor of two integers.

Used here for integer pairs such as $(a,b)$, $(b,c)$, $(b,r_1)$, and $(r_1,r_2)$.

1. Formula
   Observation

   The displayed algebra replaces one integer by its difference with an integer multiple of the other.

2. Audio
   Observation

   The displayed algebra replaces one integer by its difference with an integer multiple of the other.

$a,b,c$

Integers in the lemma proving $\gcd(a,b)=\gcd(b,c)$ under the condition $b\mid a-c$.

Integers.

1. Formula
   Observation

   The integer multiplier appears in the divisibility equation and its rearrangement.

2. Audio
   Observation

   The integer multiplier appears in the divisibility equation and its rearrangement.

$y$

An integer witnessing that $a-c$ is a multiple of $b$.

$y\in\mathbb{Z}$.

1. Formula
   Observation

   A common divisor is introduced and tracked through the forward divisibility chain; the reverse argument is not separately shown.

2. Audio
   Observation

   A common divisor is introduced and tracked through the forward divisibility chain; the reverse argument is not separately shown.

1. The video verbally identifies $d$ as the greatest common divisor, but the displayed line only explicitly states $d\mid a$ and $d\mid b$ before the later conclusion about gcd equality.

$d$

An integer divisor of $a$ and $b$ used in the proof; verbally treated as the greatest common divisor.

$d\in\mathbb{Z}$.

1. Formula
   Observation

   The board uses the divisibility sign in the common-divisor argument.

2. Audio
   Observation

   The board uses the divisibility sign in the common-divisor argument.

$\mid$

Divisibility relation: $x\mid y$ means $x$ divides $y$.

Integers.

1. Formula
   Observation

   Successive divisions introduce quotients and remainders with boxed decreasing bounds.

2. Audio
   Observation

   Successive divisions introduce quotients and remainders with boxed decreasing bounds.

$q_1,q_2,r_1,r_2$

Quotients and remainders in successive division steps of the Euclidean algorithm.

Integers, with remainder bounds $0\le r_1<b$ and $0\le r_2<r_1$ implied by the division-algorithm context; the board explicitly shows only $r_1<b$ and $r_2<r_1$.

1. Formula
   Observation

   The board uses the dividend in the GCD reduction equations.

a

First integer input to the greatest common divisor function.

Positive integer in the ordered positive-input algorithm; nonnegative during the base case.

1. Formula
   Observation

   The board uses the divisor in the GCD reduction equations.

b

Second integer input to the greatest common divisor function.

Nonnegative integer, positive whenever division is performed.

1. Formula
   Observation

   The descending remainder chain reaches zero in the terminal argument.

$r_k$

Nonnegative remainder indexed along the Euclidean chain; editorial convention $r_0=b$ includes exact first-step divisibility.

Non-negative Integer

1. Audio
   Observation

   The definition and small-number examples introduce positive common divisors and coprimality.

2. Formula
   Observation

   The definition and small-number examples introduce positive common divisors and coprimality.

The GCD of two integers is the largest positive integer that divides both numbers without leaving a remainder. If the GCD of two numbers is 1, they are called coprime.

1. Integers a and b, not both zero; the greatest positive common divisor is used.

1. Audio
   Observation

   The narration contrasts a descending divisor search with the faster remainder algorithm.

A naive approach to finding the GCD involves checking every integer from the smaller number down to 1 to see if it divides both numbers. This method has a linear time complexity, making it inefficient for large numbers.

1. Positive integer inputs; linear worst-case count of divisibility tests in min(a,b), treating each arithmetic test as unit cost.

1. Definition of Greatest Common Divisor (GCD)

1. Formula
   Observation

   The first board statement says that exchanging the inputs preserves the GCD.

2. Audio
   Observation

   The first board statement says that exchanging the inputs preserves the GCD.

The order of the arguments in the GCD function does not affect the result.

1. Integers a and b, not both zero.

1. Definition of Greatest Common Divisor (GCD)

1. Formula
   Observation

   The next statement treats a positive input which divides the other input.

2. Audio
   Observation

   The next statement treats a positive input which divides the other input.

If a positive integer a divides another integer b, then the greatest common divisor of a and b is simply a.

1. $a > 0$

2. a divides b (a|b)

1. Definition of Greatest Common Divisor (GCD)

1. Formula
   Observation

   The third board statement identifies congruence as a way to preserve common divisors with the modulus.

2. Audio
   Observation

   The third board statement identifies congruence as a way to preserve common divisors with the modulus.

If two integers a and c are congruent modulo b, their greatest common divisors with b are identical. This property is the foundation of the Euclidean algorithm, allowing the reduction of large numbers.

1. Integers a and c; positive integer modulus b.

1. Definition of Greatest Common Divisor (GCD)

1. Formula
   Observation

   The board retains the symmetry statement for the GCD.

The video lists as a basic fact that swapping the two arguments does not change the greatest common divisor.

1. Integers $(a,b)$ not both zero; the GCD is positive.

1. Formula
   Observation

   The board retains the positive-divisor special case.

If $a$ is positive and divides $b$, then the greatest common divisor of $a$ and $b$ is exactly $a$.

1. $a>0$

2. $a\mid b$

1. Symmetry of gcd

1. Formula
   Observation

   The congruence lemma and forward common-divisor argument are shown; the public converse is an editorial completion.

2. Audio
   Observation

   The congruence lemma and forward common-divisor argument are shown; the public converse is an editorial completion.

1. The earlier native lemma frame confirms congruence, not the model-read set-membership notation. The source shows the forward divisor implication; the converse is supplied editorially.

For integer $a,c$ and positive $b$, replacing $a$ by $c=a-by$ preserves the GCD. The source displays the forward common-divisor implication. Editorial completion: a divisor of $b$ and $c$ also divides $a=c+by$, so both pairs have the same positive common divisors.

1. $a,c,y\in\mathbb Z$, $b>0$ is an integer.

2. $c=a-by$.

1. Symmetry of gcd

1. Formula
   Observation

   The board replaces a dividend–divisor pair by a divisor–remainder pair without changing the GCD.

2. Audio
   Observation

   The board replaces a dividend–divisor pair by a divisor–remainder pair without changing the GCD.

The Euclidean algorithm is presented as repeated application of the reduction lemma to division remainders: replace $(a,b)$ by $(b,r_1)$, then $(r_1,r_2)$, and so on, preserving the gcd at each step.

1. Integer inputs $a\ge b>0$, with standard nonnegative division remainders.

2. Divide by $r_1$ only while it is positive; stop if it is zero.

1. Gcd reduction under subtraction of a multiple

1. Formula
   Observation

   The board completes the remainder chain and identifies the final positive divisor.

2. Audio
   Observation

   The board completes the remainder chain and identifies the final positive divisor.

For positive integer inputs, replace the pair by the divisor and nonnegative remainder. Stop at zero and return the preceding positive divisor; exact first-step divisibility returns the original divisor.

1. Nonnegative integer inputs, not both zero; for the displayed division chain use $a\ge b>0$.

2. A recursive division requires $b>0$ and the nonnegative remainder; when $b=0$ return $a$.

1. Formula
   Observation

   The complexity slides discuss a remainder bound and a logarithmic call count; the public arithmetic-model conditions are editorial.

2. Formula
   Observation

   The complexity slides discuss a remainder bound and a logarithmic call count; the public arithmetic-model conditions are editorial.

For positive ordered inputs, within two recursive calls the larger parameter falls to at most half its earlier value, unless the algorithm already stops. This yields a logarithmic number of remainder calls in numerical magnitude under unit-cost arithmetic.

1. Integer $a>b>0$; $N=a+b$ is numerical magnitude, not bit length.

2. Each arithmetic remainder operation is counted as unit cost; this is not a bound on total bit operations.

1. Euclidean Algorithm Principle

1. Audio
   Observation

   The source groups the symmetry, divisibility and congruence properties into one supporting lemma.

2. Formula
   Observation

   The source groups the symmetry, divisibility and congruence properties into one supporting lemma.

The Euclidean algorithm relies on three properties of the GCD: commutativity, the case where one number divides the other, and the relationship between GCD and modular congruence.

1. The first two parts require their stated integer and positivity conditions; congruence is used with positive modulus b.

Universal quantification over integers a, b, c satisfying the specific conditions of each part.

1. Formula
   Observation

   The narration links the preceding GCD facts to the remainder algorithm.

2. Audio
   Observation

   The narration links the preceding GCD facts to the remainder algorithm.

The video presents three lemmas—symmetry of gcd, gcd when one positive integer divides another, and gcd preservation under subtracting a multiple—as the basis for explaining the Euclidean algorithm.

1. The integers are in the usual gcd setting.

2. For the second lemma, $a>0$ and $a\mid b$.

3. For the third lemma, $b\mid a-c$.

Universal over the displayed integer variables in each lemma.

1. Formula
   Observation

   The source states GCD equality after showing the forward implication; equality requires the editorial converse.

2. Audio
   Observation

   The source states GCD equality after showing the forward implication; equality requires the editorial converse.

1. The displayed proof explicitly tracks one common divisor $d$; full rigor would also require the reverse inclusion or an appeal to the definition of gcd, which is not separately written out in this clip.

Under the condition $b\mid a-c$, the greatest common divisor of $a$ and $b$ equals the greatest common divisor of $b$ and $c$.

1. $a,c\in\mathbb Z$, $b>0$ is an integer.

2. $b\mid(a-c)$.

For all integers $a,c$ and positive integer $b$ satisfying the hypothesis.

1. Formula
   Observation

   The native complexity slide compares the new remainder with half of the earlier dividend.

For integers $a>b>0$, the new second argument $a\bmod b$ is at most half the previous first argument $a$.

1. $a > b > 0$

For all valid inputs a, b

1. Formula
   Observation

   The board starts the congruence argument by expressing a difference as an integer multiple; later footage continues it.

2. Audio
   Observation

   The board starts the congruence argument by expressing a difference as an integer multiple; later footage continues it.

1. Only the beginning of this argument lies in the first 0–101-second analysis interval; the full source continues. The reverse common-divisor implication will be supplied as an editorial mathematical clarification.

1. Expression

   $$a \equiv c \pmod b$$
   Explanation

   Start with the assumption that a ≡ c (mod b).

   Justification

   Hypothesis of the third part of the lemma.

   Shown in the video
2. Expression

   $$b \mid (a - c)$$
   Explanation

   By the definition of congruence, b must divide the difference between a and c.

   Justification

   Definition of modular congruence.

   Shown in the video
3. Expression

   $$\exists y \in \mathbb{Z}, by = a - c$$
   Explanation

   This means there exists an integer y such that by equals a minus c.

   Justification

   Definition of divisibility.

   Shown in the video

The displayed equations start the argument. The source continues beyond this analysis interval; this partial derivation alone does not yet establish equality of the two GCDs.

1. Formula
   Observation

   The board derives divisibility of the difference and then states equality; the reverse divisor-set argument is editorial.

2. Audio
   Observation

   The board derives divisibility of the difference and then states equality; the reverse divisor-set argument is editorial.

1. The clip shows the forward divisibility chain clearly, but it does not separately display the converse inclusion needed for a fully symmetric proof of equality of gcd sets.

1. Expression

   $$\exists y\in\mathbb{Z}\; by=a-c$$
   Explanation

   Start from the hypothesis that $b$ divides $a-c$, so there is an integer $y$ with $by=a-c$.

   Justification

   Definition of divisibility.

   Shown in the video
2. Expression

   $$c=a-by$$
   Explanation

   Rearrange the equation to express $c$ in terms of $a$, $b$, and $y$.

   Justification

   Algebraic rearrangement of $by=a-c$.

   Shown in the video
3. Expression

   $$\exists d\in\mathbb{Z},\ d\mid a,\ d\mid b$$
   Explanation

   Take an integer $d$ that divides both $a$ and $b$; the speaker identifies this as the greatest common divisor context.

   Justification

   Assumption in the proof setup / definition of common divisor.

   Shown in the video
4. Expression

   $$d\mid a-by$$
   Explanation

   Since $d$ divides $a$ and $b$, it also divides the combination $a-by$.

   Justification

   Closure of divisibility under integer linear combinations; the speaker describes it as multiplying by a factor of $b$.

   Shown in the video
5. Expression

   $$d\mid c$$
   Explanation

   Because $c=a-by$, the previous divisibility statement becomes $d\mid c$.

   Justification

   Substitution using $c=a-by$.

   Shown in the video
6. Expression

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

   The source states equality after the forward implication. To complete the proof, also take any positive divisor of $b$ and $c$; it divides $a=c+by$. Thus the two positive-common-divisor sets coincide.

   Justification

   Editorial reverse inclusion, together with the observed forward inclusion, justifies equality of the GCDs.

   Supplementary explanation

The equality is correct for integer $a,c$ and positive integer $b$. Its full proof uses both common-divisor implications; the reverse implication above is editorial, not separately displayed in the source.

1. Formula
   Observation

   The board shows successive symbolic divisions and corresponding GCD equalities.

2. Audio
   Observation

   The board shows successive symbolic divisions and corresponding GCD equalities.

1. The stopping case is outside this 101–202-second analysis interval and is explained later in the full source.

1. Expression

   $$a=bq_1+r_1,\ 0\le r_1<b$$
   Explanation

   Apply division of $a$ by $b$ to introduce quotient $q_1$ and remainder $r_1$.

   Justification

   Division algorithm for integers.

   Supplementary explanation
2. Expression

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

   Replace the pair $(a,b)$ by $(b,r_1)$ without changing the gcd.

   Justification

   Reduction lemma, completed with the editorial reverse-divisor argument.

   Shown in the video
3. Expression

   $$b=r_1q_2+r_2,\ 0\le r_2<r_1$$
   Explanation

   When $r_1>0$, divide $b$ by $r_1$; otherwise stop.

   Justification

   Division algorithm for integers.

   Supplementary explanation
4. Expression

   $$\gcd(b,r_1)=\gcd(r_1,r_2)$$
   Explanation

   Repeat the same reduction to pass from $(b,r_1)$ to $(r_1,r_2)$.

   Justification

   Same reduction lemma applied to the next pair.

   Shown in the video
5. Expression

   $$\dots$$
   Explanation

   Repeat while the current divisor is positive. Positive integer remainders strictly decrease, so the process terminates rather than continuing indefinitely.

   Justification

   Editorial nonnegative-integer descent; the next source interval presents the terminal rule.

   Supplementary explanation

The Euclidean algorithm is obtained by iterating the identity $\gcd(x,y)=\gcd(y,\operatorname{rem}(x,y))$ through successively smaller remainders.

1. Formula
   Observation

   The native slide uses contradiction for a remainder bound. Its zero-quotient aside contains a typo; the corresponding public step is editorially corrected.

1. The native slide incorrectly says that zero quotient would imply $k=b$; the correct consequence is $k=a$. The public quotient step below is an editorial correction, not a faithful copy of that incorrect aside.

1. Expression

   $$a \% b = k, \quad k > a/2$$
   Explanation

   Under integer $a>b>0$, suppose for contradiction that the remainder exceeds half the dividend.

   Justification

   Assumption for contradiction

   Supplementary explanation
2. Expression

   $$a = q \cdot b + k, \quad k < b$$
   Explanation

   By definition of modulo, a can be written as quotient times divisor plus remainder, where remainder is less than divisor.

   Justification

   Division algorithm

   Shown in the video
3. Expression

   $$a/2 < k < b < a$$
   Explanation

   Combining the assumption $k > a/2$ with $k < b$ gives this chain.

   Justification

   Transitivity of inequality

   Shown in the video
4. Expression

   $$q = 1$$
   Explanation

   The bound $b>a/2$ rules out a quotient of at least two, and $a>b$ requires a positive quotient. Thus $q=1$. In particular, zero quotient would give $k=a$, not the slide’s $k=b$.

   Justification

   Editorially corrected integer quotient bounds.

   Supplementary explanation
5. Expression

   $$k + b > a/2 + a/2 = a$$
   Explanation

   Substituting $q=1$ into $a = b + k$ gives $a = b + k$. But we established $k > a/2$ and $b > a/2$, so their sum exceeds a.

   Justification

   Arithmetic substitution

   Shown in the video
6. Expression

   $$a>a$$
   Explanation

   We derived $k + b > a$, but the equation $a = q*b + k$ with $q=1$ implies $a = b + k$. This is a contradiction.

   Justification

   Logical contradiction

   Supplementary explanation

The assumed large remainder is impossible, so $k\le a/2$. Applying this across two calls gives the parameter reduction used to bound the number of remainder calls.

1. Formula
   Observation

   The introduction displays small integer pairs to explain GCD and coprimality; their divisor lists below are editorial verification.

2. Audio
   Observation

   The introduction displays small integer pairs to explain GCD and coprimality; their divisor lists below are editorial verification.

Find the GCD of several pairs of integers.

1. Pairs: (7, 21), (24, 30), (7, 9)

Determine the greatest common divisor for each pair.

1. Explanation

   For 7 and 21, 7 divides 21, so the GCD is 7.

   Justification

   Definition of GCD.

   Shown in the video
2. Explanation

   For 24 and 30, the common divisors are 1, 2, 3, 6. The greatest is 6.

   Justification

   Definition of GCD.

   Supplementary explanation
3. Explanation

   For 7 and 9, the only common divisor is 1.

   Justification

   Definition of GCD.

   Shown in the video

GCD(7, 21) = 7; GCD(24, 30) = 6; GCD(7, 9) = 1.

The speaker notes that since GCD(7, 9) = 1, the numbers 7 and 9 are coprime.

1. Diagram
   Observation

   The opening presents a fast-GCD question and a pair of integer inputs.

1. Text boxes

2. Blue background

1. Transition from general title to specific problem example.

The opening motivates efficient GCD computation with a larger integer pair; that pair is posed rather than worked through numerically in the source.

1. Diagram
   Observation

   A gridded whiteboard contains a numbered lemma and progressively written equations.

2. Animation
   Observation

   A gridded whiteboard contains a numbered lemma and progressively written equations.

1. Grid paper background

2. Handwritten text and formulas

1. Appearance of the lemma statement.

2. Sequential writing of the proof steps for the third part of the lemma.

1. The first two parts of the lemma remain static while the third is being proven.

The board organizes the lemma and its equations; the reverse common-divisor argument requires an editorial supplement.

1. Diagram
   Observation

   The gridded board adds algebra lines beneath the numbered lemma.

2. Animation
   Observation

   The gridded board adds algebra lines beneath the numbered lemma.

1. Title “Euclidean Algorithm”

2. Handwritten lemma list

3. Proof lines with $\exists y\in\mathbb{Z}$, $c=a-by$, $\exists d\in\mathbb{Z}$, divisibility statements, and $\gcd(a,b)=\gcd(b,c)$

1. Lines are added one after another beneath the lemma list.

2. The proof grows from the hypothesis $by=a-c$ to the conclusion $\gcd(a,b)=\gcd(b,c)$.

1. The board remains a single static writing surface with no coordinate axes or geometric figures.

2. The lemma numbering stays visible above the proof.

The board organizes the reduction argument; its forward direction is observed and the public reverse direction is explicitly editorial.

1. Animation
   Observation

   The view moves to a lower writing area for successive remainder equations.

2. Diagram
   Observation

   The view moves to a lower writing area for successive remainder equations.

1. Scrolled board view

2. New handwritten equations for successive divisions

3. Ellipsis indicating continuation

1. The earlier lemma proof shifts upward out of primary focus.

2. New lines are written below to apply the lemma to division remainders.

3. The final visible state includes an ellipsis after the second reduction.

1. The same mathematical theme continues from lemma to algorithm.

2. No numerical example is introduced; the derivation stays symbolic.

The scroll marks the transition from proving the key lemma to using it as the recursive mechanism of the Euclidean algorithm.

1. Animation
   Observation

   The board view moves to connect the remainder chain with the earlier GCD facts.

1. Handwritten mathematical equations

1. View moves vertically to show context

1. Equations remain static while camera pans

Visual aid to connect the final result back to the initial lemma definitions.

1. Diagram
   Observation

   The source displays a Java-style recursive function with a zero-divisor guard.

1. Code block

1. Transition from whiteboard to typed code

1. Code logic matches the mathematical derivation

Demonstrates how the recursive mathematical definition translates directly into programming syntax.

1. Audio
   Observation

   The narration motivates a more efficient algorithm by comparing it with exhaustive candidate testing.

One might think checking all numbers down to 1 is a viable strategy for computing GCD.

The video highlights that this brute-force approach has linear time complexity, making it too slow for large numbers, thus motivating the Euclidean algorithm.

1. Formula
   Observation

   The source explicitly shows the forward common-divisor implication before concluding equality.

2. Audio
   Observation

   The source explicitly shows the forward common-divisor implication before concluding equality.

One might think the written chain alone proves equality of the two gcds just by showing that every common divisor of $a$ and $b$ divides $c$.

To justify $\gcd(a,b)=\gcd(b,c)$ rigorously, one also needs the reverse inclusion (or an equivalent argument using the definition of greatest common divisor). The clip shows the forward direction explicitly and then states the equality.

1. Formula
   Observation

   The current analysis interval ends while the remainder chain continues; the full source later explains the stopping rule.

2. Audio
   Observation

   The current analysis interval ends while the remainder chain continues; the full source later explains the stopping rule.

A viewer may assume the displayed chain already specifies the full Euclidean algorithm.

This 101–202-second interval establishes the reduction mechanism. The full source later stops when the remainder becomes $0$ and returns the preceding positive divisor; there is no full-source media omission.

1. Audio
   Observation

   The source transitions from direct divisor search to the Euclidean algorithm.

The Euclidean algorithm is presented as an efficient method specifically for applying and computing the Greatest Common Divisor.

1. Formula
   Observation

   The congruence statement supplies the invariant used in subsequent GCD reductions.

Congruence preserves common divisors with the modulus and is applied to reduce GCD computations; this is an invariant, rather than a generalization of the GCD definition.

1. Audio
   Observation

   The remainder steps use the common-divisor invariant established with editorial completion.

2. Formula
   Observation

   The remainder steps use the common-divisor invariant established with editorial completion.

The reduction lemma, with its editorial reverse-common-divisor completion, justifies each Euclidean remainder step.

1. Formula
   Observation

   The equal-GCD statements exchange the order of the integer pair.

2. Audio
   Observation

   The equal-GCD statements exchange the order of the integer pair.

1. The clip does not explicitly point to the symmetry lemma at the moment of conclusion; the connection is inferred from the displayed statements.

Symmetry of gcd allows the reduction result to be written with the second argument first, yielding the form $\gcd(a,b)=\gcd(b,c)$ used in the algorithm.

1. Formula
   Observation

   The division equations provide the next argument of the GCD.

2. Audio
   Observation

   The division equations provide the next argument of the GCD.

Each Euclidean step is an instance of the reduction lemma after expressing the dividend as divisor times quotient plus remainder.

1. Audio
   Observation

   The narration links the recursive function with the preceding remainder rule.

The mathematical principle is applied directly to write the recursive function.

1. Formula
   Observation

   The remainder bound is used to motivate the logarithmic number of recursive calls.

The corrected halving argument implies a logarithmic number of recursive remainder calls for ordered positive integers under unit-cost arithmetic.

1. Audio
   Observation

   The source compares the number of arithmetic tests needed by a direct search.

1. Brute Force Method for GCD

1. Formula
   Observation

   The congruence lemma states an equality between two GCD expressions.

1. GCD and Modular Congruence

1. Formula
   Observation

   The initial board equations translate congruence into divisibility.

1. Proof of GCD and Modular Congruence Property (Part 1)

1. Formula
   Observation

   The board connects subtraction of an integer multiple to common-divisor preservation.

2. Audio
   Observation

   The board connects subtraction of an integer multiple to common-divisor preservation.

1. Gcd reduction under subtraction of a multiple
2. Proof that $b\mid a-c$ implies $\gcd(a,b)=\gcd(b,c)$

1. Formula
   Observation

   Successive divisions are accompanied by equal-GCD identities.

2. Audio
   Observation

   Successive divisions are accompanied by equal-GCD identities.

1. Euclidean algorithm reduction rule
2. Recursive reduction chain of the Euclidean algorithm

1. Formula
   Observation

   The highlighted remainder inequalities motivate descent and termination.

2. Audio
   Observation

   The highlighted remainder inequalities motivate descent and termination.

1. Euclidean algorithm reduction rule
2. Recursive reduction chain of the Euclidean algorithm

1. Formula
   Observation

   The source compares parameter reduction with the resulting call count.

1. Time Complexity of Euclidean Algorithm
2. Remainder Halving Property

1. Formula
   Observation

   The displayed function returns its first argument when its second argument is zero.

1. Euclidean Algorithm Principle