\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amssymb,amsfonts,amsmath,amsthm} 
\usepackage[margin= 1in]{geometry}
\usepackage{url}

\usepackage{enumerate}
\usepackage{color}
\usepackage[pdftex]{graphicx}
\usepackage{lastpage}
\usepackage{mathptmx}

\newtheorem{thm}{THEOREM}[]
\newtheorem{lem}[thm]{LEMMA}
\newtheorem{cor}[thm]{COROLLARY}
\newtheorem{prop}[thm]{PROPOSITION}
\newtheorem{as}[thm]{ASSUMPTION}
\newtheorem{conjecture}[thm]{Conjecture}
\newtheorem{claim}[thm]{CLAIM}
\theoremstyle{definition}
\newtheorem{defi}[]{DEFINITION}
\theoremstyle{definition}
\newtheorem{remark}[thm]{REMARK}
\newtheorem{fact}[thm]{Fact}
\newtheorem{ex}[thm]{Example}

\setlength{\parindent}{0cm}

\newcommand{\tab}{\hspace{3ex}}
\newcommand{\R}{\mathbb{R}}

\usepackage{titlesec}
\usepackage{sectsty}
\hyphenchar\font=-1

\sectionfont{  \normalsize	\sectionrule{0pt}{0pt}{-5pt}{0.05pt}
	}

\titleformat*{\section}{ \Large  \center}
\titleformat{\subsection}[runin]
               {\normalfont\bfseries }
               {}{0em}{}[.]
               
\titlespacing{\section}
               {\parindent}{0pt}{5pt}
\titlespacing{\subsection}
               {0pt}{2ex plus .1ex minus .2ex}{5pt} 
               
               
               \makeatletter
 \renewcommand{\@evenfoot}{%
   Page \thepage{} of \pageref{VeryLastPage} \hfil
    
 }
 \renewcommand{\@oddfoot}{\@evenfoot}
 \makeatother

               
\begin{document}

\begin{center}
{\huge  \sc   Homework 4} \\
\smallskip
{ Due Date: 04/28/2022}\\
\smallskip
{Name:  }\\
{\large  }
\end{center}
\vspace{1cm}



\begin{enumerate}

\item[10.1] For each of the following pairs $a,b$ of integers, find the highest common factor $d=hcf(a,b)$, and find integers $s,t$ such that $d=sa+tb$.
\begin{enumerate}
\item $a=17, b=29$.
\item $a=552, b=713$.
\item $a=345, b=299$. 
\newpage


\end{enumerate}
\newpage
\item[10.2] Show that if $a,b$ are positive integers and $d=hcf(a,b)$, then there are positive integers $s,t$ such that $d=sa-tb$.\newline
Find such positive integers $s,t$ in each of the cases $(a),(b),(c)$ in Exercise 1
\newpage

\item[10.3] 


A train leaves Moscow for St.Petersburg every 7 hours, on the hour. Show that on some days it is possible to catch this train at 9:00 am.

Whenever there is a 9:00 am train, Ivan takes it to visit his aunt Olga. How often does Olga see her nephew?

Discuss the corresponding problem involving the train to Vladivostok which leaves Moscow every 14 hours. 
\newpage

\item[10.4] 

\begin{enumerate}
    \item Show that for all positive integers $n$, $hcf(6n+8,4n+5)=1$
    
    \item Suppose $a,b$ are integers such that $a\mid b$ and $b\mid a$. Prove that $a=\pm b$. 
    
    \item Suppose $s,t,a,b$ are integers such that $sa+tb=1$. Show that $hcf(a,b)=1$.
    
\end{enumerate}

\newpage

\item[10.10] After a particular exciting viewing of the new Danish thriller \textit{ Den heletal} Ivor Smallbrain repairs for refreshment to the prison's high security fast-food outlet O'Ducks. He decides that he'd like to eat some delicious Chicken O'Nuggets. These are sold in packs of two sizes- on containing 4 O'Nuggets, and the other containing 9 O'Nuggets.

Prove that for any integer $n>23$, it is possible for Ivor to buy $n$ O'Nuggets( assuming he has enough  money). 

\vspace{2cm}
Perversely, however, Ivor decides that he must buy exactly 23 O'Nuggets, no more and no less. Is he able to do this?

\vspace{2cm}
Generalize this question, replacing $4$ and $9$ by any pair $a,b$ of coprime positive integers: find an integer $N$(depending on $a$ and $b$), such that for any integer $n>N$ it is possible to find integers $s,t\geq 0$ satisfying $sa+tb=n$, but no such $s,t$ exist satisfying $sa+tb=N$. 

\newpage

\item[11.2]

\begin{enumerate}
    \item Which positive integers have exactly three positive divisors?
    
    
    \item Which positive integers have exactly four positive divisors?
\end{enumerate}

\newpage 


\item[11.3] Suppose $n\geq 2$ is an integer with property that whenever a prime $p$ divides $n$, $p^2$ also divides $n$. Prove that $n$ can be written as the product of a square and a cube. 

\newpage 
\item[11.5]
\begin{enumerate}
    \item Prove that $2^{\frac{1}{3}}$ and $3^{\frac{1}{3}}$ are irrational. 
    
    \item Let $m$ and $n$ be positive integers. Prove that $m^{\frac{1}{n}}$ is rational if and only if $m$ is an $n^{\text{th}}$ power. 
    
\end{enumerate}

\newpage 
\item[11.8]
\begin{enumerate}
    \item[(b)] Find all solutions $x,y\in \mathbb{Z}$ to the Diophantine equation:
    \[
    x^2-x=y^3
    \]
\end{enumerate}

\end{enumerate}




\label{VeryLastPage}
\end{document}