\documentclass[11pt,twoside]{article}
\usepackage{amsmath}

%\usepackage{psfig}

\input{macros-course}

\begin{document}

\tutn{15}{11/5/99}{November 6, 1999}

\begin{problems}

\problem Recall that $F_n$ denotes the $n$th Fibonacci number.

\bparts

\ppart Which Fibonacci numbers are even?  Prove it!

\solution{

Every third one is even, starting from $F_0 = 0$.  Prove this by proving
that $F_n$ is even iff $3 \mid n$ by strong induction on $n$.  The base
cases are that $F_0$ is even and $F_1$ is odd.  Now consider
\[
F_{n+1} \eqdef F_n + F_{n-1}.
\]
There are three cases, depending on what $n$ is congruent to modulo 3.

\emph{Case 0}: $n \equiv 0 \pmod 3$.  Then $n+1 \equiv 1 \not\equiv 0
\pmod 3$.  So we must prove that $F_{n+1}$ is odd.  Now $n - 1 \not\equiv 0
\pmod 3$, so by hypothesis, $F_n$ is even and $F_{n-1}$ is odd, so $F_{n+1}$
is odd as required.

\emph{Case 1}: $n \equiv 1 \pmod 3$.  Then $n+1 \equiv 2 \not\equiv 0
\pmod 3$.  So we must prove that $F_{n+1}$ is odd.  Now $n-1 \equiv 0 \pmod
3$, so by hypothesis, $F_n$ is odd and $F_{n-1}$ is even, so $F_{n+1}$ is
odd as required.

\emph{Case 2}: $n \equiv 2 \pmod 3$.  Then $n+1 \equiv 0 \pmod 3$.  So we
must prove that $F_{n+1}$ is even.  Now $n-1 \equiv 1 \pmod 3$, so by
hypothesis, $F_n$ is odd and $F_{n-1}$ is odd, so $F_{n+1}$ is even as
required.

}

\ppart The previous result is a special case for $m=3$ of the assertion
that $F_m \mid F_n$ iff $m \mid n$ for all $m,n \in \naturals, m > 0$.
Assuming this assertion for the time being, how many Fibonacci numbers
up to $F_{100}$ are \emph{not} multiples of 3 or 8 or 13?

\solution{

Every 4th number is multiple of $F_4 = 3$, every 6th number is multiple of
$F_6 =8$, and every 7th number is multiple of $F_7 = 13$.

Now, total = 100 (starting with $F_1$ and going to $F_{100}$)\\
mult of 3 = $\floor{100/4} = 25$,\\
mult of 8 = $\floor{100/6}= 16$,\\
mult of 13 = $\floor{100/7}=14$,\\
mult of 3 and 8 = $\floor{100/12}=8$, (since 12 is $\lcm(4,6)$),\\
mult of 3 and 13 = $\floor{100/28}=3$ (since 28 is $\lcm(4,7)$),\\
mult of 8 and 13 = $\floor{101/42}=2$, (since 42 is $\lcm(6,7)$),\\
mult of 3 and 8 and 13 = $\floor{101/84}=1$, (since 84 is $\lcm(4,6,7)$).

So the answer is $100 - 25 - 16 - 14 + 8 + 3 + 2 - 1 = 57$.
}

\ppart (Optional, in case you're curious.)  Prove that $F_m \mid F_n$ iff
$m \mid n$ for all $m,n \in \naturals, m > 0$.  \hint Prove that
\begin{eqnarray*}
\gcd(F_m,F_{m-1})& = & 1, \mbox{ and}\\
F_{m-1}F_n \pmod {F_m} & \equiv & F_{n+m}.
\end{eqnarray*}
  
\solution{

We first show that the two results suggested as hints imply the result to
be proved.

\begin{proof}

So suppose $\gcd(F_m,F_{m-1})=1$.  Then $F_{m-1}$ has an inverse $\bmod
F_m$, and so if $F_{m-1}a \equiv b \pmod {F_m}$, then either both $a$ and
$b$ are both congruent to 0 $\bmod {F_m}$, or neither is.

Now also suppose that $F_{m-1}F_n \equiv F_{n+m} \pmod {F_m}$.  Letting $a
= F_{n}$ and $b = F_{n+m}$, we conclude that
\[
F_n \equiv 0 \pmod {F_m}\mbox{  iff  } F_{n+m} \equiv 0 \pmod {F_m}.
\]
An obvious induction now implies
\[
F_{n} \equiv 0 \pmod {F_m} \mbox{  iff  } F_{n+km} \equiv 0 \pmod {F_m}
\]
for all $n,m,k \in \naturals$, $m>0$.  But any pair of natural numbers
that are congruent $(\mod m)$ can be written in the form $n$ and $n+km$
for some $n$ and $k$.  So the ``iff'' statement above can be rephrased as
\[
\mbox{if }n' \equiv n \pmod m,\mbox{ then }[F_{n} \equiv 0 \pmod {F_m} \mbox{ iff } F_{n'} \equiv 0
\pmod {F_m}].
\]

Now if $m \mid n$ then $n \equiv 0 \pmod m$, and since $F_0 = 0 \equiv 0
\pmod {F_m}$, we can conclude that $F_n \equiv 0 \pmod {F_m}$.

Conversely, if $\neg[m \mid n]$, then $n \equiv k \pmod m$ for some $k$
where $0 < k < m$.  But $F_k \not\equiv 0 \pmod {F_m}$ when $0 < k < m$
because except for $F_0$, all Fibonacci numbers are positive, and $k<m$
implies $F_k < F_m$.  So the ``iff'' statement implies that $F_n
\not\equiv 0 \pmod {F_m}$ also.

\end{proof}

It remains to prove the two results in the hint.

Now we know that $\gcd(a, b) = \gcd(a-b,b)$, so in particular
\[
\gcd(F_m,F_{m-1}) = \gcd(F_m-F_{m-1}, F_{m-1}) = \gcd(F_{m-2},F_{m-1}) =
\gcd(F_{m-1},F_{m-2})
\]
for all $m \geq 2$.  But this implies $\gcd(F_m,F_{m-1}) =
\gcd(F_{1},F_{0}) = 1$ by trivial induction on $m$.

Finally, we prove that $F_{m-1}F_n \equiv F_{n+m} \pmod {F_m}$ by
induction on $n$.  The base case $n=0$ is
\[
F_{m-1}F_0  \equiv F_{m} \pmod {F_m},
\]
which is immediate since $F_0 = 0 \equiv F_m \pmod {F_m}$.  The induction
case is also routine, and is left to the reader.

}

\eparts


\end{problems}

\end{document}

