6.3 Factorization into Primes 91So assume that there exists an integer with two different factorizations;
call such an integer a “criminal.” There may be many criminals, but we
consider thesmallestone. Being a criminal, this has at least two different
factorizations:
n=p 1 ·p 2 ···pm=q 1 ·q 2 ···qk.
We may assume thatp 1 is the smallest prime occurring in these factoriza-
tions. (Indeed, if necessary, we can interchange the left-hand side and the
right-hand side so that the smallest prime in any of the two factorizations
occurs on the left-hand side; and then change the order of the factors on
the left-hand side so that the smallest factor comes first. In the usual slang
of mathematics, we say that we may assume thatp 1 is the smallest prime
without loss of generality.) We are going to produce a smaller criminal; this
will be a contradiction, since we assumed thatnwas the smallest one.
The numberp 1 cannot occur among the factorsqi; otherwise, we can
divide both sides byp 1 and get a smaller criminal.
Divide eachqibyp 1 with residue:qi=p 1 ai+ri, where 0≤ri<p 1 .We
know thatri = 0, since a prime cannot be a divisor of another prime.
Letn′ =r 1 r 2 ···rk. We show thatn′is a smaller criminal. Trivially
ri<p 1 <qi, and son′ =r 1 r 2 ···rk<q 1 q 2 ···qk =n. We show that
n′, too, has two different factorizations into primes. One of these can be
obtained from the definitionn′=r 1 r 2 ···rk. Here the factors may not be
primes, but we can break them down into products of primes, so that we
end up with a decomposition ofn′.
To get another decomposition, we observe thatp 1 |n′. Indeed, we can
write the definition ofn′in the form
n′=(q 1 −a 1 p 1 )(q 2 −a 2 p 1 )···(qk−akp 1 ),and if we expand, then every term will be divisible byp 1. (One of the terms
isq 1 q 2 ···qk, which is equal tonand so divisible byp 1. All the other terms
containp 1 as a factor.) Now we dividen′byp 1 and then continue to factor
n′/p 1 , to get a factorization ofn′.
But are these two factorizations different? Yes! The primep 1 occurs in
the second, but it cannot occur in the first, where every prime factor is
smaller thanp 1.
Thus we have found a smaller criminal. Sincenwas supposed to be
the smallest among all criminals, this is a contradiction. The only way
to resolve this contradiction is to conclude that there are no criminals;
our “indirect assumption” was false, and no integer can have two different
prime factorizations.
6.3.1Read carefully the following “minimal criminal” argument:Assertion.Every negative integer is odd.