\documentclass{article}
\usepackage{amsmath, amssymb,verbatim, amsthm, graphicx}

%exercise environment
\newcounter{exercise}
\setcounter{exercise}{0}
\newenvironment{exercise}{\addtocounter{exercise}{1} \noindent{\bf{Exercise \theexercise.}}}{\vspace{.5cm}}

\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\C}{\mathbb{C}}

\textwidth 6.5in
\textheight 9in
\oddsidemargin 0in
\evensidemargin 0in
\headsep -0.5in

\setlength{\parskip}{0.25cm}

\pagenumbering{gobble}

\begin{document}

\begin{center}
\includegraphics[width=0.5in]{../ltr-logo.jpg}
\end{center}

\noindent{\Large{\textsc{Number Theory \hfill Assignment 2.3  \\ Fall 2023 \hfill Due September 6}}}

\large

\vspace{1cm}


\begin{exercise}
Let $\{ f_n \}$ denote the Fibonacci sequence, as defined in Exercise 2.2.2.  Let $\beta < \alpha$ denote the roots of the polynomial $x^2-x-1$.  Use strong induction to prove that
\[
f_n = \frac{1}{\sqrt{5}} \left( \alpha^n - \beta^n \right)
\] 
for all $n \ge 0$.  [{\em Suggestion.}  Except in the base cases, {\em do not} use the expressions for $\alpha$ and $\beta$ that come from the quadratic formula.  Instead, notice that since $\alpha^2 - \alpha - 1 = 0$, we have $\alpha^2 = \alpha+1$, and likewise for $\beta$.]
\end{exercise}

\begin{exercise}
If $a,b,n \in \N$, use the strong form of B{\'e}zout's lemma to prove that $(a,b)=1$ if and only if $(a^n, b^n)=1$.  [{\em Suggestion.}  For the forward implication, write $ra+sb=1$ and expand $(ra+sb)^{2n}$ using the Binomial Theorem.  The converse is trivial.]
\end{exercise}

\begin{exercise}
Textbook exercise 2.3.20, parts (a)-(e).
\end{exercise}

\begin{exercise}
Textbook exercise 2.4.4.
\end{exercise}

\end{document}
