% Math 370 hw5 Spring 2014
%
\documentclass{article}
\pagestyle{empty}
\usepackage[textheight=10in, textwidth=7.5in]{geometry}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{verbatim}

%% create an environment for theorems
\newtheorem*{thm}{Theorem}

\newcommand{\coursehome}
{http://www.cs.umb.edu/~eb/370}

\title{History of Mathematics \\
Homework 5
}
\author{Ethan Bolker}

\begin{document}

\maketitle

The first question requires work before Tuesday. It's all due
on Thursday, March 13 .

\begin{enumerate}

\item Come prepared to discuss possible term paper topics.


\item Do Exercise 4.38 in the text.

% this will save lots of typing
\newcommand{\w}[1]{%
\omega^{#1}
}

The product
%
\begin{equation*}
P =
(1 + \w{2} + \w{4} + \w{5} + \w{6} + \w{10} + \w{11})
(1 + \omega + \w{5} + \w{6} + \w{7} + \w{9} + \w{11})
\end{equation*}
%
has $7 \times 7 = 49$ terms, which I will collect by powers of
$\omega$:

\begin{center}
\begin{tabular}{ccccccccccccccccccccccc}
0 & 1 & 2 & 3 & 4 &5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 &14 &15 &16 &17 & 18 &19 &20 &21 & 22 \\
\hline
1 &   & 1 &   & 1 & 1& 1 &   &   &   & 1  &  1 &    &    &   &   &   & &    &   &   &  &   \\
  & 1 &   & 1 &   &1 & 1 & 1 &   &   &    &  1 & 1  &    &   &   &   & &   &   &   &   \\
  &   &   &   &   &1 &   & 1 &   & 1 & 1  &  1 &    &    &   &1  &1  &  &    &   &   &   &    \\
  &   &   &   &   &  & 1 &   & 1 &   & 1  & 1  & 1  &    &   &   &1 &1  &    &   &   &   &    \\
  &   &   &   &   &  &   & 1 &   & 1 &    & 1  & 1  & 1  &   &   &  &1  & 1  &   &   &   &    \\
  &   &   &   &   &  &   &   &   & 1 &    & 1  &    & 1  &1  &1  &   &  &    &1  & 1 &   &    \\
  &   &   &   &   &  &   &   &   &   &    & 1  &    & 1  &   &1  &1 &1  &    &   &   & 1 &  1 \\
\hline
1 & 1 & 1 & 1 & 1 &3 & 3 & 3 & 1 & 3 & 3  &  7 &  3 &  3 &1  & 3 & 3 &3 & 1  &1  & 1 & 1 &  1 \\
\end{tabular}
\end{center}

Since the sums in the last line of that table are all odd, I can write
%
\begin{equation*}
P = (1 + \omega + \w{2} + \cdots + \w{22}) + 2 \times (\text{something}).
\end{equation*}
%
The first sum on the right is $0$ since $\omega$ is a
$23^{\text{th}}$ root of unity, so $P$ is divisible by 2.

This computation was easy, but I can't imagine how Kummer thought to
try it.

\item What is the etymology of the word ``cyclotomic''?

It's glued together from the Greek roots ``cyclo'' for ``circle'' and
``tom..'' for ``cut''. Most of you found and quoted a more thorough
answer.


\item The Euclidean Algorithm (which we will study in class Tuesday).

\begin{enumerate}

\item Find a solution in integers to the equation
%
\begin{equation*}
1001x + 512y = 1 .
\end{equation*}

I cheated. This is pasted from the screen at
\url{http://www.math.sc.edu/~sumner/numbertheory/euclidean/euclidean.html}
\begin{center}
\begin{verbatim}
 1001 = 512*1 + 489
 512 = 489*1 + 23
 489 = 23*21 + 6
 23 = 6*3 + 5
 6 = 5*1 + 1
 5 = 1*5 + 0

 1 = -174*512 + 89*1001
\end{verbatim}
\end{center}

The calculator at
\url{$http://www.mathcelebrity.com/euclidalgo.php?num1t=+1001&num2t=+512&pl=Euclids+Extended+Algorithm}
uses a version of the algorithm that finds the values of $x$ and $y$
along with the greatest common divisor, without having to work
backwards.

\item Where in Euclid will you find the Euclidean algorithm?
 Did Euclid invent/discover it?

According to wikipedia (usually a reliable source for mathematics)

\begin{quote}
 [The Euclidean algorithm] appears in Euclid's Elements (c. 300 BC),
 specifically in Book 7  (Propositions 1–2) and Book 10 (Propositions
 2–3).  

\ldots

The algorithm was probably not discovered by Euclid, who compiled
results from earlier mathematicians in his Elements. The
mathematician and historian B. L. van der Waerden suggests that Book
VII derives from a textbook on number theory written by mathematicians
in the school of Pythagoras. The algorithm was probably known by
Eudoxus of Cnidus (about 375 BC). The algorithm may even
pre-date Eudoxus, judging from the use of the technical term
[Greek here] (anthyphairesis, reciprocal subtraction) in works by
Euclid and Aristotle.
\end{quote}

\item  Show that after every two steps in the Euclidean algorithm, the
  remainder is reduced by at   least one half. 
Conclude that the Euclidean algorithm terminates in at most
$2\log_2(b)$ steps.
In particular, show that the number of steps is at most seven
times the number of digits in $b$.

Here's a proof from
\url{http://www.math.caltech.edu/~2010-11/1term/ma006a/Ma6a%20-euc-alg.pdf}.
Write $a_i$ for the remainder at the $i^{\text{th}}$ step. 

If $a_{i +1} \le a_i/2$, the claim certainly holds, since always
$a_{i+2} <a_{i+1}$. And if
$a_{i+1} > a_{i}/2$ then the remainder when we attempt to divide
$a_{i}$ by 
$a_{i+1}$ (it will only go in once) is
$a_{i+2} = a_i - a_{i+1} <a_{i}/2$.


\item Experiment with the Euclidean algorithm applied to find the
  greatest common divisor of consecutive Fibonacci numbers. Discover
  something cool.

I used the same web site as in an earlier problem to calculate the GCD
of 144 and 89:

\begin{verbatim}
 144 = 89*1 + 55
 89 = 55*1 + 34
 55 = 34*1 + 21
 34 = 21*1 + 13
 21 = 13*1 + 8
 13 = 8*1 + 5
 8 = 5*1 + 3
 5 = 3*1 + 2
 3 = 2*1 + 1
 2 = 1*2 + 0

 1 = -55*89 + 34*144
\end{verbatim}

I can see that the successive quotients are all the Fibonacci numbers
on the way to the two I started with. It's pretty easy to understand
why when you think about the way the Fibonacci numbers are
constructed:
%
\begin{equation*}
F_{n} = F_{n-1} + F_{n-2} \ .
\end{equation*}

\emph{Conscutive} Fibonacci numbers are
relatively prime: the 
greatest common divisor is 1. The linear combination is 
%
\begin{equation*}
F_{n-3}F_n - F_{n-2}F_{n-1} = \pm 1 \ ;
\end{equation*}
the sign depends on whether $n$ is even or odd.

All of you ignored the word ``consecutive'' in the problem. That led
you to discover something I never knew: the greatest common divisor of
any two Fibonacci numbers ia again a Fibonacci number. No one tried to
prove it.

\end{enumerate}


\end{enumerate}

\newpage

Here is the \LaTeX{} source for this document. You can cut it from the
pdf and use it to start your answers. I used the \verb!\jobname! macro
for the source file name, so you can call your file by any name you like.

\verbatiminput{\jobname}

\end{document}
