\documentclass[12pt]{article} % % Doug Nychka's LaTeX template (8/13/2004). To create a pdf file from this %use pdflatex % % if you read one more comment read the one that starts with *********** % % %See folder texpower for more GREAT EXAMPLES %LIKE THIS. \nofiles % Suppress all those pesky files! \include{defs2} % include some color support (see examples below) \usepackage[usenames,dvipsnames]{color} %Include the texpower packages to allow for pause \usepackage[display]{texpower} \usepackage{ fancyvrb,listings,alltt} %\usepackage{pdfslide} \newcommand{\tabend}{\\\hline} % % set background color \definecolor{Pcolor}{rgb}{.971,.951,.92} % A cool manila \pagecolor{Pcolor} % see the Tex files associated with dvipsnames % for some predefined colors. % % this little style file allows you to % step through a page adding items % %\usepackage{pause} % % include a graphics package for importing figures % \usepackage{graphicx} % % \RequirePackage[pdftex,pdfpagemode=none, pdftoolbar=true, pdffitwindow=true,pdfcenterwindow=true]{hyperref} % % change these to suit! Margins assume an inch as default % \setlength{\paperheight}{7in} \setlength{\paperwidth}{9in} \setlength{\textheight}{6.75in} \setlength{\textwidth}{7.5in} \setlength{\evensidemargin}{-.75in} \setlength{\oddsidemargin}{-.75in} \setlength{\topmargin}{-.75in} \setlength{\parskip}{.125in} \setlength{\parindent}{0in} % % % set background color \definecolor{Pcolor}{rgb}{.971,.951,.92} % A rosy manila \pagecolor{Pcolor} % Define heading color. \definecolor{Hcolor}{rgb}{.0,.0,.99} % my heading color % % these are my basic page headings % note how the color is set % \def\mytitle#1{{\color{Hcolor}{\it \LARGE #1}\\ }} \def\MYTITLE#1{{\bf\color{Hcolor}{\huge #1}\\ \rule[.15in]{\textwidth}{.03in} }} \def\myTITLE#1{{\color{Hcolor}{\huge #1}\\}} % just to make the math work, everyone does this differently ... \newcommand{\BLD}[1]{\mbox{\boldmath $#1$}} % low tech way to start a new "slide" and add a background image % This has been tuned to the aspect paper sizes declared above. \newcommand{\BS}{ \newpage \vspace*{-1.06in} \hspace*{-.32in} \includegraphics[height=\paperheight, width=\paperwidth]{/home/dwick/DATA/Professional/Other/Pictures&Worksheets/17a.jpg} % Some rock face in Boulder Canyon. Time-For-Lunch-2.jpg \vspace*{-\paperheight} \vspace*{.5in} \hspace*{-\paperwidth} } % uncomment this version for just a new page and no background image. % note that you still get a background color from setting \pagecolor above %\newcommand{\BS}{ \newpage} \begin{document} %%%%%%%%%%% {\color{Black} %begin default text color {\LARGE % fault is LARGE size font { \sf % default face is sans serif %%%%%%%%%%%% \BS \MYTITLE{ Perfectly Amicable} \cl {Darren Wick} \cl {Ashland University} \cl {March 31, 2006 } %%%%%%%%%%%% \BS \MYTITLE {Perfect Numbers} \begin{itemize} \item A positive integer $n$ is {\it perfect} if it is the sum of its proper divisors \noi \item Denote the sum of the proper divisors of $n$ by $\sigma (n)$. Then $n$ is perfect iff $\sigma (n)=n$ \noi \item $\sigma (8) =1+2+4=7$ \noi \item $\sigma (6)=1+2+3=6$ \noi \item If $p$ is prime then $\sigma(p)=1$ \end{itemize} \BS \MYTITLE{Euclid's Algorithm} \begin{itemize} \item Book IX, Proposition 36 of {\it The Elements} \noi \item {\it If as many numbers as we please beginning from a unit be set out continuously in double proportion until the sum of all becomes prime, and if the sum multiplied into the last make some number, then the product will be perfect} \noi \item Translation: If $2^k -1 $ is prime, then $2^{k-1}(2^k-1)$ is perfect. \noi \item Generates the first four perfect numbers known in ancient times: 6, 28, 496, 8128 \end{itemize} \BS \begin{center} \addtolength{\tabcolsep}{1mm} \renewcommand{\arraystretch}{1.2} \begin{tabular}{|c|c|c|c|} \hline \hline $k$ & $2^k-1$ & $2^{k-1}$ & $2^{k-1}(2^k-1)$ \\ \hline \hline 1&1&& \\ \hline 2&3&2&6 \\ \hline 3&7&4&28\\ \hline 4&15&&\\ \hline 5&31&16&496\\ \hline 6&63&&\\ \hline 7&127&64&8128\\ $\cdots$ &$\cdots$ &$\cdots$ &$\cdots$ \\ \hline\hline \end{tabular} \end{center} \BS \MYTITLE{Proof of Euclid's Algorithm} \noi \vspace{-.67in} Let $p=2^k-1$ be prime. \noi Then $N=2^{k-1}p$ has divisors \noi $$1,2,2^2,\ldots ,2^{k-1} \ {\rm and} \ p,2p,2^2p,\ldots , 2^{k-2}p,2^{k-1}p$$ \noi Thus $$\sigma (N)=(1+2+\ldots+2^{k-1}) +(p+2p+2^2p+\ldots 2^{k-2}p)$$ \noi \vspace{-.6in} $$=(2^k-1)+p(2^{k-1}-1)$$ \noi \vspace{-.6in} $$=(2^k-1)+(2^k-1)(2^{k-1}-1)$$ \noi \vspace{-.6in} $$=(2^k-1)(1+(2^{k-1}-1))$$ \noi \vspace{-.6in} $$=2^{k-1}(2^k-1)=N$$ \BS \MYTITLE {Nicomachus Conjectures ($\sim$ 100 A.D.)} \cl { 6, 28, 496, 8128} \begin{itemize} \item The $n^{th}$ perfect number has $n$ digits \noi \item Perfect numbers end in 6 and 8 alternately \noi \item All perfect numbers are even \noi \item Euclid's algorithm gives all perfect numbers \noi \item There are infinitely many perfect numbers \end{itemize} \BS \begin{center} \addtolength{\tabcolsep}{1mm} \renewcommand{\arraystretch}{1.2} \begin{tabular}{|c|c|c|c|c|} \hline \hline $k$ & $2^k-1$ & $2^{k-1}$ & Perfect Number & Discoverer\\ \hline \hline 13&8191&4096&33,550,336 &Regius (1536)\\ \hline $\cdots$ &$\cdots$ &$\cdots$ &$\cdots$ &$\cdots$\\ 17&$2^{17}-1$&$2^{16}$&8,589,869,056 & Cataldi (1603)\\ \hline $\cdots$ &$\cdots$ &$\cdots$ &$\cdots$&$\cdots$ \\ 19&$2^{19}-1$&$2^{18}$&137,438,691,328&Cataldi\\ \hline $\cdots$ &$\cdots$ &$\cdots$ &$\cdots$ &$\cdots$\\ 31&$2^{31}-1$&$2^{30}$&19 digits & Euler\\ \hline\hline \end{tabular} \end{center} \BS \MYTITLE{Nicomachus Conjectures} \cl {6, 28, 496, 8128, 33550336, 8589869056} \begin{itemize} \item That the $n^{th}$ perfect number has $n$ digits is false \noi \item That perfect numbers end in 6 and 8 alternately is false \end{itemize} \BS \MYTITLE{Nicomachus Conjectures} Nicomachus other 3 conjectures are still unresolved \begin{itemize} \item All perfect numbers are even \noi Euler showed that if an odd perfect number did exist, it would be of the form $$b^2(4n+1)^{4k+1}$$ with $4n+1$ prime \noi \item Euclid's algorithm gives all perfect numbers \noi Euler showed that any even perfect number is a consequence of Euclid's algorithm. \noi \item There are infinitely many perfect numbers \end{itemize} \BS \MYTITLE{Question} \begin{itemize} \item The fifth perfect number, $2^{12}(2^{13}-1)$, was apparently not known to Euclid. \noi \item It is found by determining that $2^{13}-1=8191$ is prime \noi \item Why didn't Euclid know this? \end{itemize} \BS \MYTITLE{Current Status} \begin{itemize} \item There are currently 43 known Mersenne primes $2^p-1$, and hence 43 known perfect numbers \noi \item The number of known Mersenne primes, 43, is prime \\ \noi \vspace{-.3in} \cl{ but not a Mersenne prime} \noi \item The largest known Mersenne prime is $$2^{30,402,457}-1$$ \noi \item The corresponding $43^{rd}$ perfect number has $18,304,103$ digits \end{itemize} \BS \MYTITLE{Amicable Numbers} \begin{itemize} \item Two positive integers $n$ and $m$ are {\it amicable} if $\sigma(n)=m$ and $\sigma(m)=n$ \noi \item The smallest pair of amicable numbers is $220$ and $284$, known to and revered by the Pythagoreans \noi \item $220=2^2\times 5\times 11$ and $284=2^2\times 71$ \noi \item $\sigma (220)=1+2+4+5+10+11+20+22+44+55+110=284$ \noi \item $\sigma (284)=1+2+4+71+142=220$ \end{itemize} \BS \MYTITLE{Thabit ibn Qurra's Algorithm ($\sim$ 800 A.D.)} \noi Theorem: Define $$p_{k}=3\cdot2^{k}-1$$ $$q_k= 9\cdot2^{2k-1}-1$$ \noi Then if $p_{k-1}, p_k, $ and $q_k$ are all prime, \noi $$ 2^kp_{k-1}p_k \ \ \ {\rm and} \ \ \ 2^k q_k \ \ \ {\rm are \ amicable} $$ \BS \begin{center} \addtolength{\tabcolsep}{1mm} \renewcommand{\arraystretch}{1.2} \begin{tabular}{|c|c|c|c|} \hline \hline $k$ & $3\cdot 2^k-1$ & $9\cdot 2^{2k-1}-1$ & Amicable Pair \\ \hline \hline 1& 5&17& \\ \hline 2&11&71& 220,\ 284 \\ \hline 3&23&287&\\ \hline 4&47&1151&17296, \ 18416\\ \hline 5&95&4607&\\ \hline 6&191&18431&\\ \hline 7&383&73727&9363584, \ 9437056\\ $\cdots$ &$\cdots$ &$\cdots$ &$\cdots$ \\ & &&\\ $\cdots$ &$\cdots$ &$\cdots$ &$\cdots$ \\ \hline\hline \end{tabular} \end{center} \BS \MYTITLE{ibn Qurra's Algorithm} \begin{itemize} \item Only 3 amicable pairs have been generated using ibn Qurra's algorithm \noi \item Euler later generalized ibn Qurra's algorithm \end{itemize} \BS \MYTITLE{Euler's Algorithm} \noi If the following are all prime for some $1\leq m \leq n-1$ \noi $$p=2^m(2^{n-m}+1)-1$$ $$q=2^n(2^{n-m}+1)-1$$ $$r=2^{n+m}(2^{n-m}+1)^2-1$$ \noi Then $$2^npq \ \ \ {\rm and } \ \ \ 2^n r \ \ \ {\rm are \ amicable}$$ \BS \MYTITLE{Euler's Algorithm} ibn Qurra's algorithm is a special case of Euler's algorithm with $m=n-1$. \noi \begin{center} \addtolength{\tabcolsep}{1mm} \renewcommand{\arraystretch}{1.2} \begin{tabular}{|c|c|c|c|c|} \hline \hline $(m,n)$ & $p$ & $q$ & $r$ & Amicable Pair \\ \hline \hline (1,2) & 5 & 11 & 71 & 220 , \ 284 \\ \hline (3,4)& 23 & 47 & 1151 & 17296, \ 18416 \\ \hline (6,7) & 191 & 383 & 73727 & 9363584 , \ 9437056\\ \hline $\cdots$&$\cdots$&$\cdots$&$\cdots$&$\cdots$ \\ \hline $\cdots$&$\cdots$&$\cdots$&$\cdots$&$\cdots$ \\ \hline\hline \end{tabular} \end{center} \BS \MYTITLE{Euler's Algorithm} \begin{center} \begin{tabular}{|c|c|c|c|c|} \hline \hline $(m,n)$ & $p$ & $q$ & $r$ & Amicable Pair \\ \hline \hline (1,2) & 5 & 11 & 71 & 220 , \ 284 \\ \hline (3,4)& 23 & 47 & 1151 & 17296, \ 18416 \\ \hline (6,7) & 191 & 383 & 73727 & 9363584 , \ 9437056\\ \hline (1,8) &257&33023&8520191&2172649216, \ 2181168896\\ \hline (29,40)&big&big&big& huge, \ huge\\ \hline\hline \end{tabular} \end{center} \noi No others known for $n<2500$ \BS \MYTITLE{Euler's Algorithm} Euler extended his algorithm even further to show \noi If $p,q,r$ are any primes with \noi \begin{enumerate} \item $r=pq+p+q$ \noi \item $2^n (p+q+r)=r+1$ \noi \end{enumerate} Then $2^n pq$ and $2^n r$ are amicable. \noi He gave no additional amicable pairs of this form \BS \MYTITLE{Euler's Algorithm} Euler gave 30 new pairs of amicable numbers in a paper of 1747 \noi Including the third and fourth smallest pairs \noi $$2620=2^2\cdot 5\cdot 131 \ \ \ {\rm and}\ \ \ 2924=2^2\cdot17\cdot43$$ \noi $$5020=2^2\cdot 5\cdot 251 \ \ \ {\rm and}\ \ \ 5564=2^2\cdot13\cdot107$$ \noi In 1866, an Italian teenager found the second smallest pair $$1184=2^5\cdot 37 \ \ \ {\rm and} \ \ \ 1210=2\cdot5\cdot11^2$$ \BS \MYTITLE{Currrent Status} \noi There are 1427 known amicable pairs less than $10^{10}$ \BS \BS \MYTITLE{References} \begin{enumerate} \item Euler, {\it " On Amicable Numbers"}, Nova Acta Eruditorum, 1747 \item Eves, {\it "An Introduction to the History of Mathematics"} \item Katz, {\it "A History of Mathematics, an Introduction"} \item Sandifer, {\it "How Euler Did It"}, MAA Online, Nov. 05 \item www-history.mcs.st-and.ac.uk (Mactutor) \item www.mathworld.wolfram.com \item amicable.adsl.dk \end{enumerate} \BS Proof of ibn Qurra's algorithm: Assuming that $q_k$ is prime, the divisors of $b=2^k q_k$ are $$1,2,2^2,\ldots ,2^{k}$$ $$q_k,2q_k,2^2q_k,\ldots , 2^{k-1}q_k,2^{k}q_k$$ Thus $$\sigma (2^kq_k)=(1+2+\ldots+2^{k})$$ $$+(q_k+2q_k+2^2q_k+\ldots 2^{k-1}q_k)$$ $$=(2^{k+1}-1)+q_k(2^{k}-1)$$ $$=(2^{k+1}-1)+(9\cdot2^{2k-1}-1)(2^{k}-1)$$ $$=2^k-1+9\cdot 2^{3k-1}-2^k-9\cdot 2^{2k-1}+1$$ $$=2^{k+1}-2^k+9(2^{3k-1}-2^{2k-1})$$ \BS On the other hand, $$a=2^kp_{k-1}p_k=2^k(3\cdot2^{k-1}-1)(3\cdot2^k-1)$$ $$=2^k (9\cdot 2^{2k-1}-3\cdot 2^k-3\cdot 2^{k-1}+1)$$ $$=9\cdot 2^{3k-1}-3\cdot2^{2k}-3\cdot2^{2k-1}+2^k$$ $$=9\cdot 2^{3k-1}-3(2^{2k}+2^{2k+1})+2^k$$ $$=9\cdot 2^{3k-1}-3\cdot2^{2k-1}(2+1)+2^k$$ $$=9\cdot2^{2k-1}-9\cdot2^{2k-1}+2^k$$ Thus we have that $$\sigma(b)=a$$ \BS Assuming that $p_{k-1}$ and $p_k$ are prime, the divisors of $a=2^kp_{k-1}p_k$ are $$1,2,2^2,\ldots ,2^{k}$$ $$p_{k-1},2p_{k-1},\ldots , 2^{k}p_{k-1}$$ $$p_{k},2p_{k},\ldots , 2^{k}p_{k}$$ $$p_{k-1}p_k,2p_{k-1}p_k,\ldots , 2^{k}p_{k-1}p_k$$ Thus we have that $$\sigma (a)=1+2+2^2+\ldots +2^{k}$$ $$+p_{k-1}(1+2+2^2+\ldots +2^{k})$$ $$+p_{k}(1+2+2^2+\ldots +2^{k})$$ $$+p_{k-1}p_k(1+2+2^2+\ldots +2^{k-1})$$ \BS $$=(2^{k+1}-1)+p_{k-1}(2^{k+1}-1)+p_k(2^{k+1}-1)+p_{k-1}p_k(2^{k}-1)$$ $$=(2^{k+1}-1)+p_{k-1}(2^{k+1}-1)+p_k(2^{k+1}-1)+p_{k-1}p_k(2^{k+1}-1)$$ $$-p_{k-1}p_k2^k$$ $$=(2^{k+1}-1)(1+p_{k-1}+p_k+p_kp_{k-1})-2^kp_kp_{k-1}$$ $$=(2^{k+1}-1)(1+p_{k-1})(1+p_k)-2^k(9\cdot 2^{2k-1}-3\cdot2^{k-1}-3\cdot 2^k+1)$$ $$=(2^{k+1}-1)(3\cdot2^{k-1})(3\cdot 2^k)-2^k(9\cdot 2^{2k-1}-3\cdot2^{k-1}-3\cdot 2^k+1)$$ $$=2^k\big[ 9\cdot 2^{2k}-9\cdot2^{k-1}-9\cdot 2^{2k-1}+3\cdot2^{k-1}+3\cdot 2^k-1 \big]$$ $$=2^k\big[ (9\cdot 2^{2k}-9\cdot 2^{2k-1})-6\cdot 2^{k-1}+3\cdot2\cdot2^{k-1}-1\big]$$ $$=2^k \big[ 9\cdot 2^{k-1} -1 \big] =2^kq_k=b$$ \end{document}