Why does repeating the subtraction operation lead to a much smaller equivalent gcd problem?
Conditions
- The initial numbers are positive integers.
- The operation is subtracting the smaller from the larger.
- The goal is to preserve the gcd while reducing the numbers.
Reasoning, step by step
- Start with two positive integers and ().
- Replace with .
- Observe that , so the larger number decreases.
- Repeat the process.
- The numbers strictly decrease in magnitude.
- Eventually, the numbers become small enough that the gcd is obvious (e.g., one is zero or they are equal).
- The equivalence is maintained because the set of common divisors does not change.
Example
The script states: 'Subtracting the smaller positive integer from the larger preserves their common divisors. Repeating the operation leads to a much smaller equivalent gcd problem.'
Common misconceptions
- Thinking that the gcd changes as the numbers get smaller.
- Believing that the process might never end for certain pairs of integers.
- Confusing the reduction in magnitude with a loss of information about the gcd.
Watch the explanation
Connected concepts
Explore next
Related questions
The Euclidean algorithm moves the old divisor to the left-hand side (new dividend) and the old remainder to the smaller-number position (new divisor) to recursively reduce the problem. This shift ensures that each subsequent division step operates on smaller numbers while preserving the greatest common divisor of the original pair, continuing until a remainder of zero is reached.
Conditions: The algorithm is applied to two positive integers.; The previous remainder is not zero.; The process continues until a remainder of 0 is obtained.
For a nonnegative integer , the greatest common divisor of and is itself. This serves as the base case for the Euclidean algorithm, terminating the recursion when the second argument becomes zero.
Conditions: is a nonnegative integer.; The pair is .
To form the next division line, you take the divisor from the previous line and make it the dividend of the new line. Then, you take the remainder from the previous line and make it the divisor of the new line.
Conditions: You have just completed a division step in the Euclidean algorithm.; The previous remainder is not 0.
To start the Euclidean algorithm for , you write the larger number as the smaller number multiplied by an unknown quotient plus an unknown remainder. Specifically, you set up the division equation .
Conditions: The inputs are positive integers.; The larger number is placed on the left-hand side of the equation.; The quotient is an integer and the remainder satisfies .
The Euclidean algorithm using division terminates when one of the entries in the current pair becomes zero. Specifically, when the remainder in the step becomes zero, the next pair is or , and the algorithm stops, returning the non-zero entry as the gcd.
Conditions: The algorithm uses the step .; and are nonnegative integers.; Termination occurs when the second argument is 0.
Answers are generated from source material and independently checked. Consult the original video or creator if something is unclear.