Step 1: Start with two positive integers, a and b, where a > b. 🌟
Example: Let a = 56 and b = 12.
Step 2: Divide a by b to get the quotient q and remainder r such that a = bq + r, where 0 ≤ r < b. ➗
Example: 56 = 12 × 4 + 8 (remainder is 8).
Step 3: Check if r = 0. If true, b is the GCD of a and b. 🎯
Example: Since r ≠ 0 (remainder is 8), continue to the next step.
Step 4: Replace a with b and b with r. Repeat the process until r = 0. 🔄
Example:
12 = 8 × 1 + 4 (remainder is 4).
8 = 4 × 2 + 0 (remainder is 0).
The GCD is 4. 🎉