\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{amsfonts}
\usepackage{amsmath, amsthm, amssymb}
\usepackage{enumitem}
%\pagestyle{headings}

\usepackage{mathtools}

\newcommand{\0}{\mathbf 0}
\newcommand{\C}{{\mathbb C}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\diag}{\textrm{diag}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\normal}{\trianglelefteq}
\newcommand{\bmid}{\,\Big|\,}
\newcommand{\ds}{\displaystyle}

\DeclareMathOperator{\GCD}{GCD}

\begin{document}

\thispagestyle{empty}

\begin{flushright}
  Your Name Goes Here
\end{flushright}


\begin{center}
  \textbf{Math 25}\\ Homework 2
\end{center}

\begin{enumerate}
\item Find all integer solutions to $11305x + 455y = 105.$

\item Find all integer solutions to $15x +35y +21z = 1$.  Hint: Your
  answer should have two free parameters.


\item The Fibonacci numbers are a sequence of recursively defined
  integers $F_0, F_1, F_2, \dots$ where $F_0 = 0$, $F_1 = 1$ and
  $F_{n+2} = F_{n+1} + F_n$ for all $n \ge 0$.  A few values of $F_n$:

  \begin{center}
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|}
      \hline  $n$&0  &1  &2  &3  &4  &5  &6  &7  &8  &9  &10  \\ 
      \hline  $F_n$&0  &1  &1  &2  &3  &5  &8  &13  &21  &34  &55  \\ 
      \hline 
    \end{tabular} 
  \end{center}
  Their occurrence in nature is uncanny, from models of uncontrolled
  population growth, to phyllotaxis, to number of seeds in spirals of
  sunflowers.

  \begin{enumerate}
  \item For $n \ge 0$, show that $\gcd(F_{n+1},F_n) = 1$.
  \item Show that for $n \ge 2$, the Euclidean algorithm takes exactly
    $n$ steps to compute $\gcd(F_{n+2}, F_{n+1})$
  \item Consider a \textbf{generating function} for the Fibonacci
    numbers:
    \[G(x) = \sum_{n=0}^\infty F_n x^n = x + x^2 + F_3x^3 + F_4x^4 +
      F_5x^5+ \cdots.
    \]
    Show that
    \[G(x) = \frac{x}{1-x-x^2}.
    \]
    Hint: Compute $G(x) - xG(x) - x^2G(x)$.
  \item Exploration (\textbf{not required}).  Show that for $n \ge 0$,
    $\ds F_n = \frac1{\sqrt5}\left(\alpha^n - \beta^n\right)$, where
    \[\alpha = \frac{1+\sqrt 5}{2}, \mbox{ and } \beta = \frac{1-\sqrt
        5}{2}.\] \textit{Hint:} Start by using partial fractions to
    express
    \[G(x) = \frac{x}{1-x-x^2} = \frac{-x}{x^2 +x -1} =
      \frac{A}{x-\alpha_0} + \frac{B}{x-\beta_0}.
    \]

  \end{enumerate}



\item Let $a,b$ be positive integers, and suppose that
  $\gcd(a,b) = 1$.  We want to investigate \textbf{non-negative}
  integer solutions to $ax + by = c$, that is, solutions with both
  $x,y \ge 0$.  Even though $\gcd(a,b) =1$, there is no guarantee of
  any non-negative solutions, especially when $c$ is small relative to
  $a,b$.

  \begin{enumerate}
  \item Show that for $c = ab$, the only non-negative solutions are
    $(0,a)$ and $(b,0)$.
  \item Now let $c > ab$.  Show that there is always a non-negative
    solution to $ax + by = c$.
  \end{enumerate}

\item Prove that there are infinitely many primes of the form $6m + 5$
  for $m$ a non-negative integer.

\item Let $m,n$ be relatively prime positive integers.

  \begin{enumerate}
  \item Prove that if an integer $m>1$ factors as
    $m = p_1^{e_1}\cdots p_r^{e_r}$ and $d \mid m$, then $d$ can be
    written as $d = p_1^{a_1} \cdots p_r^{a_r}$ where
    $0 \le a_i \le e_i$ for $1 \le i \le r$.


  \item Show that every divisor $d \mid mn$ can be written uniquely as
    $d = d_md_n$ where $d_m \mid m$ and $d_n \mid n$.

  \item Use the above to show that if $n\ge 2$ is an integer with
    prime factorization $n = p_1^{e_1}\cdots p_r^{e_r}$, then every
    divisor $d \mid n$ can be written uniquely as
    $d = p_1^{a_1} \cdots p_r^{a_r}$ where $0 \le a_i \le e_i$ for
    $i = 1, \dots, r$.
  \end{enumerate}





\end{enumerate}


\end{document}


%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
