\documentstyle[12pt,twoside,macpsfig,amssymb]{article}
\input{macros-course}

\begin{document}

\pset{1}{September 8, 1994}{Monday, September 12}

{\bf Reading:\ }Maurer \& Ralston: Section 0.7, Chapter 1 from 
{\it Introduction to the Theory of Numbers\/} by Niven and Zuckerman 
(Handout~\ref{nz}). 

{\bf Supplementary reading:\ }{\it The Nuts and Bolts of Proofs\/} by
Cupillari, available at The Coop.

\bigskip

This problem set is due in tutorial this Monday.  There will be a
handout listing tutorial assignments distributed in recitation on
Friday, September~9.  This handout, as all handouts, will be available
in the course locker on Athena as described in the Course Information
handout (Handout~\ref{course-information}).

\bigskip

Some of the problems ask you to ``verify or falsify'' a proof.  For these
problems, you must either justify the correctness of each step of the
proof, or else locate and explain the error.  It is not sufficient to
merely show that an incorrect proof is indeed wrong.  You must explain
where the bug is.

When you are asked for a proof, you may assume the facts on
Handout~\ref{symbols}, as well as any theorems proved in class.  Do
not assume facts that we have not proved, such as, for example, that
every rational number is representable by a fraction in lowest terms.

Read Handout~\ref{course-information} for the policy on problem sets.

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Verify or falsify the following proofs:

\begin{problemparts}
\problempart  If $a$ and $b$ are two equal real numbers, then $a=0$.

%						\begin{Proof}
\begin{eqnarray*}
a&=&b \\
a^2&=&ab \\
a^2-b^2&=&ab-b^2 \\
(a-b)(a+b)&=&(a-b)b \\
a+b&=&b \\
a&=&0 
\end{eqnarray*}
%						\end{Proof}

\newpage
\problempart There exist irrational numbers $a$ and $b$ such that
$a^b$ is rational.

%						\begin{Proof}
\begin{quotation}
Problem~\ref{irrat} proves that $\sqrt{2}$ is irrational.  Suppose
that $\paren{\sqrt{2}}^{\sqrt{2}}$ is rational.  Then, let
$a=\sqrt{2}$, let $b=\sqrt{2}$, and the proof is finished.  Suppose,
however, that $\paren{\sqrt{2}}^{\sqrt{2}}$ is irrational.  Then, let
$a=\paren{\sqrt{2}}^{\sqrt{2}}$ and let $b=\sqrt{2}$.  Thus, we have
$a^b=\paren{\sqrt{2}^{\sqrt{2}}}^{\sqrt{2}}=
\paren{\sqrt{2}}^{\sqrt{2}\cdot\sqrt{2}} = \paren{\sqrt{2}}^2 = 2$,
which is rational, and we're done.
\end{quotation}
%						\end{Proof}
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\remove{
	\problem
	Verify (!) or falsify the following proof that $-1=1$.
	\begin{eqnarray*}
	\sqrt{-1} & = & \sqrt{-1} \\
	\sqrt{1\over -1} & = & \sqrt{-1\over 1} \\
	\sqrt{1} \over \sqrt{-1} & = & \sqrt{-1} \over \sqrt{1} \\
	\sqrt{1} \sqrt{1} & = & \sqrt{-1} \sqrt{-1} \\
	1 & = & -1.
	\end{eqnarray*}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
Prove
\begin{eqnarray*}
\gcd (a,b) & = & \gcd (a+b,b) \\
& = & \gcd (a-b,b)
\end{eqnarray*} 
and
\begin{eqnarray*}
\gcd (a,b,c) & = & \gcd ( \gcd (a,b), c) \\
& = & \gcd ( \gcd (a,b), \gcd (b,c)). \\
\end{eqnarray*} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
Prove that if rational numbers $a/b$ and $c/d$ are in lowest terms,
then \\$a/b + c/d$ is not an integer unless $|b|=|d|$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem \label{irrat}
Prove that $\sqrt{p}$ is irrational for $p$ prime.\\
\hspace*{.3in}
(\hint Suppose that $\sqrt{p} = a/b \in \rationals$.  
Use the well-ordering principle on $b$ and obtain a contradiction.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
Prove that if $2^n-1$ is prime, then $n$ is prime.\\
\hspace*{.3in}
(\hint  Recall that $(x-1) \mid (x^k -1)$.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\remove{
	\problem
	Prove that $\gcd (a+b, a-b)$ is $1$ or $2$ if $\gcd (a,b)=1$.
}

\end{problems}

\end{document}


