How to Prove Two Numbers are Relatively Prime?

To prove that two numbers are relatively prime (also known as coprime), you need to demonstrate that their greatest common divisor (GCD), also known as highest common factor (HCF), is 1.

Here's a breakdown of the methods:

Methods to Prove Relative Primality

Calculate the Greatest Common Divisor (GCD/HCF):
- The most straightforward method is to find the GCD of the two numbers.
- If the GCD is 1, then the numbers are relatively prime.
- If the GCD is greater than 1, then the numbers are not relatively prime.
Algorithms for finding GCD:
- Euclidean Algorithm: This is the most efficient method. It involves repeatedly applying the division algorithm until you get a remainder of 0. The last non-zero remainder is the GCD.
  - Example: Prove 15 and 28 are relatively prime using the Euclidean Algorithm.
    1. 28 = 15 * 1 + 13
    2. 15 = 13 * 1 + 2
    3. 13 = 2 * 6 + 1
    4. 2 = 1 * 2 + 0
    Since the last non-zero remainder is 1, GCD(15, 28) = 1. Therefore, 15 and 28 are relatively prime.
- Prime Factorization: Find the prime factorization of each number. If they share no common prime factors, they are relatively prime.
  - Example: Prove 8 and 15 are relatively prime using prime factorization.
    - 8 = 2 x 2 x 2 = 2³
    - 15 = 3 x 5
    Since 8 and 15 share no common prime factors, they are relatively prime.
Check for Common Divisors (Less Efficient):
- List the divisors of each number.
- If the only divisor they share is 1, then they are relatively prime. This method is less efficient for larger numbers.
- Example: Prove 8 and 9 are relatively prime by checking for common divisors.
  - Divisors of 8: 1, 2, 4, 8
  - Divisors of 9: 1, 3, 9
  The only common divisor is 1; therefore, 8 and 9 are relatively prime.

Key Points

Two prime numbers are always relatively prime (unless they are the same prime number, in which case their GCD is that prime number).
Any two consecutive integers are always relatively prime.

In summary, proving that two numbers are relatively prime involves demonstrating that their greatest common divisor is 1, commonly achieved through the Euclidean algorithm or by verifying that they share no common prime factors.