Discrete Mathematics

246 DISCRETE

MATHEMATICS---------------------------

form

n'=(q,-a,p,)(q2

-azp

,) ...

(qk

-akp,),

and

if

we expand, then every term will be divisible by p

1

•

Now we divide

n'

by p

1

and then continue to factor

n'lp

1

,

to get a factorization

of

n'

.

But are these two factorizations different? Yes! The prime p

1

occurs in the second, but it cannot occur

in the first, where every prime factor is smaller than

p

1

•

Thus, we have found a smaller criminal. Since n was supposed to be the smallest among all criminals,

this is a contradiction. The only way to resolve this contradiction is to conclude that our

"indirect assumption"

was false and no integer can ...