exercises-integers.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section2.3Exercises

¶

1

Prove that

$$\begin{equation*} 1^2 + 2^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6} \end{equation*}$$

for $n \in {\mathbb N}\text{.}$

Hint

The base case, $S(1): [1(1 + 1)(2(1) + 1)]/6 = 1 = 1^2$ is true. Assume that $S(k): 1^2 + 2^2 + \cdots + k^2 = [k(k + 1)(2k + 1)]/6$ is true. Then

$$\begin{align*} 1^2 + 2^2 + \cdots + k^2 + (k + 1)^2 & = [k(k + 1)(2k + 1)]/6 + (k + 1)^2\\ & = [(k + 1)((k + 1) + 1)(2(k + 1) + 1)]/6, \end{align*}$$

and so $S(k + 1)$ is true. Thus, $S(n)$ is true for all positive integers $n\text{.}$

2

Prove that

$$\begin{equation*} 1^3 + 2^3 + \cdots + n^3 = \frac{n^2(n + 1)^2}{4} \end{equation*}$$

for $n \in {\mathbb N}\text{.}$

3

Prove that $n! \gt 2^n$ for $n \geq 4\text{.}$

Hint

The base case, $S(4): 4! = 24 \gt 16 =2^4$ is true. Assume $S(k): k! \gt 2^k$ is true. Then $(k + 1)! = k! (k + 1) \gt 2^k \cdot 2 = 2^{k + 1}\text{,}$ so $S(k + 1)$ is true. Thus, $S(n)$ is true for all positive integers $n\text{.}$

4

Prove that

$$\begin{equation*} x + 4x + 7x + \cdots + (3n - 2)x = \frac{n(3n - 1)x}{2} \end{equation*}$$

for $n \in {\mathbb N}\text{.}$

5

Prove that $10^{n + 1} + 10^n + 1$ is divisible by 3 for $n \in {\mathbb N}\text{.}$

6

Prove that $4 \cdot 10^{2n} + 9 \cdot 10^{2n - 1} + 5$ is divisible by 99 for $n \in {\mathbb N}\text{.}$

7

Show that

$$\begin{equation*} \sqrt[n]{a_1 a_2 \cdots a_n} \leq \frac{1}{n} \sum_{k = 1}^{n} a_k. \end{equation*}$$

8

Prove the Leibniz rule for $f^{(n)} (x)\text{,}$ where $f^{(n)}$ is the $n$th derivative of $f\text{;}$ that is, show that

$$\begin{equation*} (fg)^{(n)}(x) = \sum_{k = 0}^{n} \binom{n}{k} f^{(k)}(x) g^{(n - k)}(x). \end{equation*}$$

Hint

Follow the proof in Example 2.4.

9

Use induction to prove that $1 + 2 + 2^2 + \cdots + 2^n = 2^{n + 1} - 1$ for $n \in {\mathbb N}\text{.}$

10

Prove that

$$\begin{equation*} \frac{1}{2}+ \frac{1}{6} + \cdots + \frac{1}{n(n + 1)} = \frac{n}{n + 1} \end{equation*}$$

for $n \in {\mathbb N}\text{.}$

11

If $x$ is a nonnegative real number, then show that $(1 + x)^n - 1 \geq nx$ for $n = 0, 1, 2, \ldots\text{.}$

Hint

The base case, $S(0): (1 + x)^0 - 1 = 0 \geq 0 = 0 \cdot x$ is true. Assume $S(k): (1 + x)^k -1 \geq kx$ is true. Then

$$\begin{align*} (1 + x)^{k + 1} - 1 & = (1 + x)(1 + x)^k -1\\ & = (1 + x)^k + x(1 + x)^k - 1\\ & \geq kx + x(1 + x)^k\\ & \geq kx + x\\ & = (k + 1)x, \end{align*}$$

so $S(k + 1)$ is true. Therefore, $S(n)$ is true for all positive integers $n\text{.}$

12Power Sets

Let $X$ be a set. Define the of $X\text{,}$ denoted ${\mathcal P}(X)\text{,}$ to be the set of all subsets of $X\text{.}$ For example,

$$\begin{equation*} {\mathcal P}( \{a, b\} ) = \{ \emptyset, \{a\}, \{b\}, \{a, b\} \}. \end{equation*}$$

For every positive integer $n\text{,}$ show that a set with exactly $n$ elements has a power set with exactly $2^n$ elements.

13

Prove that the two principles of mathematical induction stated in Section 2.1 are equivalent.

14

Show that the Principle of Well-Ordering for the natural numbers implies that 1 is the smallest natural number. Use this result to show that the Principle of Well-Ordering implies the Principle of Mathematical Induction; that is, show that if $S \subset {\mathbb N}$ such that $1 \in S$ and $n + 1 \in S$ whenever $n \in S\text{,}$ then $S = {\mathbb N}\text{.}$

15

For each of the following pairs of numbers $a$ and $b\text{,}$ calculate $\gcd(a,b)$ and find integers $r$ and $s$ such that $\gcd(a,b) = ra + sb\text{.}$

1. 14 and 39

2. 234 and 165

3. 1739 and 9923

4. 471 and 562

5. 23,771 and 19,945

6. $-4357$ and 3754

16

Let $a$ and $b$ be nonzero integers. If there exist integers $r$ and $s$ such that $ar + bs =1\text{,}$ show that $a$ and $b$ are relatively prime.

17Fibonacci Numbers

The Fibonacci numbers are

$$\begin{equation*} 1, 1, 2, 3, 5, 8, 13, 21, \ldots. \end{equation*}$$

We can define them inductively by $f_1 = 1\text{,}$ $f_2 = 1\text{,}$ and $f_{n + 2} = f_{n + 1} + f_n$ for $n \in {\mathbb N}\text{.}$

1. Prove that $f_n \lt 2^n\text{.}$

2. Prove that $f_{n + 1} f_{n - 1} = f^2_n + (-1)^n\text{,}$ $n \geq 2\text{.}$

3. Prove that $f_n = [(1 + \sqrt{5}\, )^n - (1 - \sqrt{5}\, )^n]/ 2^n \sqrt{5}\text{.}$

4. Show that $\lim_{n \rightarrow \infty} f_n / f_{n + 1} = (\sqrt{5} - 1)/2\text{.}$

5. Prove that $f_n$ and $f_{n + 1}$ are relatively prime.

Hint

For (a) and (b) use mathematical induction. (c) Show that $f_1 = 1\text{,}$ $f_2 = 1\text{,}$ and $f_{n + 2} = f_{n + 1} + f_n\text{.}$ (d) Use part (c). (e) Use part (b) and Exercise 2.3.16.

18

Let $a$ and $b$ be integers such that $\gcd(a,b) = 1\text{.}$ Let $r$ and $s$ be integers such that $ar + bs =1\text{.}$ Prove that

$$\begin{equation*} \gcd(a,s) = \gcd(r,b) = \gcd(r,s) = 1. \end{equation*}$$

19

Let $x, y \in {\mathbb N}$ be relatively prime. If $xy$ is a perfect square, prove that $x$ and $y$ must both be perfect squares.

Hint

Use the Fundamental Theorem of Arithmetic.

20

Using the division algorithm, show that every perfect square is of the form $4k$ or $4k + 1$ for some nonnegative integer $k\text{.}$

21

Suppose that $a, b, r, s$ are pairwise relatively prime and that

$$\begin{align*} a^2 + b^2 & = r^2\\ a^2 - b^2 & = s^2. \end{align*}$$

Prove that $a\text{,}$ $r\text{,}$ and $s$ are odd and $b$ is even.

22

Let $n \in {\mathbb N}\text{.}$ Use the division algorithm to prove that every integer is congruent mod $n$ to precisely one of the integers $0, 1, \ldots, n-1\text{.}$ Conclude that if $r$ is an integer, then there is exactly one $s$ in ${\mathbb Z}$ such that $0 \leq s \lt n$ and $[r] = [s]\text{.}$ Hence, the integers are indeed partitioned by congruence mod $n\text{.}$

23

Define the of two nonzero integers $a$ and $b\text{,}$ denoted by $\lcm(a,b)\text{,}$ to be the nonnegative integer $m$ such that both $a$ and $b$ divide $m\text{,}$ and if $a$ and $b$ divide any other integer $n\text{,}$ then $m$ also divides $n\text{.}$ Prove there exists a unique least common multiple for any two integers $a$ and $b\text{.}$

Hint

Use the Principle of Well-Ordering and the division algorithm.

24

If $d= \gcd(a, b)$ and $m = \lcm(a, b)\text{,}$ prove that $dm = |ab|\text{.}$

25

Show that $\lcm(a,b) = ab$ if and only if $\gcd(a,b) = 1\text{.}$

26

Prove that $\gcd(a,c) = \gcd(b,c) =1$ if and only if $\gcd(ab,c) = 1$ for integers $a\text{,}$ $b\text{,}$ and $c\text{.}$

27

Let $a, b, c \in {\mathbb Z}\text{.}$ Prove that if $\gcd(a,b) = 1$ and $a \mid bc\text{,}$ then $a \mid c\text{.}$

Hint

Since $\gcd(a,b) = 1\text{,}$ there exist integers $r$ and $s$ such that $ar + bs = 1\text{.}$ Thus, $acr + bcs = c\text{.}$

28

Let $p \geq 2\text{.}$ Prove that if $2^p - 1$ is prime, then $p$ must also be prime.

29

Prove that there are an infinite number of primes of the form $6n + 5\text{.}$

Hint

Every prime must be of the form 2, 3, $6n + 1\text{,}$ or $6n + 5\text{.}$ Suppose there are only finitely many primes of the form $6k + 5\text{.}$

30

Prove that there are an infinite number of primes of the form $4n - 1\text{.}$

31

Using the fact that 2 is prime, show that there do not exist integers $p$ and $q$ such that $p^2 = 2 q^2\text{.}$ Demonstrate that therefore $\sqrt{2}$ cannot be a rational number.