PGCD : 4 MÉTHODES. Quelle sera ta préférée ?

Introduction

This tutorial will guide you through four different methods to calculate the Greatest Common Divisor (PGCD) or GCD in French. Understanding how to find the PGCD is essential for simplifying fractions, solving problems in number theory, and enhancing your overall mathematical skills. Let’s dive into each method step-by-step.

Step 1: Listing the Divisors

In this method, you identify all the divisors of each number and find the largest one that they share.

1. Find the divisors of each number:

   • For example, to find the PGCD of 12 and 18:
     • Divisors of 12: 1, 2, 3, 4, 6, 12
     • Divisors of 18: 1, 2, 3, 6, 9, 18

2. Identify the common divisors:

   • Common divisors of 12 and 18: 1, 2, 3, 6

3. Determine the greatest common divisor:

   • The PGCD is 6.

Practical Tip

This method can be time-consuming for larger numbers, so it's more efficient for smaller pairs.

Step 2: Successive Subtractions

This method involves subtracting the smaller number from the larger until both numbers are equal.

1. Identify the two numbers:

   • For instance, take 48 and 18.

2. Subtract the smaller from the larger:

   • 48 - 18 = 30
   • 30 - 18 = 12
   • 18 - 12 = 6
   • 12 - 6 = 6
   • 6 - 6 = 0

3. Result:

   • When both numbers become equal, that number is the PGCD. Here, the PGCD is 6.

Common Pitfall

This method can lead to errors if you forget to subtract correctly, so it's essential to keep track of your calculations.

Step 3: Euclidean Algorithm

This method is more efficient for larger numbers and is based on the principle that the PGCD of two numbers also divides their difference.

1. Start with two numbers:

   • For example, 48 and 18.

2. Apply the Euclidean algorithm:

   • Compute the remainder of the larger number divided by the smaller.
   • 48 mod 18 = 12
   • Now, replace the larger number with the smaller and the smaller with the remainder:
     • New pair: 18 and 12
     • 18 mod 12 = 6
     • New pair: 12 and 6
     • 12 mod 6 = 0

3. Result:

   • When the remainder is 0, the last non-zero remainder is the PGCD. Here, the PGCD is 6.

Practical Tip

This method is highly efficient and works well with large numbers, making it a preferred choice for many mathematicians.

Step 4: Prime Factorization

This method involves breaking each number down into its prime factors.

1. Find the prime factors of each number:

   • For 12: 2 × 2 × 3
   • For 18: 2 × 3 × 3

2. List the common prime factors:

   • Common factors are 2 and 3.

3. Multiply the lowest powers of common prime factors:

   • 2^1 × 3^1 = 6

4. Result:

   • The PGCD is 6.

Real-World Application

This method is particularly useful in algebra and number theory as it helps in understanding the structure of numbers.

Conclusion

You have learned four distinct methods to find the PGCD: listing divisors, successive subtractions, the Euclidean algorithm, and prime factorization. Each method has its advantages depending on the numbers involved and the context in which you are working. For efficiency, the Euclidean algorithm is often recommended for larger numbers. Practice these methods to find which one you prefer and become more confident in your mathematical abilities.