[Number & Operations · Core Concepts ② - Greatest Common Divisor] The Essence of GCD: Common Divisor Theorem, Coprime Classification & 3 Practical Applications

Integrated Math 1 (Middle) · Core Concepts ② [Numbers & Operations: GCD & Applications]

The Essence of GCD: Common Divisor Theorem, Coprime Classification & 4 Practical Applications

From the invariant divisor theorem and coprime definitions to exponent comparison algorithms, integer denominator conditions, and remainder reversal rules

🌱 The Greatest Common Divisor is a mathematical tool for extracting the 'largest common building block' shared between numbers
While elementary arithmetic identifies common divisors by listing factors individually, secondary mathematics uses prime factorization to analyze atomic structures and isolate shared building blocks via algebraic algorithms.

"All common divisors of two or more numbers are divisors of their GCD, and in prime factorized form, we strictly select common prime bases with smaller or equal exponents." Mastering this invariant principle instantly demystifies integer denominator constraints and complex remainder reversal problems in seconds.
CORE THEORY 1

The Fundamental Common Divisor Theorem & Coprime (Relatively Prime) Definition

Govern all common divisors through their GCD alone, and establish rigorous definitions for coprime integer pairs.

[1] The Common Divisor Invariance Theorem
The common divisors of two or more natural numbers are strictly identical to the divisors of their Greatest Common Divisor (GCD).
Thus, instead of cataloging divisors for each number separately, prime-factorizing the GCD and computing its divisors is the premier analytical strategy.

[2] Definition of Coprime (Relatively Prime)
Two natural numbers whose GCD is exactly $1$ are called 'coprime'.
1. The number $1$ is coprime to every natural number (e.g., 1 and 7, 1 and 100).
2. Any two distinct prime numbers are unconditionally coprime (e.g., 3 and 5, 7 and 11).
3. Crucial Warning: Two numbers can be coprime even if both are composite numbers ($8 = 2^3$ and $9 = 3^2$ share only 1 as a common factor, making them coprime).
[Diagram 1] Subset Relationship: Common Divisors and GCD (e.g., 24 and 36)
GCD of 24 and 36
12
$12 = 2^2 \times 3$
➔
All Common Divisors of 24 and 36
1, 2, 3, 4, 6, 12
Matches divisors of 12: $(2+1)(1+1) = 6$
✏️ [Example 1] Finding Perfect Square Common Divisors via GCD
When the greatest common divisor of natural numbers $A$ and $B$ is $72$, find the number of common divisors that are perfect squares.
💡 Yulcho's Pro-Tip: The exact values of $A$ and $B$ are irrelevant. Their common divisors are exclusively the divisors of 72. Factorize 72 and filter for even prime exponents.
View Solution & Answer (Click)
1. Prime-factorize GCD 72:
$72 = 2^3 \times 3^2$

2. Select even powers ($k^2$ divisors):
Choices for prime 2: $2^0 = 1, 2^2 = 4$
Choices for prime 3: $3^0 = 1, 3^2 = 9$
Square divisors are $1 \times 1 = 1^2$, $4 \times 1 = 2^2$, $1 \times 9 = 3^2$, $4 \times 9 = 6^2 = 36$.
There are 4 perfect square common divisors.
Answer: 4
✏️ [Example 1-2] Identifying the Second-Largest Common Divisor
For three numbers $2^2 \times 3^3 \times 5^2$, $2^2 \times 3 \times 7^2$, and $2^3 \times 3^4 \times 11$, find the second-largest common divisor.
💡 Yulcho's Pro-Tip: All common divisors divide the GCD. The largest common divisor is the GCD ($G$) itself; the second-largest common divisor is $G$ divided by its smallest prime factor (2), namely $G \div 2$.
View Solution & Answer (Click)
1. Calculate the GCD:
Common prime bases are 2 and 3.
Minimum exponent for 2: $2$
Minimum exponent for 3: $1$
$\text{GCD} = G = 2^2 \times 3 = 12$

2. Order common divisors descendingly:
Divisors of 12: $12, 6, 4, 3, 2, 1$
Largest: $12$
Second-largest: $12 \div 2 = 6$ ($2 \times 3$)
Answer: 6 (or $2 \times 3$)
CORE THEORY 2

Algorithms for Finding the GCD via Prime Factorization

Extract the greatest common divisor systematically using prime factor exponents.

Two-Step Protocol for GCD in Exponential Form:
Step 1: Fully decompose each integer into prime-factor powers.
Step 2: Select only common prime bases, choosing the smaller or equal exponent for each shared base.

Why do we select the smaller exponent?
Between $2^3$ and $2^2$, $2^3$ contains $2^2$ as a divisor, but $2^2$ cannot divide $2^3$. The maximum power that can simultaneously divide both without remainder is restricted by the smaller exponent ($2^2$).
[Diagram 2] Two Algorithms for Finding the GCD of 60, 84, and 126
[Method 1] Repeated Division (Ladder Method)
 2 ) 60  84  126
 ---
 3 ) 30  42   63
 ---
     10  14   21 (No common divisor > 1)
Multiply left-side common divisors:
$\text{GCD} = 2 \times 3 = 6$
[Method 2] Prime Factor Exponent Comparison
 $60 = 2^2 \times 3^1 \times 5^1$
 $84 = 2^2 \times 3^1 \times 7^1$
$126 = 2^1 \times 3^2 \times 7^1$
--------------------------------
$\text{GCD} = \mathbf{2^1 \times 3^1 = 6}$
Select shared bases 2 and 3 with minimal powers:
$\text{GCD} = 2^1 \times 3^1 = 6$
✏️ [Example 2] Reverse Deduction of Missing Exponents from GCD
The GCD of $2^a \times 3^3 \times 5$, $2^3 \times 3^b$, and $2^2 \times 3^2 \times c$ is $2^2 \times 3$. Find natural numbers $a, b$ and single-digit prime $c$. (where $a \ge 2$)
💡 Yulcho's Pro-Tip: The GCD exponent is the minimum among the terms. For base 3, the minimum is 1, forcing $b = 1$. The absence of 5 and $c$ in the GCD means they cannot be common to all three terms.
View Solution & Answer (Click)
1. Base 2 exponents: $a, 3, 2$. Minimum is 2, satisfying $a \ge 2$.
2. Base 3 exponents: $3, b, 2$. The GCD power is 1, so $\min(3, b, 2) = 1 \implies b = 1$.
3. Prime $c$: Must not be 2, 3, or 5 (to avoid making 5 a common factor). Among single-digit primes (2, 3, 5, 7), $c = 7$.
Thus, $a = 2, b = 1, c = 7$.
Answer: $a = 2, b = 1, c = 7$
CORE THEORY 3

4 Essential Application Protocols for GCD Word Problems

Standard protocols for word problems involving phrases like 'as many as possible' or 'largest possible dimension'.

Type ① Equal Distribution (Grouping)
Distributing items equally to the maximum number of people without remainder:
Maximum people = GCD of the quantities
Type ② Tiling a Rectangle with Squares
Covering an $A \times B$ rectangle with largest identical squares without gaps:
Square side length = $\text{GCD}(A, B)$
Total tiles $= (A \div G) \times (B \div G)$
Type ③ Natural Number Denominators
When $\frac{a}{n}$ and $\frac{b}{n}$ both simplify to integers:
Denominator $n$ = common divisor of $a$ and $b$
Largest integer $n$ = $\text{GCD}(a, b)$
Type ④ Division with Non-Zero Remainders
Dividing by unknown divisor $x$ leaving excess or shortage:
Subtract surplus ($A - p$), add deficit ($B + q$)
Divisor $x$ divides GCD (Condition: $x > \text{remainder}$)
✏️ [Example 3] Tiling Wall Dimensions and Total Tile Count
A rectangular wall measures $180\text{ cm}$ in length and $108\text{ cm}$ in height. We want to tile it completely with the largest possible identical square tiles without cutting. Find the side length of the tile and the total number of tiles needed.
💡 Yulcho's Pro-Tip: The tile side is $\text{GCD}(180, 108)$. Determine total tiles by multiplying tiles across length and height to avoid computational slip-ups.
View Solution & Answer (Click)
1. Find the tile side length:
$180 = 2^2 \times 3^2 \times 5$, $108 = 2^2 \times 3^3$
$\text{GCD} = 2^2 \times 3^2 = 36\text{ cm}$

2. Compute total tiles needed:
Horizontal count: $180 \div 36 = 5$
Vertical count: $108 \div 36 = 3$
Total tiles: $5 \times 3 = 15$
Answer: Side length: $36\text{ cm}$, Total tiles: $15$
✏️ [Example 4] Natural Number Denominator Constraints
Find the greatest natural number $n$ such that both fractions $\frac{18}{n}$ and $\frac{27}{n}$ evaluate to natural numbers.
💡 Yulcho's Pro-Tip: For the fraction to become an integer, denominator $n$ must divide numerators 18 and 27 simultaneously. The greatest $n$ is $\text{GCD}(18, 27)$.
View Solution & Answer (Click)
1. $n$ must be a common divisor of 18 and 27.
2. The largest common divisor is the GCD:
$18 = 2 \times 3^2$, $27 = 3^3$
$\text{GCD} = 3^2 = 9$
Thus, the greatest natural number $n$ is 9.
Answer: 9
✏️ [Example 5] Deducing the Divisor with Non-Zero Remainders
When 150 is divided by a natural number, it leaves a remainder of 6. When 95 is divided by the same natural number, it leaves a remainder of 5. Find the greatest such natural number.
💡 Yulcho's Pro-Tip: Subtract excess remainders first: $150 - 6 = 144$ and $95 - 5 = 90$. Ensure the calculated divisor strictly exceeds both remainders (6 and 5).
View Solution & Answer (Click)
1. Correct for exact divisibility:
$150 - 6 = 144$
$95 - 5 = 90$

2. Calculate the GCD of 144 and 90:
$144 = 2^4 \times 3^2$
$90 = 2 \times 3^2 \times 5$
$\text{GCD} = 2 \times 3^2 = 18$

3. Remainder condition check:
The divisor must exceed remainder 6. Since $18 > 6$, it is valid.
Answer: 18
WARNING

3 Exam Traps in Greatest Common Divisors

🚨 [Trap 1] Believing "Two coprime numbers must both be prime"
Counterexample: $8$ and $9$ are both composite, yet their GCD is 1, making them coprime. 'Coprime' describes a relative divisor relationship between numbers, not an intrinsic prime property of individual numbers.
🚨 [Trap 2] Confusing "Tile Side Length" with "Total Tiles Needed"
Always verify what the final sentence asks: the square tile dimension ($\text{GCD}$) or the total quantity of tiles required ($(\text{Length}/G) \times (\text{Width}/G)$).
🚨 [Trap 3] Omitting the condition "Divisor > Remainder" in Reversals
When listing divisors of the GCD, any candidate less than or equal to the remainder must be strictly eliminated. If the remainder is 6, divisors 1, 2, 3, and 6 cannot be solutions.
🌿 Yulcho's Masterclass Review
"The Greatest Common Divisor is not mere mechanical division. It is the fundamental algebraic process of extracting the maximal common atomic block shared among numbers. Understanding that common divisors divide the GCD, and adhering to smaller prime exponents, lays the groundwork for factoring out common terms in high school algebra."
Having completed our GCD theoretical foundations and 4 core application protocols, our next post explores: [Integrated Math 1 (Middle) · Problem Types ②] Greatest Common Divisor: 15 Benchmark Types & 1:1 Parallel Diagnostic Drills.

Comments

Popular posts from this blog

Authentic Reference Models Beyond Basic Rulers

[Math Column]Studying Alongside Dedicated Peers: Becoming Each Other’s Lifelong Catalyst

[High School Math] Coordinate Geometry: 15 Essential Practice Problems on Section Formulas (Internal & External Division)