\input{preamble}
\begin{document}

\begin{center}
  Fall 2021 -- Math 328K -- 55385
\end{center}
\section*{Homework 12}
\begin{center}
  \itshape no submission; the first four problems are about continued fractions, the others are a wild mix to practice some of the earlier topics; some of them are taken from old exams
\end{center}

\begin{problem}
  Express $\sqrt{28}$ as a continued fraction, and find the solution $(x,y) \in \bZ^2$ for the equation $x^2 - 28y^2 = 1$ with the least positive $y$ value.
\end{problem}

\begin{problem}
  Let $a_0,a_1, \dots$ and $b_0, b_1, \dots$ be sequences of integers, with $a_1,a_2,\dots,b_1,b_2,\dots$ positive. Assume that
  \[[a_0,a_1,\dots] = [b_0,b_1,\dots]\]
  and show that then $a_i = b_i$ for all $i$.
\end{problem}

\begin{problem}
  Let $a_0, a_1, \dots$ be a sequence of integers, with $a_1, a_2, \dots$ positive, and $\alpha = [a_0,a_1,a_2, \dots]$. Show that
  \[-\alpha = \begin{cases}[-a_0 - 1, 1, a_1-1, a_2, a_3, \dots] & \text{if $a_1 > 1$} \\ [-a_0-1,a_2+1, a_3, \dots] & \text{if $a_1 = 1$}.\end{cases}\]
\end{problem}

\begin{problem}
  Let $\alpha$ be an irrational number with continued fraction $[a_0,a_1, \dots]$ and $C_k = p_k/q_k$ it's $k$--th convergent ($p_k$ and $q_k$ coprime, $q_k > 0$).

  For each $k \geq 0$ and $0 \leq m \leq a_k$ define the \emph{semiconvergent}
  \[S_{k,m} = \frac{mp_k + p_{k-1}}{mq_k + q_{k-1}}.\]
  Note that $S_{k,0} = C_{k-1}$ and $S_{k,a_k} = C_{k+1}$. Show that if $k$ is odd and $0 \leq m < a_k$, then $S_{k,m} < S_{k,m+1}$.

  {\itshape Hint: a useful lemma might be that $\frac{a}{b} < \frac{a+c}{b+d} < \frac{c}{d}$ if $\frac{a}{b} < \frac{c}{d}$.}
\end{problem}

% \begin{problem}
%   Let $\alpha$ be an irrational number with continued fraction $[a_0,a_1, \dots]$, and $C_k = p_k/q_k$ it's $k$--th convergent ($p_k$ and $q_k$ coprime, $q_k > 0$).

%   Let $r,s$ be another pair of coprime integers, with $s > 0$, such that $\frac{r}{s}$ is a \emph{best lower approximation} of $\alpha$. That means that $\frac{r}{s} < \alpha$, and there is no fraction $\frac{r'}{s'}$ with $\frac{r}{s} < \frac{r'}{s'} < \alpha$ and $0 < s' < s$.

%   Further define for each $k \geq 0$ and $0 \leq m \leq a_k$ the \emph{semiconvergent}
%   \[S_{k,m} = \frac{m p_k + p_{k-1}}{m q_k + q_{k-1}}.\]
%   Note that $S_{k,0} = C_{k-1}$ and $S_{k,a_k} = C_{k+1}$.

%   Let $k$ be an odd positive integer and $m \in \{0,\dots,a_k-1\}$. Show that
%   \begin{enumerate}[a)]
%   \item $S_{k,m} < S_{k,m+1}$.

%     {\itshape Hint: a useful lemma might be that $\frac{a}{b} < \frac{a+c}{b+d} < \frac{c}{d}$ if $\frac{a}{b} < \frac{c}{d}$.}
%   \item \
%     \[S_{k,m+1} - S_{k,m} < \frac{1}{(q_k(m+1) + q_{k-1})(q_km + q_{k-1})}.\]
%   \item If $\frac{r}{s} > S_{k,m}$, then
%     \[\frac{r}{s} - S_{k,m} = \frac{x}{s(q_km + q_{k-1})}\]
%     for some positive integer $x$.
%   \end{enumerate}
% \end{problem}

% \begin{problem}
%   Assume that $C_1 < \frac{r}{s} < \alpha$. Show that $\frac{r}{s}$ is a semiconvergent of $\alpha$.

%   {\itshape Hint: Assuming that $S_{k,m} < \frac{r}{s} < S_{k,m+1}$, show using the previous problem that $S_{k,m+1}$ is a better approximation of $\alpha$ than $\frac{r}{s}$.}
% \end{problem}

\begin{problem}
  Let $n$ be a positive integer. Show that $(n^2 + 2, n^3 + 1)$ is either $1$ or $3$ or $9$.
\end{problem}

\begin{problem}
  Let $m,n \in \bZ_+$ be coprime and $a \in \bZ_+$. Show that if $a^m = b^n$ for some $b \in \bZ_+$ then $a = c^n$ for some $c \in \bZ_+$.
\end{problem}

\begin{problem}\
  \begin{enumerate}[a)]
  \item Find all solutions $x \in \bZ/15\bZ$ of the equation $108x = 9$.
  \item How many solutions $x$ does the equation $108x = 9$ have in $\bZ/15^k\bZ$, depending on $k \in \bN$?
  \end{enumerate}
\end{problem}

\begin{problem}
  An ancient Chinese problem asks for the least number of gold coins a band of 17 pirates could have stolen. The problem states that when the pirates divided the coins into equal piles, 3 coins were left over. When they fought over who should get the extra coins, one of the pirates was slain. When the remaining pirates divided the coins into equal piles, 10 coins were left over. The pirates faught again over who should get the extra coins, and another pirate was slain. When they divided the coins in equal piles again, no coins were left over. What is the answer to this problem?
\end{problem}

\begin{problem}
  A room contains 20000 light bulbs, numbered $1,2,3,\dots,20000$. All light bulbs are initially off. Now 20000 people enter the room, one after another, switch some of the bulbs on or off, and then leave. The first person toggles all the light bulbs (i.e. switches them on). The second person toggles (switches off) bulbs number $2,4,6,8,\dots$. The third person toggles bulbs number $3,6,9,12,\dots$. The fourth person toggles bulbs number $4,8,12,16,\dots$, and so on. How many light bulbs are on after all 20000 people went through the room?
\end{problem}

\begin{problem}\
  The goal of this is to find all $x \in \bZ/m\bZ$ with $x^2 = [1]$, for all $m \in \bZ_+$.
  \begin{enumerate}[a)]
  \item If $m$ is an odd prime, show that $x^2 = [1]$ has exactly two solutions $x \in \bZ/m\bZ$, which are $[1]$ and $[-1]$.
  \item If $m = p^k$ is a power of an odd prime $p$, show that $x^2 = [1]$ still has exactly two solutions $x \in \bZ/m\bZ$, which are $[1]$ and $[-1]$.
  \item Assume $m = 2^k$ for an integer $k \geq 3$. Show that $x^2 = [1]$ has exactly $4$ solutions in $\bZ/m\bZ$, which are
    \[[-1],\quad [1],\quad [2^{k-1} - 1],\quad [2^{k-1} + 1].\]
    {\itshape Hint: First show that these are solutions. Then you can use induction to show that there are no other solutions.}
  \item Now let $m \in \bZ_+$ be arbitrary and $m = 2^{i_0} p_1^{i_1} \cdots p_k^{i_k}$ its prime--power decomposition, with $p_1, \dots, p_k$ being pairwise different odd primes and $i_1, \dots, i_k \geq 1$.

    Show that $x^2 = [1]$ has $2^{k+e}$ solutions $x \in \bZ/m\bZ$, where
    \[e = \begin{cases}
        0 & \text{if $i_0 = 0$ or $1$,} \\
        1 & \text{if $i_0 = 2$,} \\
        2 & \text{if $i_0 \geq 3$.} \\
      \end{cases}\]
  \end{enumerate}
\end{problem}


\end{document}
