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).

References

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

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

71492778