92 6. Integers, Divisors, and Primes
Proof.Suppose, by way of contradiction, that there are negative
integers that are even. Call these integers criminals, and letnbe a
minimal criminal. Consider the number 2n. This is smaller thann
(recall thatnis negative!), so it is a smaller criminal. But we assumed
thatnwas the smallest criminal, so this is a contradiction.
This assertion is obviously wrong. Where is the error in the proof?As an application of Theorem 6.3.1, we prove a fact that was known to the
Pythagoreans (students of the great Greek mathematician and philosopher
Pythagoras) in the sixth centuryB.C.
Theorem 6.3.2The number
√
2 is irrational.(A real number isirrationalif it cannot be written as the ratio of two
integers. For the Pythagoreans, the question arose from geometry: They
wanted to know whether the diagonal of a square is “commeasurable” with
its side, that is, whether there is any segment that is contained in both
of them an integer number of times. The above theorem answered this
question in the negative, causing a substantial turmoil in their ranks.)
Proof. We give an indirect proof again: We suppose that
√
2 is rational,
and derive a contradiction. What the indirect assumption means is that
√
2
can be written as the quotient of two positive integers:
√
2=a/b. Squaring
both sides and rearranging, we get 2b^2 =a^2.
Now consider the prime factorization of both sides, and in particular, the
prime number 2 on both sides. Suppose that 2 occursmtimes in the prime
factorization ofaandntimes in the prime factorization ofb. Then it occurs
2 mtimes in the prime factorization ofa^2. On the other hand, it occurs 2n
times in the prime factorization ofb^2 , and thus it occurs 2n+ 1 times in
the prime factorization of 2b^2. Since 2b^2 =a^2 , and the prime factorization
is unique, we must have 2n+1=2m. But this is impossible, since 2n+1 is
odd but 2mis even. This contradiction proves that
√
2 must be irrational.
6.3.2Are there any even primes?6.3.3 (a) Prove that ifpis a prime,aandbare integers, andp|ab, then
eitherp|aorp|b(or both).
(b) Suppose thataandbare integers anda|b. Also suppose thatpis a prime
andp|bbutpa. Prove thatpis a divisor of the ratiob/a.6.3.4Prove that the prime factorization of a numberncontains at most log 2 n
factors.
6.3.5Let p be a prime and 1 ≤ a ≤ p−1. Consider the numbers
a, 2 a, 3 a,...,(p−1)a. Divide each of them byp, to get residuesr 1 ,r 2 ,...,rp− 1.
Prove that every integer from 1 top−1 occursexactly onceamong these residues.
[Hint: First prove that no residue can occur twice.]