gcd and the Fundamental Theorem of Arithmetic
According to the Fundamental Theorem of Arithmetic, every integer N has a unique representation in the form
|(1)||N = p1n1p2n2...pmnm ,|
where all all pi's are prime and ni's are positive. Relaxing the latter we may write
|(2)||N = 2n23n3...pinpi...,|
where the exponents npi are non-negative. If any is zero, pi does not actually divide N. The reverse is also true. Therefore, pi divides N iff npi> 0.
(2) is more convenient if we want to compare representations of two integers. Let
|(3)||M = 2m23m3...pimpi...,|
As before, pi|M iff mpi> 0. If pi is a common factor for N and M then the largest power of pi that divides both is given by min(npi, mpi). Since gcd(N,M) is the largest common divisor of N and M and is divisible by any other common divisor of the two,
|(4)||gcd(N,M) = 2min(n2, m2)3min(n3, m3)...pimin(npi, mpi)...|
Two numbers N and M are coprime iff min(npi, mpi) = 0 for all i. Since all the exponents are non-negative, the latter is equivalent to
|(5)||npimpi = 0 for all i.|
This is handy in proving that if gcd(N,M) = 1 and gcd(N,K) = 1 then gcd(N,MK) = 1. Indeed, the combination of npimpi = 0 and npikpi = 0 is equivalent to a single assertion that npi(mpi+kpi) = 0 for non-negative mpi and kpi.
From (2) and (3) we also obtain a representation for the Least Common Multiple lcm(N,M):
|(6)||lcm(N,M) = 2max(n2, m2)3max(n3, m3)...pimax(npi, mpi)...|
The fact that gcd(N,M) * lcm(N,M) = N * M is thus equivalent to n + m = min(n,m) + max(n,m).
- R.Graham, D.Knuth, O.Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
Copyright © 1996-2018 Alexander Bogomolny