Find the greatest common divisor of 84 and 52

To find the greatest common divisor (GCD) of 84 and 52, we can use the method of prime factorization or the Euclidean algorithm. Here, we’ll apply both methods for clarity.

Method 1: Prime Factorization

First, we find the prime factors of each number:

• 84: 2 × 2 × 3 × 7 (or 2² × 3 × 7)
• 52: 2 × 2 × 13 (or 2² × 13)

Next, we identify the common prime factors. The only prime factor they have in common is 2, and the smallest power of 2 that appears in both factorizations is 2².

Thus, the GCD is:

GCD = 2² = 4

Method 2: Euclidean Algorithm

We can also find the GCD using the Euclidean algorithm:

1. Divide 84 by 52, which gives a quotient of 1 and a remainder of 32 (84 = 52 × 1 + 32).
2. Now, replace 84 with 52 and 52 with 32, and repeat the process: 52 ÷ 32 gives a quotient of 1 and a remainder of 20 (52 = 32 × 1 + 20).
3. Now, take 32 and 20: 32 ÷ 20 gives a quotient of 1 and a remainder of 12 (32 = 20 × 1 + 12).
4. Next, take 20 and 12: 20 ÷ 12 gives a quotient of 1 and a remainder of 8 (20 = 12 × 1 + 8).
5. Now with 12 and 8: 12 ÷ 8 gives a quotient of 1 and a remainder of 4 (12 = 8 × 1 + 4).
6. Finally, take 8 and 4: 8 ÷ 4 gives a quotient of 2 and a remainder of 0 (8 = 4 × 2 + 0).

When the remainder reaches 0, the divisor at that step is the GCD. Thus, the GCD is 4.

In conclusion, using both methods, we find that the greatest common divisor of 84 and 52 is 4.