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 = p₁^n₁p₂^n₂...p_m^n_m ,

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

(2)	N = 2^{^n₂}3^{^n₃}...p_i^{^n_{p_i}}...,

where the exponents n_{p_i} 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_{p_i}> 0.

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

(3)	M = 2^{^m₂}3^{^m₃}...p_i^{^m_{p_i}}...,

As before, p_i|M iff m_{p_i}> 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_{p_i}, m_{p_i}). 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) = 2^{^{min(n₂, m₂)}}3^{^{min(n₃, m₃)}}...p_i^{^{min(n_{p_i}, m_{p_i})}}...

Two numbers N and M are coprime iff min(n_{p_i}, m_{p_i}) = 0 for all i. Since all the exponents are non-negative, the latter is equivalent to

(5)	n_{p_i}m_{p_i} = 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 n_{p_i}m_{p_i} = 0 and n_{p_i}k_{p_i} = 0 is equivalent to a single assertion that n_{p_i}(m_{p_i}+k_{p_i}) = 0 for non-negative m_{p_i} and k_{p_i}.

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

(6)	lcm(N,M) = 2^{^{max(n₂, m₂)}}3^{^{max(n₃, m₃)}}...p_i^{^{max(n_{p_i}, m_{p_i})}}...

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

References

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

72111974