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_{1}^{n1}p_{2}^{n2}...p_{m}^{nm} , |
where all all p_{i}'s are prime and n_{i}'s are positive. Relaxing the latter we may write
(2) | N = 2^{n2}3^{n3}...p_{i}^{npi}..., |
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
(3) | M = 2^{m2}3^{m3}...p_{i}^{mpi}..., |
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,
(4) | gcd(N,M) = 2^{min(n2, m2)}3^{min(n3, m3)}...p_{i}^{min(npi, mpi)}... |
Two numbers N and M are coprime iff min(n_{pi}, m_{pi}) = 0 for all i. Since all the exponents are non-negative, the latter is equivalent to
(5) | n_{pi}m_{pi} = 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_{pi}m_{pi} = 0 and n_{pi}k_{pi} = 0 is equivalent to a single assertion that n_{pi}(m_{pi}+k_{pi}) = 0 for non-negative m_{pi} and k_{pi}.
From (2) and (3) we also obtain a representation for the Least Common Multiple lcm(N,M):
(6) | lcm(N,M) = 2^{max(n2, m2)}3^{max(n3, m3)}...p_{i}^{max(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
- R.Graham, D.Knuth, O.Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
- Modular Arithmetic
- Chinese Remainder Theorem
- Euclid's Algorithm
- Pick's Theorem
- Fermat's Little Theorem
- Wilson's Theorem
- Euler's Function
- Divisibility Criteria
- Examples
- Equivalence relations
- A real life story
|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
71625235