gcd and the Fundamental Theorem of Arithmetic

According to the Fundamental Theorem of Arithmetic, every integer N has a unique representation in the form

where all all p_i's are prime and n_i's are positive. Relaxing the latter we may write

where the exponents n_pi are non-negative. If any is zero, p_i does not actually divide N. The reverse is also true. Therefore, p_i divides N iff n_pi> 0.

(2) is more convenient if we want to compare representations of two integers. Let

As before, p_i|M iff m_pi> 0. If p_i is a common factor for N and M then the largest power of p_i that divides both is given by min(n_pi, m_pi). Since gcd(N,M) is the largest common divisor of N and M and is divisible by any other common divisor of the two,

From (2) and (3) we also obtain a representation for the Least Common Multiple lcm(N,M):

The fact that gcd(N,M) * lcm(N,M) = N * M is thus equivalent to n + m = min(n,m) + max(n,m).

References

1. R.Graham, D.Knuth, O.Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.

• Modular Arithmetic
  • Differences and Similarities
  • Solutions to some problems
• Chinese Remainder Theorem
• Euclid's Algorithm
  • Euclid's Game
  • Binary Euclid's Algorithm
  • gcd and the Fundamental Theorem of Arithmetic
  • Extension of Euclid's Algorithm
  • Stern-Brocot Tree
    • Fine features
    • Binary Encoding
    • Binary Encoding, a Second Interpretation
    • Continued Fractions on the Stern-Brocot Tree
    • Fractions on a Binary Tree
  • Farey series
    • Farey series, a story
• Pick's Theorem
  • Pick's Theorem, A Proof
  • Farey Series
  • Pick's Theorem Applies to the Farey Series
  • Stern-Brocot Tree
• Fermat's Little Theorem
• Wilson's Theorem
• Euler's Function
• Divisibility Criteria
  • Further examles of divisibility criteria
• Examples
• Equivalence relations
• A real life story

Copyright © 1996-2008 Alexander Bogomolny