ยง1.3 Exercises

Exercises 1.3.A

Exercise 1.3.1

Express each number as a product of primes:

  • (a) 5040
  • (b) -2345
  • (c) 45,670
  • (d) 2,042,040

Exercise 1.3.2

(a) Verify that \(2^5 - 1\) and \(2^7 - 1\) are prime.

(b) Show that \(2^{11} - 1\) is not prime.

Exercise 1.3.3

Which of the following numbers are prime:

  • (a) 701
  • (b) 1009
  • (c) 1949
  • (d) 1951

Exercise 1.3.4

Primes \(p\) and \(q\) are said to be twin primes if \(q = p + 2\). For example, 3 and 5 are twin primes; so are 11 and 13. Find all pairs of positive twin primes less than 200.

Exercise 1.3.5

(a) List all the positive integer divisors of \(3^5 \cdot 5^4\), where \(r, s, t \in \mathbb{Z}\) and \(s, t > 0\).

(b) If \(r\), \(s\), \(t \in \mathbb{Z}\) are positive, how many positive divisors does \(2^3 \cdot 3^5 \cdot 5^4\) have?

Exercise 1.3.6

If \(p > 5\) is prime and \(p\) is divided by 10, show that the remainder is 1, 3, 7, or 9.

Exercise 1.3.7

If \(a\), \(b\), \(c\) are integers and \(p\) is a prime that divides both \(a\) and \(a + bc\), prove that \(p \mid b\) or \(p \mid c\).

Exercise 1.3.8

(a) Verify that \(x - 1\) is a factor of \(x^n - 1\).

(b) If \(n\) is a positive integer, prove that the prime factorization of \(2^{2n} \cdot 3^n - 1\) includes 11 as one of the prime factors.

Hint: \(2^{2n} \cdot 3^n = (2^n \cdot 3^{n/2})^2\).

Exercise 1.3.9

Let \(p\) be an integer other than 0, \(\pm 1\). Prove that \(p\) is prime if and only if it has this property: Whenever \(r\) and \(s\) are integers such that \(p = rs\), then \(r = \pm 1\) or \(s = \pm 1\).

Exercise 1.3.10

Let \(p\) be an integer other than 0, \(\pm 1\). Prove that \(p\) is prime if and only if for each \(a \in \mathbb{Z}\) either \((a, p) = 1\) or \(p \mid a\).

Exercise 1.3.11

If \(a\), \(b\), \(c\), and \(d\) are integers and \(p\) is a prime factor of both \(a - b\) and \(c - d\), prove that \(p\) is a prime factor of \((a + c) - (b + d)\).

Exercise 1.3.12

Prove Corollary 1.9.

Exercise 1.3.13

Prove that every integer \(n > 1\) can be written in the form \(p_1^{r_1} p_2^{r_2} \cdots p_k^{r_k}\), with the \(p_i\) distinct positive primes and every \(r_i > 0\).

Exercise 1.3.14

Let \(p\) be an integer other than 0, \(\pm 1\) with this property: Whenever \(b\) and \(c\) are integers such that \(p \mid bc\), then \(p \mid b\) or \(p \mid c\). Prove that \(p\) is prime.

Hint: If \(d\) is a divisor of \(p\), say \(p = dt\), then \(p \mid d\) or \(p \mid t\). Show that this implies \(d = \pm p\) or \(d = \pm 1\).

Exercise 1.3.15

If \(p\) is prime and \(p \mid a^r\), is it true that \(p^r \mid a^r\)? Justify your answer.

Hint: Corollary 1.6.

Exercise 1.3.16

Prove that \((a, b) = 1\) if and only if there is no prime \(p\) such that \(p \mid a\) and \(p \mid b\).

Exercise 1.3.17

If \(p\) is prime and \((a, b) = p\), then \((a^2, b^2) = p^2\)?

Exercise 1.3.18

Prove or disprove each of the following statements:

  • (a) If \(p\) is prime and \(p \mid (a^2 + b^2)\) and \(p \mid (c^2 + d^2)\), then \(p \mid (a^2 - c^2)\).
  • (b) If \(p\) is prime and \(p \mid (a^2 + b^2)\) and \(p \mid (c^2 + d^2)\), then \(p \mid (a^2 + c^2)\).
  • (c) If \(p\) is prime and \(p \mid a\) and \(p \mid (a^2 + b^2)\), then \(p \mid b\).

Exercises 1.3.B

Exercise 1.3.19

Suppose that \(a = p_1^{r_1} p_2^{r_2} \cdots p_k^{r_k}\) and \(b = p_1^{s_1} p_2^{s_2} \cdots p_k^{s_k}\), where \(p_1, p_2, \dots, p_k\) are distinct positive primes and each \(r_i\), \(s_i \geq 0\). Prove that \((a \mid b)\) if and only if \(r_i \leq s_i\) for every \(i\).

Exercise 1.3.20

If \(a = p_1^{r_1} p_2^{r_2} \cdots p_k^{r_k}\) and \(b = p_1^{s_1} p_2^{s_2} \cdots p_k^{s_k}\), where \(p_1, p_2, \dots, p_k\) are distinct positive primes and each \(r_i\), \(s_i \geq 0\), then prove that:

  • (a) \((a, b) = p_1^{\min(r_1, s_1)} p_2^{\min(r_2, s_2)} \cdots p_k^{\min(r_k, s_k)}\), where for each \(i\), \(n_i = \min(r_i, s_i)\).
  • (b) \([a, b] = p_1^{\max(r_1, s_1)} p_2^{\max(r_2, s_2)} \cdots p_k^{\max(r_k, s_k)}\).

Hint: See Exercise 31 in Section 1.2.

Exercise 1.3.21

If \(c^2 = ab\) and \((a, b) = 1\), prove that \(a\) and \(b\) are perfect squares.

Exercise 1.3.22

Let \(n = p_1^{r_1} p_2^{r_2} \cdots p_k^{r_k}\), where \(p_1, p_2, \dots, p_k\) are distinct primes and each \(r_i \geq 0\). Prove that \(n\) is a perfect square if and only if each \(r_i\) is even.

Exercise 1.3.23

Prove that \(a \mid b\) if and only if \(a^2 \mid b^2\).

Hint: See Exercise 19.

Exercise 1.3.24

Prove that \( a \mid b \) if and only if \( a^n \mid b^n \).

Exercise 1.3.25

Let \( p \) be prime and \( 1 \leq k < p \). Prove that \( p \) divides the binomial coefficient:

\[ \binom{p}{k} = \frac{p!}{k!(p-k)!} \]

Exercise 1.3.26

If \( n \) is a positive integer, prove that there exist \( n \) consecutive composite integers. Hint: Consider \( (n + 1)! + 2, (n + 1)! + 3, (n + 1)! + 4, \ldots \)

Exercise 1.3.27

If \( p > 3 \) is prime, prove that \( p^2 + 2 \) is composite. Hint: Consider the possible remainders when \( p \) is divided by 3.

Exercise 1.3.28

Prove or disprove: The sums

\[ 1 + 2 + 4, \quad 1 + 2 + 4 + 8, \quad 1 + 2 + 4 + 8 + 16, \ldots \]

are alternately prime and composite.

Exercise 1.3.29

If \( n \in \mathbb{Z} \) and \( n \neq 0 \), prove that \( n \) can be written uniquely in the form \( n = 2^k m \), where \( k \geq 0 \) and \( m \) is odd.

Exercise 1.3.30

(a) Prove that there are no nonzero integers \( a, b \) such that \( a^2 = 2b^2 \). Hint: Use the Fundamental Theorem of Arithmetic.

(b) Prove that \( \sqrt{2} \) is irrational. Hint: Use proof by contradiction (Appendix A). Assume that \( \sqrt{2} = \frac{a}{b} \) (with \( a, b \in \mathbb{Z} \)) and use part (a) to reach a contradiction.

Exercise 1.3.31

If \( p \) is a positive prime, prove that \( \sqrt{p} \) is irrational. See Exercise 30.

Exercise 1.3.32

(Euclid) Prove that there are infinitely many primes. Hint: Use proof by contradiction (Appendix A). Assume there are only finitely many primes \( p_1, p_2, \ldots, p_k \), and reach a contradiction by showing that the number \( p_1 p_2 \cdots p_k + 1 \) is not divisible by any of \( p_1, p_2, \ldots, p_k \).

Exercise 1.3.33

Let \( p > 1 \). If \( 2^p - 1 \) is prime, prove that \( p \) is prime. Hint: Prove the contrapositive: If \( p \) is composite, so is \( 2^p - 1 \).
Note: The converse is false by Exercise 2(b).

Exercise 1.3.34

Prove or disprove: If \( n \) is an integer and \( n > 2 \), then there exists a prime \( p \) such that \( n < p < n! \).

Exercises 1.3.C

Exercise 1.3.35

(a) Let \( a \) be a positive integer. If \( \sqrt{a} \) is rational, prove that \( \sqrt{a} \) is an integer.

(b) Let \( r \) be a rational number and \( a \) an integer such that \( r^n = a \). Prove that \( r \) is an integer. Part (a) is the case when \( n = 2 \).

Exercise 1.3.36

Let \( p, q \) be primes with \( p \geq 5 \), \( q \geq 5 \). Prove that \( 24 \mid (p^2 - q^2) \).