SECTION 2.1 Elementary Number Theory 77
a=pe 11 pe 22 ···perr, b=pf 11 pf 22 ···pfrrbe the prime factorization of a and b where some of the exponents
might be 0. For eachi = 1, 2 , ...,r, let mi = min{ei, fi} and let
Mi= max{ei, fi}. The following should be clear:
gcd(a,b) =pm 11 pm 22 ···pmrr, lcm(a,b) =pM 11 pM 22 ···pMr r.From the above we see that we have two rather different methods
of finding the greatest common divisor and least common multiple of
two positive integers. The first is the Euclidean algorithm, which we
encountered on page 59, and the second is based on the Fundamental
Theorem of Arithmetic above. On the surface it would appear that the
latter method is much easier than the former method—and for small
numbers this is indeed the case. However, once the numbers get large
then the problem of factoring into primes becomes considerably more
difficult than the straightforward Euclidean algorithm.
Exercises
- Find the prime factorizations of the numbers
(a) 12500
(b) 12345
(c) 24227- Find the factorization of the numbersp^3 (p−1)^2 (p+ 1)(p^2 +p+ 1),
wherep= 2, 3 , 5 , 7. - Compute the gcd and lcm of the following pairs of numbers
(a) 2090 and 1911
(b) 20406 and 11999
(c) 2^10 + 1 and 2^10 −1.- Show that ifpis a prime, thenp+1 andp^2 +p+1 must be relatively
prime. Find integerssandtsuch thats(p+ 1) +t(p^2 +p+ 1) = 1.