Properties of GCD and LCM
For two (positive) integers N and M, the properties of their greatest common divisor gcd and the least common multiple lcm come in pairs; the phenomenon is partly explained by the formula
(Above, as below, the symbols M, N, P, Q stand for positive integers.)
P|N and P|M ⇒ P|gcd(N, M),
N|P and M|P ⇒ lcm(N, M)|P.
In plain English: every common divisor of N and M, also divides their greatest common divisor; and every common multiple of two integers is divisible by their least common multiple.
N = gcd(N, M) ⇔ N|M
M = lcm(N, M) ⇔ N|M.
In plain English: N divides M if and only if N is the greatest common divisor of the pair; in turn, this is only true if M is the least common multiple of the two.
gcd(P·N, P·M) = P·gcd(N, M)
lcm(P·N, P·M) = P·lcm(N, M).
In plain English: an extra common factor of N and M is a factor of both gcd(N, M) and lcm(N, M). This is easily observed with the interactive tool for computing gcd and lcm.
Proof
It is enough to establish this property for prime P. Suppose prime p appears in the factorization of N with the exponent, a ≥ 0, and in M with the exponent b ≥ 0. Then the exponents of p in pN and pM are, respectively,
If gcd(N_{1}, N_{2}) = 1, then
gcd(N_{1}·N_{2}, M) = gcd(N_{1}, M)·gcd(N_{2}, M)
lcm(N_{1}·N_{2}, M) = lcm(N_{1}, M)·lcm(N_{2}, M)/M.
In plain English: for relatively prime N_{1} and N_{2},
It is important to observe that, for distinct primes p and q, gcd(p^{a}, q^{b}) = 1 while
gcd(N, M) = gcd(p^{a}q^{b}, M) = gcd(p^{a}, M)·gcd(q^{b}, M), lcm(N, M) = lcm(p^{a}q^{b}, M) = lcm(p^{a}, M)·lcm(q^{b}, M), |
which shows that much can be done by taking the prime number decomposition and looking at one prime factor at a time.
gcd(gcd(N, M), P) = gcd(N, gcd(M, P))
lcm(lcm(N, M), P) = lcm(N, lcm(M, P)).
This property can be described as the associativity of both gcd and lcm. Associativity shows that the gcd and lcm for more than two numbers could be defined unambiguously in several ways. For example
gcd(M, N, P) = gcd(gcd(M, N),P) = gcd(M, gcd(N, P))
lcm(M, N, P) = lcm(lcm(M, N),P) = lcm(M, lcm(N, P)).
With this definition we state and prove lemma that was instrumental in establishing the generalized Chinese Remainder Theorem.
Lemma
For integers N_{1}, ..., N_{k}, k ≥ 2,
lcm(gcd(N_{1}, M), gcd(N_{2}, M), ..., gcd(N_{k}, M)) = gcd(lcm(N_{1}, ..., N_{k}), M)
gcd(lcm(N_{1}, M), lcm(N_{2}, M), ..., lcm(N_{k}, M)) = lcm(gcd(N_{1}, ..., N_{k}), M).
As with the union and intersection of the sets, gcd and lcm satisfy two distributive laws.
Proof
We prove the first identity. Let p be a prime divisor of lcm(gcd(N_{1}, M), gcd(N_{2}, M), ..., gcd(N_{k}, M)) and α the largest exponent such that
Conversely, suppose, for a prime p, p^{α} divides gcd(lcm(N_{1}, ..., N_{k}), M). It then divides both lcm(N_{1}, ..., N_{k}) and M. Being a power of a prime, it divides at least one of N_{i}. Let it be N_{1}. Then p^{α} is a common multiple of N_{1} and M and, therefore, divides
Exercise
(The First Moscow Mathematical Olympiad, 1935)
lcm(M, N, P) · gcd(M, N) · gcd(N, P) · gcd(P, M) = NMP · gcd(N, M, P).
|Contact| |Front page| |Contents| |Arithmetic|
Copyright © 1996-2018 Alexander Bogomolny64480309 |