2026-10-15

Exercises for Chapter 5

Source: Richard Hammack, The Book of Proof, 3rd ed., “Exercises for Chapter 5” (p. 136).

A. Prove the following statements with contrapositive proof. (In each case, think about how a direct proof would work. In most cases contrapositive is easier.)

• 5. Suppose \(x\in\mathbb{R}\). If \(x^2+5x<0\) then \(x<0\).

• 9. Suppose \(n\in\mathbb{Z}\). If \(3\nmid n^2\), then \(3\nmid n\).

• 11. Suppose \(x,y\in\mathbb{Z}\). If \(x^2(y+3)\) is even, then \(x\) is even or \(y\) is odd.

B. Prove the following statements using either direct or contrapositive proof.

• 20. If \(a\in\mathbb{Z}\) and \(a\equiv 1 \pmod{5}\), then \(a^2\equiv 1 \pmod{5}\).

• 25. Let \(n\in\mathbb{N}\). If \(2^n-1\) is prime, then \(n\) is prime.

• 29. If integers \(a\) and \(b\) are not both zero, then \(\gcd(a,b)=\gcd(a-b,b)\).

• 32. If \(a\equiv b \pmod{n}\), then \(a\) and \(b\) have the same remainder when divided by \(n\).