幂次最大公约数相等性证明：如何证GCD(a^d,b^d)=GCD(a,b)^d

Hey there, let's walk through proving that for any integer ( d \geq 1 ), ( \gcd(a^d, b^d) = \gcd(a, b)^d ). This is a staple result in number theory, and we can use two straightforward approaches to make it click.

Approach 1: Prime Factorization (The Fundamental Theorem of Arithmetic) #

This is the most direct way—we'll use the fact that every integer has a unique prime factorization.

First, let's write the prime factorizations of ( a ) and ( b ):

• ( a = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k} )
• ( b = p_1^{f_1} p_2^{f_2} \dots p_k^{f_k} )

(We include all primes from both factorizations, using 0 as the exponent if a prime doesn't appear in one of the numbers.)

• Step 1: Calculate ( \gcd(a, b)^d )
  By definition, the gcd of two numbers takes the minimum exponent of each prime present in their factorizations. So:
  [
  \gcd(a, b) = p_1^{\min(e_1, f_1)} p_2^{\min(e_2, f_2)} \dots p_k^{\min(e_k, f_k)}
  ]
  When we raise this to the ( d )-th power, each exponent gets multiplied by ( d ):
  [
  \gcd(a, b)^d = p_1^{d \cdot \min(e_1, f_1)} p_2^{d \cdot \min(e_2, f_2)} \dots p_k^{d \cdot \min(e_k, f_k)}
  ]

• Step 2: Calculate ( \gcd(a^d, b^d) )
  First, let's find the factorizations of ( a^d ) and ( b^d ):

  • ( a^d = p_1^{d e_1} p_2^{d e_2} \dots p_k^{d e_k} )
  • ( b^d = p_1^{d f_1} p_2^{d f_2} \dots p_k^{d f_k} )

  Again, we take the minimum exponent for each prime to get the gcd:
  [
  \gcd(a^d, b^d) = p_1^{\min(d e_1, d f_1)} p_2^{\min(d e_2, d f_2)} \dots p_k^{\min(d e_k, d f_k)}
  ]

• Step 3: Show the exponents are equal
  The key here is recognizing that for any non-negative integers ( e, f ) and positive integer ( d ), ( \min(d e, d f) = d \cdot \min(e, f) ). Why? Because multiplying by a positive integer preserves order:

  • If ( e \leq f ), then ( d e \leq d f ), so ( \min(d e, d f) = d e = d \cdot \min(e, f) )
  • If ( f < e ), then ( d f < d e ), so ( \min(d e, d f) = d f = d \cdot \min(e, f) )

  Since every prime's exponent matches exactly between ( \gcd(a^d, b^d) ) and ( \gcd(a, b)^d ), the two numbers are identical.

Approach 2: Coprime Reduction #

If prime factorization feels too formal, this method uses simpler coprimality properties.

• Step 1: Reduce to coprime integers
  Let ( g = \gcd(a, b) ). By definition, we can write:

  • ( a = g \cdot a' )
  • ( b = g \cdot b' )
    where ( \gcd(a', b') = 1 ) (we've factored out all common divisors).

• Step 2: Look at ( d )-th powers
  Now let's compute the ( d )-th powers of ( a ) and ( b ):

  • ( a^d = g^d \cdot (a')^d )
  • ( b^d = g^d \cdot (b')^d )

• Step 3: Use coprimality of powers
  A key side result: if two numbers are coprime, their ( d )-th powers are also coprime. So ( \gcd((a')^d, (b')^d) = 1 ).

  When we take the gcd of ( a^d ) and ( b^d ), we can factor out the ( g^d ) term, and what's left is the gcd of two coprime numbers (which is 1):
  [
  \gcd(a^d, b^d) = g^d \cdot \gcd((a')^d, (b')^d) = g^d \cdot 1 = \gcd(a, b)^d
  ]

Either approach works perfectly—pick the one that resonates with your understanding of number theory!

内容的提问来源于stack exchange，提问作者m ath