\problemdata                                                             
        {fibonacci numbers} % latex-friendly label for the prob.
        {division rule} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 8, 5} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   

\newcommand{\lcm}{\mathop{\rm lcm}\nolimits}                                                                         
                                                                         
\begin{problem}           
Recall that $F_n$ denotes the $n$th Fibonacci number.

\begin{problemparts}

\problempart 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.

}

\problempart 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$.
}

\end{problemparts}

\end{problem}
                                 