\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,ulem}
\usetikzlibrary{arrows,automata}
\usepackage[latin1]{inputenc}

\tikzstyle{vertex}=[circle,draw]

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math303}{Homework 11}{Due: Fri. Apr 12, 2023}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

\makeatletter
\def\@oddfoot{}
\makeatother

%\noindent
%\hfill Name: \underline{\hspace{3.5in}} 

%\begin{flushright}
%Name: \underline{\hspace{3.5in}} \\
%\end{flushright}
%\hrule

\def\columnseprule{0.4pt}

\newcommand{\PS}{\mathcal{P}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\st}{\colon \,}
\newcommand{\comp}[1]{\overline{#1}}
\renewcommand{\emptyset}{\varnothing}
\newtheorem{theorem}{Theorem}{}


\noindent
\textbf{Directions:} You may work to solve these problems in groups, but all written work must be your own.  Unless the problem indicates otherwise, all problems require some justification; a correct answer without supporting reasoning is not sufficient.  Submissions must be stapled.  See ``Guidelines and advice'' on the course webpage for more information.

\begin{enumerate}

\item Prove the following (using any method).
\begin{enumerate}
	\item There is a prime number between $90$ and $100$.
	\item If $a\in\ZZ$, then $a^3\equiv a\pmod{3}$.
	\item There exists a positive real number $x$ for which $x^2 < \sqrt{x}$.
	\item Suppose $a,b\in\ZZ$.  If $a+b$ is odd, then $a^2 + b^2$ is odd.
	\item There exist unique non-negative integers $x$ and $y$ such that $145408=x\cdot 2^y$ and $x$ is odd.
\end{enumerate}

\item Let $a,b,c,d\in\ZZ$ and suppose that $bc-ad = 1$.  Prove that $\gcd(an+b,cn+d)=1$ for each $n\in\ZZ$.  Hint: show that $bc-ad$ is an integer combination of $an+b$ and $cn+d$.  That is, find integers $x$ and $y$ such that $x(an+b) + y(cn+d) = bc-ad = 1$.  

\item Let $n$ be an integer such that $n\ge 3$, and suppose that $n$ lights are arranged in a circle.  Initially, all lights are off.  Each light is attached to a switch, but flipping a switch toggles the on/off status of its light and the two neighboring lights.  In terms of $n$, what is the minimum number of switch flips needed to turn all lights on?  Prove that your answer is correct.


\end{enumerate}
\end{document}
