\documentstyle[12pt,twoside,macpsfig,amssymb]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\psol{1}{September 20, 1994}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
\begin{problemparts}
\problempart 
This proof is false.  In the step
\begin{eqnarray*}
(a-b)(a+b)&=&(a-b)b \\
a+b&=&b 
\end{eqnarray*}
we cancel by $(a-b) =0$.  The cancellation law allows the cancellation only of
nonzero factors.  (That is, ``division by 0 is not valid''.)

\problempart
This proof is valid.  $\paren{\sqrt{2}}^{\sqrt{2}}$ is a real number, so
it must be either rational or irrational.  We analyze both cases.

\begin{itemize}
\item {\bf Case 1:} $\paren{\sqrt{2}}^{\sqrt{2}}$ is rational.

Let $a=\sqrt{2}$ and $b=\sqrt{2}$.  $a,b$ are both irrational
by Problem 1-4.  By case hypothesis, $a^b$ is rational.

\item {\bf Case 2:} $\paren{\sqrt{2}}^{\sqrt{2}}$ is irrational.

Let $a=\paren{\sqrt{2}}^{\sqrt{2}}$ and $b=\sqrt{2}$.  
$a$ is irrational by case hypothesis, and $b$ is irrational
by Problem 1-4.

\[
\begin{array}{llll}
a^b & = & \paren{\sqrt{2}^{\sqrt{2}}}^{\sqrt{2}} & \mbox{(substitution)} \\
&=& \paren{\sqrt{2}}^{\sqrt{2}\sqrt{2}} & \mbox{(laws of exponents)} \\
&=& \paren{\sqrt{2}}^2 & \mbox{(algebra)} \\
&=& 2 & \mbox{(definition of square root)} 
\end{array}
\]

2 is rational, so $a^b$ is rational.  
\end{itemize}
We have covered all cases, so the proof is valid, even though we don't 
know whether $\paren{\sqrt{2}}^{\sqrt{2}}$ is rational or not!
\end{problemparts}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Prove that 
$\gcd (a,b) = \gcd (a+b,b) = \gcd (a-b,b)$ \\
and
$\gcd (a,b,c) = \gcd ( \gcd (a,b), c) = \gcd (\gcd (a,b), \gcd (b,c)).$

\remove{
  \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*} 
}

\begin{proof} There are four equalities to be proven.
\begin{enumerate} 	\setlength{\labelsep}{.15in}
\item	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
$\gcd(a,b)=\gcd(a+b,b)$:\\
We will show that each divides the other.
This will imply that $\gcd(a,b)= \pm \gcd(a+b,b)$.  
Moreover, they must in fact be equal since the $\gcd$ is positive by 
definition, 
(We will use this same technique in each proof.)

Proof that $\gcd(a,b)\divides \gcd(a+b,b)$:
\begin{quotation}
By definition, $\gcd(a,b)\divides a$ and $\gcd(a,b)\divides b$.  
It follows that $\gcd(a,b)\divides (a+b)$ 
(by a theorem from lecture---if $a=md$ and $b=nd$, then $a+b=(n+m)d$).
Since $\gcd(a,b)$ divides both $(a+b)$ and $b$, 
we know it divides their gcd (another theorem from lecture, stated as
a corollary there).
\end{quotation}

Proof that $\gcd(a+b,b)\divides \gcd(a,b)$:
\begin{quotation}
Since $\gcd(a+b,b)$ divides both $(a+b)$ and $b$, 
we know it divides $(a+b)-b=a$.
Since $\gcd(a+b,b)$ also divides $b$ by definition,
we know it divides $\gcd (a,b)$ as well.
\end{quotation} 

\item	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
$\gcd(a,b)=\gcd(a+b,b)$: Similar.

\item 	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
$\gcd(a,b,c)=\gcd(\gcd(a,b),c)$:\\
Proof that $\gcd(a,b,c)\divides\gcd(\gcd(a,b),c)$:
\begin{quotation}
Notice that $\gcd(a,b,c)$ divides each of $a$, $b$, and $c$.
Thus, it also divides $\gcd(a,b)$.  
Since it divides both $\gcd(a,b)$ and $c$, it also divides their gcd.
\end{quotation}
Proof that $\gcd(\gcd(a,b),c)\divides\gcd(a,b,c)$:
\begin{quotation}
Let $d=\gcd(\gcd(a,b),c)$.
Now, $d$ divides both $\gcd(a,b)$ and $c$.
Thus, we have  $d\divides\gcd(a,b)\divides a$, so $d\divides a$.
Similarly, $d|b$.
Since $d$ divides each of $a$, $b$, and $c$, it divides their gcd as well.
\end{quotation}
As above, we therefore obtain $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$.

\item	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
$\gcd(a,b,c)=\gcd(\gcd(a,b),\gcd(b,c))$:\\
Proof that $\gcd(a,b,c)\divides\gcd(\gcd(a,b),\gcd(b,c))$:
\begin{quotation}
Again, $\gcd(a,b,c)$ divides each of $a$, $b$, and $c$.
Therefore it divides $\gcd(a,b)$ and it divides $\gcd(b,c)$, 
so it also divides their gcd.
\end{quotation}
Proof that $\gcd(\gcd(a,b),\gcd(b,c))\divides\gcd(a,b,c)$:
\begin{quotation}
Let $e= \gcd(\gcd(a,b),\gcd(b,c))$.  
Since $e$ divides both $\gcd(a,b)$ and $\gcd(b,c))$, 
it also divides $a$, $b$, and $c$ individually.
It follows that $e\mid \gcd(a,b,c)$.
\end{quotation}
As above, we therefore obtain $\gcd(a,b,c)=\gcd(\gcd(a,b),\gcd(b,c))$

\end{enumerate}
\qed
\end{proof}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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|$.

\begin{proof}
We begin by defining {\em lowest terms}.  It is important
that we check that our definition is ``well-defined'', that is, 
that our definition makes sense---things we assume exist do in fact exist
and things we assume are unique are in fact unique.

\begin{quote}
{\bf Definition:} 
$q=a_0/b_0$ is in {\bf lowest terms} if $|b_0|$ is the smallest 
element of the set 
$S=\{ b\in\naturals : \exists a\in\integers \mbox{ such that } a/b =q\}$.
\end{quote}

Note that since $q\in\rationals$, $S$ is not empty: 
by definition, $q=a/b$ for some $a,b\in\integers$; 
if $b<0$, then also $q=(-a/-b)$.
Also, since $S\subseteq \nats$, the Well-Ordering Principle states 
such a smallest element exists.
The following lemma proves a useful fact.
\begin{lemma} \hspace{.1in}
Let $q\in\rationals$. If $q=a/b$ is in lowest terms, then $\gcd(a,b)=1$.
\end{lemma}
\begin{proof}
By contradition.  Assume that $\gcd(a,b)= d>1$.
Define $S$ for $q$ as above.
Then $a=md$ and $b=nd$ for some $m,n\in\integers$.
It follows that $q=md/nd=m/n$ and so $|n|\in S$.
But $|n|<|b|$ because $|b| = d|n|$ and $d>1$.
So $|b|$ is not the smallest element of $S$, 
a contradiction to the fact that $a/b$ is in lowest terms.

Therefore the assumption is false, which implies $\gcd(a,b)= d\leq 1$ 
and in fact $\gcd(a,b)= 1$, since $1$ divides every integer.
This proves the lemma. \qed
\end{proof}

We now can solve the original problem.
We must show that if $a/b+c/d$ is an integer, then $|b|=|d|$.%
\footnote{Note that ``$A$ unless $B$'' is logically equivalent to 
	``$\neg A \Rightarrow B$''.
	So, ``$a/b+c/d$ is not an integer unless $|b|=|d|$'' is equivalent to
	``$a/b+c/d$ is an integer $\Rightarrow$ $|b|=|d|$''.}
Since $a/b$ and $c/d$ are in lowest terms, we have $\gcd(a,b)=1$ and
$\gcd(c,d)=1$.
Now, $a/b+c/d=\frac{ad+bc}{bd}$.  
If this is an integer, then  $bd\mid ad+bc$, which implies $b\mid ad+bc$.  
Since $b\mid bc$, we see that $b\divides ((ad+bc)-bc)$, or $b\mid ad$.  
Recall the theorem that says if $x\mid yz$ and $\gcd(x,y)=1$, then $x\mid z$.
Since we have $b\mid ad$ and $\gcd(a,b)=1$, we conclude that $b\divides d$.
Similarly, we derive that $d\mid b$.  
Therefore, $|b|=|d|$.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\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.)
\begin{proof}
By contradiction.  Assume $\sqrt{p}$ is rational, and 
let $\sqrt{p}=a/b$ be in lowest terms (note that this uses the well-ordering
principle implicitly).
This gives $b^2p=a^2$, which implies $p\divides a^2$.
Recall that if $p$ is prime and $p\divides xy$, then either $p\divides x$
or $p\divides y$.  
Therefore $p\divides a$;  we can write $p=ma$ for some $m\in\integers$.
Thus, $a^2 = (mp)^2 = b^2p$, or $m^2p=b^2$.
As before, we conclude that $p\divides b$.
Together with $p\divides a$, this implies $p\divides \gcd(a,b)=1$,
which is impossible.
This contradiction implies that 
the assumption is false, and therefore $\sqrt{p}$ is irrational.
\end{proof}

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

\begin{proof}
We will prove the contrapositive:
If $n$ is composite, then $2^n-1$ is composite.

If $n$ is composite, then $n=ab$ for some $a,b\in\nats$ with $1<a<n$.
Recall that $(x-1) \mid (x^k -1)$ (the quotient is $x^{k-1}+\cdots +x+1$).
Letting $x=2^a$, we have $(2^a - 1) \divides ((2^a)^b - 1)$.
Since $1<a<n$, we have $1<(2^a-1)<(2^n-1)$, 
and so $2^a-1$ is a nontrivial divisor of $2^n-1$.
\remove{
	Now, $2^n-1=2^{ab}-1=(2^a-1)(2^{(b-1)a}+2^{(b-2)a}+2^{(b-3)a}+ \cdots +
	2^a + 1)$.
	For $a>1$, $2^a-1>1$.  
	For $a>1,b>1$, $2^{(b-1)a} >1$, thus
	$(2^{(b-1)a}+2^{(b-2)a}+2^{(b-3)a}+ \cdots +
	2^a + 1) >1$.
}
Therefore, $2^n-1$ is composite.
\end{proof}


\end{problems}

\end{document}
