Number Theory 25

Try proving implications directly. When proving a statement of the form, “if p, then

q,” try starting your argument by writing, “Assume p,” and then argue for q. This

method is called a direct proof of the implication.

Try proving implications via the contrapositive. When proving a statement of the

form “if p, then q,” consider the contrapositive, “if not q, then not p.” This is logi-

cally equivalent to the original statement and sometimes admits a smoother argument,

particularly when q has a negative form, in which case “not q” becomes a positive

assumption. Write, “To prove the contrapositive, assume not q.” And then argue for

not p.

Exercises

3.1 Prove that a positive integer is prime if and only if it has exactly two positive integer divisors.

3.2 Show that a positive integer p > 1 is prime if and only if, whenever p divides a product ab of

integers, then either p divides a or p divides b.

3.3 Prove a stronger version of B

´

ezout’s lemma, namely, that for any two integers a and b, the

smallest positive number d expressible as an integer linear combination of a and b is precisely

the greatest common divisor of a and b.

3.4 Read Timothy Gower’s blog post, “Why isn’t the fundamental theorem of arithmetic obvi-

ous?” (https://gowers.wordpress.com/2011/11/13/w) and his follow-up post, “Proving the

fundamental theorem of arithmetic” (https://gowers.wordpress.com/2011/11/18/p). Write a

summary.

3.5 Show that if we count the number 1 as prime, then the uniqueness claim of the fundamental

theorem of arithmetic would be false. (And this is one good reason not to count 1 as amongst

the prime numbers.)

3.6 Prove that if one prime divides another, then they are equal. (This was used in the proof of

theorem 9.)

3.7 Mathematician Evelyn Lamb fondly notes of any large prime number presented to her that

it is “one away from a multiple of 3!” And part of her point is that this is true whether you

interpret the exclamation point as an exclamation or instead as a mathematical sign for the

factorial. Prove that every prime larger than 3 is one away from a multiple of 3!. [Hint:

Consider the remainder of the number modulo 6.]

3.8 Prove that if a, b, and c are positive integers and the product abc is a multiple of 6, then one

of the numbers ab, ac,orbc is a multiple of 6.