Graded: 5.1 #10, #22

4.4 #17 – See back of book

4.4 #34

By Fermat’s Little Theorem, $23^{40}\equiv 1\pmod{41}$. Thus, $23^{1002}=23^{40\cdot 25+2}=(23^{40})^{25}\cdot 23^2\equiv 1(23^2)\pmod{41}$. Computation yields a remainder of 37.

4.4 #35 – See back of book

4.4 #38

a) $$3^4\equiv 1\pmod 5 \implies 3^{302}=(3^4)^{75}\cdot 3^2\equiv 1\cdot 3^2\equiv 4\pmod 5$$ $$3^6\equiv 1\pmod 7 \implies 3^{302}=(3^6)^{50}\cdot 3^2\equiv 1\cdot 3^2\equiv 2\pmod 7$$ $$3^{10}\equiv 1\pmod{11} \implies 3^{302}=(3^{10})^{30}\cdot 3^2\equiv 1\cdot 3^2\equiv 9\pmod{11}$$

b) If $n=3^{302}$, then $n$ satisfies the system $$\begin{cases} n\equiv 4\pmod 5 \\ n\equiv 2\pmod 7 \\ n\equiv 9\pmod{11} \end{cases}.$$ The solution to this system is $n\equiv 9\pmod{385}$. Thus, $3^{302}\textbf{ mod }385 = 9$.

4.6 #26

The decryption key is $d=2753$, and the decrypted message is SQUIRREL.

5.1 #3 – See back of book

5.1 #6

Basis step: When $n=1$, the claim is that $1\cdot 1! = 2! – 1$. This is true.

Inductive step: Suppose that the proposition is true for $n=k$, i.e. $$1\cdot 1! + 2\cdot 2! + \cdots + k\cdot k! = (k+1)! – 1.$$ Then we may add $(k+1)\cdot(k+1)!$ to each side to deduce the following result: \begin{align*} 1\cdot 1! + 2\cdot 2! + \cdots + k\cdot k! + (k+1)\cdot(k+1)! &= (k+1)\cdot(k+1)! + (k+1)! – 1 \\ &= (k+1+1)\cdot(k+1)! – 1. \end{align*} This is the proposition for $n=k+1$.

Because the desired proposition is true when $n=1$, and because the proposition for $n=k$ implies the proposition for $n=k+1$, we conclude by mathematical induction that the proposition is true for all integers $n\ge 1$. $\blacksquare$

$\bigstar$ 5.1 #10

a) Here are the first few values:

\begin{align*} \frac 1{1\cdot 2} &= \frac 12 \\ \frac 1{1\cdot 2}+\frac 1{2\cdot 3} &= \frac 23 \\ \frac 1{1\cdot 2}+\frac 1{2\cdot 3}+\frac 1{3\cdot 4} &= \frac 34 \end{align*} It appears that $$\frac 1{1\cdot 2}+\frac 1{2\cdot 3}+\cdots+\frac 1{n(n+1)} = \frac n{n+1}.$$

b) The basis step is covered by part (a). For the inductive step, suppose that $$\frac 1{1\cdot 2}+\frac 1{2\cdot 3}+\cdots+\frac 1{k(k+1)} = \frac k{k+1}.$$ Then adding $\dfrac 1{(k+1)(k+2)}$ to both sides yields \begin{align*} \frac 1{1\cdot 2}+\frac 1{2\cdot 3}+\cdots+\frac 1{k(k+1)}+\frac 1{(k+1)(k+2)} &= \frac k{k+1}+\frac 1{(k+1)(k+2)} \\ &= \frac{k(k+2)+1}{(k+1)(k+2)} \\ &= \frac{k^2+2k+1}{(k+1)(k+2)} \\ &= \frac{(k+1)(k+1)}{(k+1)(k+2)} \\ &= \frac{k+1}{k+2}. \end{align*} This completes the inductive step. We conclude by mathematical induction that our conjectured formula is valid for all integers $n\ge 1$. $\blacksquare$

5.1 #20

Basis step: If $n=7$, then the claim is that $3^7 < 7!$. This is true ($3^7=2187$ and $7!=5040$).

Inductive step: Suppose $3^k < k!$, where $k\ge 7$. Then $3^{k+1} < 3\cdot k! < (k+1)\cdot k! = (k+1)!$.

We conclude by mathematical induction that $3^n < n!$ for all integers $n > 6$. $\blacksquare$

Remark. Notice that the logic of the inductive step holds for $k\ge 2$. If we try to prove that $3^n < n!$ for $n\ge 2$, the inductive step works just fine; it’s the basis step that fails. See #50 for a similar example. The lesson is that, while the basis step in an inductive proof is often trivially easy, we still do need to perform it to make sure the proof is sound!

$\bigstar$ 5.1 #22

$n^2\le n!$ holds for $n=0,1,$ and for $n\ge 4$.

The cases $n\le 3$ can be checked by hand. For the rest, we argue by induction.

The base case is $n=4$. It is true that $4^2\le 4!$ (since $4^2=16$ and $4!=24$).

For the inductive step, suppose $k^2\le k!$, where $k\ge 4$. Then \begin{align*} (k+1)^2 &= k^2+2k+1 \\ &\le k!+2k+1 \\ &\le k!+3k \\ &\le k!+(k!)k \\ &= k!(1+k) \\ &= (k+1)!. \end{align*} This completes the inductive step. We conclude by mathematical induction that $n^2\le n!$ for all integers $n\ge 4$. $\blacksquare$

5.1 #32

Basis step: For $n=1$, the claim is that $3$ divides $1^3+2(1)$, which equals $3$. This is true.

Inductive step: Assume $3$ divides $k^3+2k$. By definition, $3$ also divides $3(k^2+k+1)$. Therefore, $3$ divides $k^3+2k+3(k^2+k+1)$, which is equal to $k^3+3k^2+5k+3$, which in turn is equal to $(k+1)^3+2(k+1)$.

We conclude by mathematical induction that $3$ divides $n^3+2n$ for all integers $n\ge 1$. $\blacksquare$

Remark. There are also various non-inductive methods of showing that $3~|~n^3+2n$ for all integers $n$. One way is to consider three cases: $n\equiv 0\pmod 3$, $n\equiv 1\pmod 3$, and $n\equiv 2\pmod 3$, and show that in each case $n^3+2n\equiv 0\pmod 3$. Another way is to use Fermat’s Little Theorem (or, more precisely, its corollary), which shows that $n^3\equiv n\pmod 3$ for all integers $n$. Then $n^3+2n\equiv 3n\equiv 0\pmod 3$. Yet another approach is to note that $n^3+2n = (n^3-n)+3n = (n-1)(n)(n+1)+3n$. Here, $(n-1)(n)(n+1)$ is divisible by 3 because it’s the product of three consecutive integers, one of which must be divisible by 3; and $3n$ is self-evidently divisible by 3 as well.

5.1 #50

The basis step is a desperate lie!