\documentstyle[11pt]{report}
\oddsidemargin=.35in
\textwidth=6.15in
\topmargin=-.6in
\textheight=8.75in
\setcounter{page}{9}
\begin{document}
\vspace*{1in}
\begin{center}
{\large\bf Chapter 2}\\
\vspace*{.1in}
{\small \em The four different branches of Arithmetic--\\
Ambition, Distraction, Uglification, and Derision.}\\
\hspace*{1.75in}-The Mock Turtle
\end{center}
\vspace*{.4in}
\noindent {\bf Definition} The $n^{th}$ triangular number, $t_{n}$, is the sum of the first $n$ positive integers, $$t_{n} = 1+2+3+... +n.$$
So, for example, $ t_{1} = 1$, $t_{2} = 3 = 1+2$, $t_{3} = 6 = 1+2+3$, and $t_{341} = 41,311.$
Triangular numbers can be visualized as the total area of a staircase; that's why they're called {\em triangular} numbers. The ancient Greeks were, and many modern folks are, interested in the geometry of numbers and defined lots of families of {\it figurate} numbers. Some of these are familiar to you--why do you think we say $x$-$squared$ and $x$-$cubed$ anyway? Perhaps less familiar are the pentagonal, hexagonal, heptagonal, $\ldots$ numbers which correspond to arrangements of points of the corresponding shape. All of these families have interesting properties, consider what follows an existence proof of that assertion in the case of the triangular numbers.
\[ t_{4} \mbox{ would be the area of: } \begin{array}{l}
\Box \\ \Box \Box \\ \Box \Box \Box \\ \Box \Box \Box \Box \end{array} \] \vspace*{.2in} \newline
\noindent {\bf Problem 2a} Prove that $N$ is triangular if and only if $N = {n(n+1) \over 2}$ for some positive integer $n$.
\vspace*{.075in}
\begin{quote}
\noindent Proof: Putting together two staircases with side $n$ gives a rectangle with sides $n$ and $n+1$. \newline
\[ \left. \begin{array}{c} \overbrace { \triangle \Box \Box \Box \Box}^{n+1} \\
\triangle \triangle \Box \Box \Box \\
\triangle \triangle \triangle \Box \Box \\
\triangle \triangle \triangle \triangle \Box \end{array}
\right \} n \]
Consider the area of this rectangle which is composed of a triangular number added itself. This area is $n(n+1)=2N$. Thus, $ N={n(n+1) \over 2}.$
\end{quote}
\vspace*{.1in}
\noindent {\bf Problem 2b} Prove $N$ is triangular iff $8N+1$ is a perfect square.
\vspace*{.075in}
\begin{quote}
\noindent Proof: As above the double of a triangular number is the product of two consecutive numbers. Geometrically, an $n$ by $n+1$ rectangle. Below is the picture for $t_2=N$, notice the four 2x3 rectangles each composed of two copies of $t_2$. This picture clearly generalizes to the cases for larger $n$. (Just in case you don't believe that, an algebraic proof is given below.)
$$
\begin{array}{ccccc}
\Box & \Box & \Box & \Diamond & \Diamond \\
\Box & \Box & \Box & \Diamond & \Diamond \\
\heartsuit & \heartsuit & \triangle & \Diamond & \Diamond \\
\heartsuit & \heartsuit & \clubsuit & \clubsuit & \clubsuit \\
\heartsuit & \heartsuit & \clubsuit & \clubsuit & \clubsuit \\
\end{array}
$$
\noindent Algebraic Proof:
$$\displaystyle{{(8n(n+1)) \over 2}} + 1 = 4n(n+1)+1 = 4n^2 + 4n +1 = (2n+1)^2$$
\end{quote}
\vspace*{.08in}
\noindent {\bf Problem 2c} Prove that the sum of two consecutive triangular numbers is a perfect square.
\vspace*{.075in}
\begin{quote}
\noindent Proof:
$$
\begin{array}{c}
\bigcirc
\end{array}
\hspace*{.4in}
\begin{array}{cc}
\bigcirc & \rule{.08in}{.08in}\\[6pt]
\rule{.08in}{.08in} & \rule{.08in}{.08in}
\end{array}
\hspace*{.4in}
\begin{array}{ccc}
\bigcirc & \bigcirc & \triangle\\[6pt]
\bigcirc & \triangle & \triangle\\[6pt]
\triangle & \triangle & \triangle
\end{array}
\hspace*{.4in}
\ldots
\hspace*{.4in}
\begin{array}{cccccc}
\diamondsuit & \diamondsuit & \diamondsuit & \diamondsuit & \diamondsuit & \spadesuit\\[6pt]
\diamondsuit & \diamondsuit & \diamondsuit & \diamondsuit & \spadesuit & \spadesuit\\[6pt]
\diamondsuit & \diamondsuit & \diamondsuit & \spadesuit & \spadesuit & \spadesuit\\[6pt]
\diamondsuit & \diamondsuit & \spadesuit & \spadesuit & \spadesuit & \spadesuit\\[6pt]
\diamondsuit & \spadesuit & \spadesuit & \spadesuit & \spadesuit & \spadesuit\\[6pt]
\spadesuit & \spadesuit & \spadesuit & \spadesuit & \spadesuit & \spadesuit
\end{array}
\hspace*{.4in}
\ldots
$$
\vspace*{.1in}
\noindent Algebraic proof:
$${n(n+1) \over 2} + {(n+1)(n+2) \over 2} = {(2n+2)(n+1) \over 2} = (n+1)^2$$
\end{quote}
\vspace*{.1in}
\noindent {\bf Problem 2d} Prove that if $N$ is triangular, then $9N+1$ and $25N+3$ are triangular.
\vspace*{.1in}
\begin{quote}
\noindent Proof:
$$9N+1= {9n(n+1) \over 2} + 1 = {(9n^2 +9n +2) \over 2} = {(3n+1)(3n+2) \over 2}$$
\vspace*{.1in}
This is triangular since it is of the form ${m(m+1) \over 2}$.
\vspace*{.075in}
$$25N+3 = {25n(n+1) \over 2} +3 = {(25n^2 +25n+6) \over 2} = {(5n+2)(5n+3) \over 2}$$ \vspace*{.1in} \newline
As before, this is of the form ${m(m+1) \over 2}$, so it is triangular.
\vspace*{.075in}
\noindent Alternate Proof: From 2b a number, $M$, is triangular if and only if $8M+1$ is a square. Let's apply this test to $M=9N+1$.
$$8(9N+1)+1 = 72N+9 = 9(8N+1)$$
Since we are given that $N$ is triangular $8N+1$ is a square, and 9 is, of course, a square. Thus this whole expression is a square and, by 2b, $9N+1$ is triangular.
Using the same method we have
$$8(25N+3)+1 = 200N+25 = 25(8N+1)$$
\end{quote}
\vspace*{.08in}
\noindent {\bf Problem 2e} Generalize the previous result.
Claim: If $N$ is triangular, then $(2k+1)^2N + {k(k+1) \over 2}$ is triangular.
\vspace*{.075in}
\begin{quote}
\noindent Proof:
$$(2k+1)^2 N + {k(k+1) \over 2} = (2k+1)^2 {n(n+1) \over 2} +{k(k+1) \over 2} $$
$$={(2k+1)^2 \times n^2 +(2k+1)^2 \times n +k(k+1)\over 2} $$
$$= {(2k+1)^2 \times n^2 +(2k+1)(k+(k+1))n+k(k+1) \over 2} $$
$$={[(2k+1)n+k][(2k+1)n+(k+1)] \over 2} $$
$$={[(2k+1)n+k][((2k+1)n+k)+1)] \over 2}$$
\vspace*{.08in}
Alternate Proof: We'll use 2b and test whether $8[(2k+1)^2N+{k(k+1) \over 2}]+1$ is a square. Notice that $(2k+1)^2=8({k(k+1) \over 2})+1$.
$$8((8t_k+1)N +t_k)+1 = (64t_k+8)N+(8t_k+1) = (8t_k+1)(8N+1)$$
The final expression is a square, by 2b. So $(8t_k+1)N +t_k$ must be triangular, also by 2b.
\end{quote}
\vspace*{.08in}
\noindent {\bf Problem 2f} Find a simple formula for the sum of the first $m$ triangular numbers.
\begin{quote}
We know from 2c that $t_{n} + t_{n+1} = (n+1)^2$
\noindent Case 1: $m$ is even.
$$t_{m} + t_{m-1} + ... + t_{4} + t_{3} + t_{2} + t_{1} $$
$$ = m^2 + (m-2)^2 + ... + 4^2 +2^2 $$
$$= 4 ({m^2 \over 2} + ... + 2^2 + 1^2)$$
Now, we know that
$$\sum_{i=0}^k i^2 = {k (k+1) (2k+1) \over 6} $$
So,
$$4({m^2 \over 2} + ... + 2^2 + 1^2)
= {2 \over 3} {m \over 2}({m \over 2} +1)(m+1) $$
$$= {m({m \over 2} +1)(m+1) \over 3}= {m(m+1)(m+2) \over 6}$$
\vspace*{.05in}
\noindent Case 2: $m$ is odd.
$$t_{m} + t_{m-1} + ... + t_{4} + t_{3} + t_{2} + t_{1} $$
$$={m(m+1) \over 2} +(m-1)^2 + (m-3)^2 + ... + 4^2 +2^2 $$
$$={(3m(m+1)+(m-1)m(m+1)) \over 6} $$
$$={(m(m+1)(3+m-1)) \over 6} $$
$$={m(m+1)(m+2) \over 6}$$
\end{quote}
\vspace*{.08in}
\noindent {\bf Problem 2g} Are there any squares that are also triangular numbers?
\vspace*{.08in}
\begin{quote}
Yes, for example 1, 36, and 1225. Is there a pattern here? We'll get back to this.
\end{quote}
\vspace*{.08in}
\noindent {\bf Problem 3} Show that ${7 \mid 2^{3n} -1}$, for all $n$.
\begin{quote}
\noindent Proof:
First note that $$2^{3n} -1 = 8^n -1$$
We also know that in general,
$$a^n -1 = (a-1)(a^{n-1} +a^{n-2} + ... + 1)$$
Thus, in our case
$$2^{3n} -1 = 8^n -1 $$
$$= (8-1)(8^{n-1} +8^{n-2} + ... + 1) $$
$$= 7 \cdot (8^{n-1} +8^{n-2} + ... + 1)$$
This is clearly divisible by 7.
\end{quote}
\vspace*{.08in}
\noindent {\bf Problem 4} Show that ${8 \mid 2^{3n} + 7}$ , for all n.
\begin{quote}
Proof: To begin an induction proof notice that 8 divides 16 ($n=1$). Assume that 8 divides $9^n+7$ for some $n$. Then,
$$9^{n+1}+7=9(9^n+7)-56$$
Both terms on the right are clearly divisible by 8.
\end{quote}
\vspace*{.1in}
\noindent {\bf Problem 5} Show that $2^n +(-1)^{n+1}$ is always divisible by $3$.
\vspace*{.1in}
\begin{quote}
Proof: Notice that $2^n$ cannot be a multiple of 3 and therefore must be of the form $3k \pm 1$. So, the statement is merely that the plus and minus sign alternate with $n$, beginning with minus when $n=1$. This is easily verified, $2(3k+1)=3(2k+1)-1$. Similarly for $3k-1$.
\end{quote}
\vspace*{.1in}
\noindent {\bf Problem 6} Show that the sum of the squares of 2 odd integers cannot be itself a square.
\vspace*{.1in}
\begin{quote}
Proof:
$$(2k+1)^2 + (2n+1)^2 = 4(k^2 + n^2 + k + n) + 2.$$
A number of the form $4k+2$ cannot be a square.
\end{quote}
\hspace*{1.7in} Day 3, September 14, notes scribed by {\it Michael Hanslick.}
\vspace*{.1in}
A list of questions that arise from inspection of the table produced in answer to problem 1.
\begin{enumerate}
\item There is often more than one way to represent an integer as the sum of $n$ squares.
\item Why don't you ever need more than 4 squares in such a sum, when $n \leq 400$?
\item What about the number of squares in a sum when $n > 400$?
\item When do two squares suffice?
\item When do three squares suffice?
\item How frequently do you need four squares?
\item Can all even numbers be written as the sum of 2 primes?
\item In how many ways?
\item When is the sum of the divisors of $n >, =, {\mbox or} < n$?
\item What is the number of divisors of a perfect number $n$?
\item Are there infinitely many deficient numbers? abundant numbers? perfect numbers?
\end{enumerate}
\noindent {\bf Definition} An integer $n$ is said to be {\it deficient} when the sum of the divisors of $n$ is less than $n$. We call $n$ {\it abundant} if its divisor sum is more than $n$, and we say it is {\it perfect} if its divisor sum equals $n$. (Here, the divisor sum does not include $n$ itself)
\vspace*{.1in}
\noindent {\bf Prime Numbers}
\vspace*{.1in}
\noindent {\bf Definition} A number $p>1$ is {\it prime} if 1 and $p$ are its only divisors. A number greater than one is called {\it composite} if it is not prime. (One itself is neither prime nor composite.)
\vspace*{.1in}
\noindent {\bf Theorem 2.1} If $p$ is prime and $p|ab$, then $p|a$ or $p|b$.
\begin{quote}
\vspace*{.1in}
\noindent Proof: Suppose $p$ does not divide $a$. Then since $gcd(p,a)=1$, Euclid's lemma implies that $p$ divides $b$.
\end{quote}
\noindent {\bf Corollary 2.1.1} If $p|a_1a_2....a_k$ and $p$ is prime, then $p|a_j$ for some $1 \leq j \leq k$.
\vspace*{.1in}
\begin{quote}
\noindent Proof: A straightforward induction, Theorem 2.1 establishes the base case.\end{quote}
\vspace*{.1in}
\noindent {\bf Corollary 2.1.2} If $p|q_1q_2....q_n$, $p$ and $q_i$ all prime, then $p = q_i$ for some $1 \leq i \leq n$.
\vspace*{.1in}
\begin{quote}
Proof: Follows immediately from Corollary 1.
\end{quote}
\vspace*{.1in}
\noindent {\bf Fundamental Theorem of Arithmetic}
Every number $a > 1$ can be written uniquely, up to the order of the factors, as a product of primes.
\vspace*{.1in}
\begin{quote}
Proof: If $a$ is a prime, we're done. If $a$ is composite, let $D$ = \mbox \{$d$: $d|a$ and $d \neq 1$ or $a$\}. $D$ has a least element, say $\delta_1$. Note that $\delta_1$ is prime, else it has a divisor which also divides $a$.
\vspace*{.1in}
Now we have $a = \delta_1 a_1$, and $a_1 < a$. Continuing in this way, we obtain:
$$a = \delta_1 \delta_2 a_2\,\,\,\,\,\,a_2 < a_1$$
\vspace*{.05in}
$$a = \delta_1 \delta_2 \delta_3 a_3\,\,\,\,\,\,a_3 < a_2$$
And so on. Clearly, this process ends in a finite number of steps, because the $a_i$ are a decreasing sequence of positive numbers. At which point we have
$$a = \delta_1 \delta_2\delta_3\ldots \delta_r$$
Where $\delta_1,...,\delta_r$ are all prime. Now all that remains to show is that this representation of $a$ as a product of primes is in fact unique.
\hspace*{1.6in} Day 4, September 16, notes scribed by {\it Steve Griffeth.}
\noindent Proof of Uniqueness
\vspace*{.05in}
Suppose, $m\geq n$, $p_i \leq p_{i+1}$, $q_i \leq q_{i+1}$, $p_i$ and $q_i$ are prime.
$$a = p_1 p_2 . . .p_n = q_1 q_2 . . .q_m$$
Now, $p_1 \mid a$, so $p_1 \mid q_1 q_2 . . . q_m$. By Corollary 2 of Theorem 2.1 $p_1 \in \{q_1, q_2, \ldots, q_m\}$. \newline
Likewise, $q_1 \in \{p_1, p_2, \ldots, p_n$\}. \newline
So $p_1 = q_k \geq q_1$ and $q_1 = p_k \geq p_1$. \newline
Since $p_1 \geq q_1$ and $q_1 \geq p_1$, $p_1 = q_1$ \vspace*{.05in} \newline
Repeat the argument for all $i$, $1 \geq i \geq n$. Divide
$$a = p_1 p_2 . . .p_n = q_1 q_2 . . .q_m$$
by $p_1 p_2 . . .p_n$ to get
$$1=1=q_{n+1} q_{n+2} . . .q_m$$
If they exist, $q_{n+1} q_{n+2} \ldots q_m$ must all be greater than $1$. So they don't exist, $m=n$, and the representation of $a$ is unique.
\end{quote}
\noindent {\bf An Introduction to Pythagorean Triples} \vspace*{.05in}
Consider the following table of numbers. It was generated by trying to find square triangles (problem 2g). Notice that a row gives a square triangle whenever its second entry and either its third or fourth entry are both squares. So that rows 3, 7, and 17 all give square triangles.
\vspace*{.05in}
\begin{center}
\begin{tabular}{||l|l|l|l||} \hline
$n$ & $n^2$ & $\frac{n^2-1}{2}$ & $\frac{n^2+1}{2}$ \\ \hline
3 & 9 & 4 & 5 \\ \hline
5 & 25 & 12 & 13 \\ \hline
7 & 49 & 24 & 25 \\ \hline
9 & 81 & 40 & 41 \\ \hline
11 & 121 & 60 & 61 \\ \hline
13 & 169 & 84 & 85 \\ \hline
15 & 225 & 112 & 113 \\ \hline
17 & 289 & 144 & 145 \\ \hline
\end{tabular}
\end{center}
\vspace*{.05in}
This table has (at least) two interesting features:
\begin{enumerate}
\item The third column is $4 t_n$ where $t_n$ is the $n^{th}$ triangular number.
\item Columns 1,3, and 4 make Pythagoreon Triples. This suggests that given an odd number $n \geq 3$, you can always generate a Pythagorean Triple of the form $(n, x, x+1)$.
\end{enumerate}
\begin{quote}
Proof of 1. We want to show ${(2k+1)^2 -1 \over 2} = 4 \cdot {k(k+1) \over 2}$, since $2k+1$ is an odd number and ${k(k+1) \over 2}$ is the $k^{th}$ triangular number. \newline
Work with the left side: \newline
$${(2k+1)^2 -1 \over 2} = {4k^2 +4k+1-1 \over 2} =4(k^2 +k)
=4 {k(k+1) \over 2}$$
\vspace*{.05in}
\noindent Proof of 2. We want to show $n^2 + ({n^2 -1 \over 2})^2 = ({n^2 +1 \over 2})^2$. Again work from the left:
$$n^2 + {(n^2 -1)^2 \over 4} = {4n^2 \over 4} + {n^4 -2n^2 +1 \over 4}
= {n^4 +2n^2 +1 \over 4}
= {(n^2 +1)^2 \over 4}$$
\end{quote}
\vspace*{.05in}
{\bf Problem 2g revisited and partially solved.}
Consider the two recursively defined sequences,
\begin{quote}
$$n_k = n_{k-1} + d_{k-1} \mbox{, } (n_1 = 1)$$ \newline
and \newline
$$d_k=n_{k-1} + n_k \mbox{, } (d_1 = 1)$$
The first few terms are
$$n_k= 1,\,\,\,2,\,\,\,5,\,\,\,12,\,\,\,29,\,\,\,70,\ldots $$
$$d_k=1,\,\,\,3,\,\,\,7,\,\,\,17,\,\,\,41,\,\,\,99,\ldots $$
From these lists, it appears that
$$d_k^2=2n_k^2 +(-1)^k$$
Proof (PMI): Basis step $(k=1)$, $n_1 = d_1 = 1$, and
$$1^2 = 2(1)^2 + (-1)^1$$
Our inductive hypothesis is
$(-1)^k=2n_{k-1}^2 -d_{k-1}^2$.
So, we will show that
$$(-1)^{k+1}=2n_k^2 -d_k^2$$
Using the definitions of $n_k$ and $d_k$
$$2n_k^2 -d_k^2 = n_k^2 + (n_{k-1} +d_{k-1})^2 - (n_{k-1} + n_k)^2$$
$$= n_k^2 + (n_{k-1}^2 + 2n_{k-1}d_{k-1} + d_{k-1}^2) -(n_{k-1}^2 + 2n_{k-1}n_k + n_k^2)$$
$$=2n_{k-1}d_{k-1} + d_{k-1}^2 - 2n_{k-1}n_k$$
Again substituting,
$$=2n_{k-1}d_{k-1} + d_{k-1}^2 -2n_{k-1}(n_{k-1} + d_{k-1})$$ $$=2n_{k-1}d_{k-1} + d_{k-1}^2 -2n_{k-1}n_{k-1} -2n_{k-1}d_{k-1}$$$$=d_{k-1}^2 -2n_{k-1}^2 $$
$$=(-1)(2n_{k-1}^2-d_{k-1}^2)$$
But, from our inductive hypothesis
this is exactly $(-1)^{k+1}$.
\end{quote}
Why did we do all of this anyway? Notice that $n_k^2 d_k^2$ is both a perfect square and a triangular number
$$n_k^2 d_k^2 = n_k^2 (2n_k^2 + (-1)^k)$$
$$={2n_k^2 \over 2} (2n_k^2 + (-1)^k)$$
Since $2n_k^2$ and $2n_k^2 + (-1)^k$ always differ by one, the above expression is of the form ${m(m+1) \over 2}$ and is thus a triangular number! So we have found infinitely many numbers that are both square and triangular. Have we found them all? (See Chapter 3.)
\vspace*{.1in}
\hspace*{1.5in} Day 4, September 16, notes scribed by {\it Jay Huston, Michael Hanslick}, and {\it Drew Schroeder.}
\noindent {\bf The Sieve of Erastothenes}
Some of us spent our summer finding primes. Some of us didn't. But, either way, the Sieve of Erastothenes is an easy way to find all of the primes less than a given number. List the numbers from $1$ to $n$. Cross out the number $1$ (by definition, $1$ is not prime). Then, beginning with $2$, skip the number you start with and cross out all other multiples of that number (i.e. skip $2$, cross out $4$, $6$, $8$, etc.). Go to the next non-eliminated number, repeat (i.e. go to $3$, cross out its multiples, then $5$, etc.). Once the end has been reached, all remaining numbers are prime. (In actuality, you only need to go up to $\sqrt n$, since there will be no multiples past that point.) An example up to the number $50$ is shown below.
\begin{center}
$\begin{array}{cccccccccc}
\not\!1 & 2 & 3 & \not\!4 & 5 & \not\!6 & 7 & \not\!8 & \not\!9 & \not\!\!10 \\
11 & \not\!\!12 & 13 & \not\!\!14 & \not\!\!15 & \not\!\!16 & 17 & \not\!\!18 & 19 & \not\!\!20 \\
\not\!\!21 & \not\!\!22 & 23 & \not\!\!24 & \not\!\!25 & \not\!\!26 & \not\!\!27 & \not\!\!28 & 29 & \not\!\!30 \\
31 & \not\!\!32 & \not\!\!33 & \not\!\!34 & \not\!\!35 & \not\!\!36 & 37 & \not\!\!38 & \not\!\!39 & \not\!\!40 \\
41 & \not\!\!42 & 43 & \not\!\!44 & \not\!\!45 & \not\!\!46 & 47 & \not\!\!48 & \not\!\!49 & \not\!\!50 \\
\end{array}$
\end{center}
And, before you embark on an expedition to find all of the primes by using the Sieve, you might want to check out this next theorem...
\vspace*{.2in}
\noindent {\bf Theorem 2.2} (from Euclid's {\it Elements}) There are infinitely many prime numbers.
\begin{quote}
\noindent{Proof:} Suppose there are only finitely many prime numbers. Then define the set $T$ as:
$$T=\{t\mid t \mbox{ is prime }\}=\{2,3,\ldots,P\}\mbox{.}$$
Now, consider the number $N=2\cdot 3\cdot\cdots\cdot P+1$.
By construction, $N$ is not divisible by any element $t\in T$. Therefore, there are two possibilities: either $N$ itself is prime, or it factors into a product of primes none of whom are in $T$. In either case $T$ does not contain all the primes and we have a contradiction to our hypothesis of only finitely many primes.
\end{quote}
So, as you can see, you and the Sieve might be there a while.
\vspace*{.2in}
\noindent {\bf Problem 9} Prove that $n^5-n$ is always divisible by $30$.
\begin{quote}
\noindent{Proof:} To show $30 | n^5-n$, we must show that $2,3,$ and $5$ all divide $n^5-n$.
First, we factor $n^5-n$:
$$n^5-n=(n-1)n(n+1)(n^2+1)\mbox{.}$$
We have three consecutive integers in $n-1, n,$ and $n+1$. Thus, by the Pigeonhole Principle, at least one of these is divisible by $2$, and exactly one is divisible by $3$. So, both $2$ and $3$ divide $n^5-n$. It remains to be shown that $5 | n^5-n$. We can write $n$ in the form $n=5k+r$, where $0\leq r\leq 4$. This gives us five cases to consider:
\hspace{.25in} Case $1$: $r=0$. If $n=5k+0$, then, clearly, $5 | n$.
\hspace{.25in} Case $2$: $r=1$. If $n=5k+1$, then $5k=n-1$, and $5| n-1$.
\hspace{.25in} Case $3$: $r=2$. If $n=5k+2$, then $n^2+1=25k^2+20k+4+1=5(5k^2+4k+1)$, and we see that $5 | n^2+1$.
\hspace{.25in} Case $4$: $r=3$. If $n=5k+3$, then $n^2+1=25k^2+30k+9+1=5(5k^2+6k+2)$, and $5|n^2+1$.
\hspace{.25in} Case $5$: $r=4$. If $n=5k+4$, then $n+1=5(k+1)$, and $5| n+1$.
Thus, $5\mid n^5-n$, as well. So, $2,3,$ and $5$ all divide $n^5-n$, and therefore, $30\mid n^5-n$ for all $n$.
\end{quote}
\vspace*{.2in}
\noindent {\bf Problem 10} The only prime one less than a cube is $7$.
\begin{quote}
\noindent{Proof:} We factor $n^3-1$ and get $n^3-1=(n-1)(n^2+n+1)$. If $n^3-1$ is to be prime, either $n-1$ or $n^2+n+1$ must be 1. So, we have two cases:
\hspace{.25in} Case $1$: If $n-1=1$, then $n=2$, and $n^3-1=8-1=7$.
\hspace{.25in} Case $2$: If $n^2+n+1=1$, then $n^2+n=n(n+1)=0$, and $n=0$ or $-1$.
This gives
$$n^3-1=0^3-1=-1$$
or
$$n^3-1=(-1)^3-1=-2\mbox{.}$$
Neither $-1$ or $-2$ are positive integers, and thus cannot be prime.
Thus, the only prime one less than a cube is $7$.
\end{quote}
\vspace*{.2in}
\noindent {\bf Problem 11} Find all primes such that $3p+1$ is a square.
\begin{quote}
If $3p+1$ is a square, then we can write $3p+1=(t+1)^2=t^2+2t+1$, and this implies that
$$3p=t^2+2t=t(t+2)\mbox{.}$$
Since $3$ and $p$ are both prime, $t$ and $t+2$ must both be prime, as well. (If they weren't, then $t(t+2)$ would have at least three prime factors, and either $3$ or $p$ would have to be composite, which we know is false.) In addition, $3$ must divide $t$ or $t+2$, which are both prime, so either $t=3$ or $t+2=3$.
If $t=3$, then $t+2=5$, so $p=5$.
If $t+2=3$, then $t=1$, so $p=1$. But, $1$ is not a prime.
So, the only prime such that $3p+1$ is a square is $5$.
\end{quote}
\vspace*{.2in}
\noindent {\bf Problem 12} Every positive integer of the form $4k+3$ has a prime factor of the same form.
\begin{quote}
\noindent{Proof:} Hold on to your hats, it's strong induction to the rescue!
{\it Basis Step:}
$k=0$. This gives $4\cdot 0+3=3$. Three is its own prime factor. So, the basis step holds.
{\it Inductive Step:}
We assume that for all $m 11$) greater than or equal to 4. Therefore, $n-9$ is composite, and $n$ has been written as the sum of two composite numbers.
\end{quote}
\vspace*{.2in}
\begin{quote}
\noindent{Proof B:} In order to find a contradiction suppose $n$ cannot be written as the sum of two composite numbers and that it is the first integer greater than 11 for which this is true.
\vspace*{.1in}
This implies:
\begin{center}
$n-1=p+q$ for composite $p$ and $q$
\end{center}
\begin{enumerate}
\item Consider $p+1$ and $q+1$: both must be prime.
To prove this, suppose not, and let $p+1$ be composite. This implies:
$$n=(p+1)+q$$
with both $p+1$ and $q$ composite, a contradiction of our hypothesis. Similarly, $q+1$ must also be prime.
\item Consider $p-1$ and $q+2$.
At least one of these numbers must be prime; otherwise, we can express $n$ as the sum of two composite numbers. But, because we know $q+1$ is prime, $q+2$ cannot also be prime. Therefore:
\begin{center}
$p-1$ is prime.
\end{center}
\item Now consider $p+3$ and $q-2$.
Again, at least one of these numbers must be prime. Since $q+1$ is prime, we know that $q-2$ cannot be, thus:
\begin{center}
$p+3$ is prime.
\end{center}
\vspace*{.1in}
We have now shown that the numbers $p-1$, $p+1$, and $p+3$ must all be prime. However, exactly one of these must be divisible by 3. Contradiction.
\end{enumerate}
\end{quote}
\vspace*{.1in}
\noindent{\bf Problem 18} A number of the form $2^{n-1}(2^n-1)$ is perfect if and only if $2^n-1$ is prime.
\begin{quote}
\noindent{Proof:} The divisors of a number of this form, not including itself, are
\begin{center}
$1,2,4,...,2^{n-1}$ and $1(2^n-1),2(2^n-1),4(2^n-1),...,2^{n-2}(2^n-1)$
\end{center}
We want to show that the sum of the divisors is equal to the number
$$\sum_{i=0}^{n-1} 2^i \, + \, \sum_{i=0}^{n-1} 2^i(2^n-1)
=2^{n-1}(2^n-1)$$
By induction we can show that
$$1+2+4+...+2^{n-1}=2^n-1$$
The base case is clear, so assume there exists $k$ such that
$$1+2+4+...+2^{k-1}=2^k-1$$.
It follows that
$$1+2+4+...+2^{k-1}+2^k=2^k-1+2^k$$
$$1+2+4+...+2^k=2\cdot2^k-1$$
Thus, $1+2+4+...+2^{n-1}=2^n-1$.
Therefore, the sum of divisors of our original number must be
$$(2^n-1)+(2^n-1)(2^{n-1}-1)$$
$$=(2^n-1)(1+2^{n-1}-1)$$
$$=2^{n-1}(2^n-1)$$
The converse is simple. If $2^n-1$ is not prime, then there are {\it more} divisors than those listed above and $2^{n-1}(2^n-1)$ is abundant.
\end{quote}
\vspace*{.1in}
\noindent{\bf Problem 19 } For every composite number $m$, $2^m-1$ is also composite.
\begin{quote}
\noindent{Proof:} Let $m=kn$ for integers $k>1$ and $n>1$. We want to show that there exists an integer $a$ such that
$$a(2^n-1)=2^{kn}-1$$
So,
$$a=\frac{(2^{n})^k-1}{2^n-1}$$
It is easy to see
$$(x^{k-1}+x^{k-2}+x^{k-3}+...+1)(x-1)=x^k-1$$
**Aside - You've seen this in calc 2; it's how you prove that a geometric series converges. Note: this is a factorization, if $x-1=1$, then $x=2$, therefore $n=1$.**
Thus, $x-1|x^k-1$. It immediately follows that $2^n-1|2^{kn}-1$.
\end{quote}
\noindent{\bf Definition} A prime of the form $2^n-1$ is called a {\em Mersenne prime}.
From the preceding theorem it follows that for $2^n-1$ to be prime, $n$ must be prime. Some examples of Mersenne primes and the perfect numbers they generate are:
$$
\begin{array}{rclcrcl}
2^2-1 & = & 3&\mbox{ \hspace*{1.25in}}&2\cdot3&=&6\\
2^3-1&=&7&\mbox{\hspace*{1.25in}}&2^2(2^3-1)&=&28\\
2^5-1&=&31&\mbox{\hspace*{1.25in}}&2^4(2^5-1)&=&496\\
2^7-1&=&127&\mbox{\hspace*{1.25in}}&2^6(2^7-1)&=&8128\\
2^{13}-1&=&8191&\mbox{\hspace*{1.25in}}&2^{12}(2^{13}-1)&=&33,550,336\\
\end{array}
$$
\vspace*{-.115in}
$$2^{127}-1=170141183460469231731687303715884105727\mbox{\hspace*{.25in}{\rm never\,\,mind}}$$
However, and this is why life is interesting, not all prime exponents produce Mersenne primes.
Some examples of prime values of $n$ that do not produce primes are:
$$2^{11}-1=2047=23 \cdot 89$$
$$2^{23}-1=8388607=47 \cdot 178481$$
$$2^{29}-1=233 \cdot 1103 \cdot 2089$$
How on earth does one tell whether $2^p-1$ is prime? It would be pretty tough to find that last factorization, not to mention to convince yourself that $2^{127}-1$ is prime. How do we know? Good questions, keep reading (or better still, go think about it for a while, then continue reading).
\vspace*{.35in}
\hspace*{1.95in} Day 5, September 18, notes scribed by {\it Rose Koch.}
\end{document}