\magnification=\magstep1
\centerline{MONT 104Q -- Mathematical Journeys: From Known to Unknown}
\centerline{Group Discussion Day 1 -- Two proofs from Euclid in Hardy's {\it A Mathematician's Apology}}
\centerline{September 21, 2015}
\bigskip
\noindent
{\it Background}
\bigskip
On pages 92 to 96 of {\it A Mathematician's Apology}, Hardy gives two famous examples of
proofs that he says exemplify ``serious mathematics.''  Both appear in essentially the same
form in the {\it Elements} of Euclid that we will study next, although not in the section
on geometry that we will study in detail.  In this discussion day, we want to work through
the details of these proofs to understand the logic behind them.  Second we want to think 
about what Hardy says about their usefulness, or lack thereof.
\bigskip
\noindent
{\it Questions}
\bigskip
\item{A.}  The first proof shows that there are {\it infinitely many different prime numbers}.
\bigskip
\itemitem{1.}  Exactly how do Hardy and Euclid present the concept of a prime number?  Note that 
Hardy takes care to say that $n = 1$ is {\it not} considered to be prime (even though the only positive 
factors of $1$ are $1$ and $n = 1$, so it looks as though we might want to).  
Is this the way you saw primes defined in your previous mathematical work?
\itemitem{2.}  The beginning of this journey, so to speak, is to assume the opposite of the
statement to be proved:  ``Let us suppose that [the series of primes {\bf does} come to an end] and that
$$2,3,5,\ldots, P$$  
is the complete series ... .''  The
strategy that will be used here is called {\it indirect proof} or {\it proof by contradiction}, or 
{\it reductio ad absurdum} in Latin.  What does this mean?  
\itemitem{3.}  Identify and carefully state (at least) two important facts about prime numbers 
and other integers that Euclid and Hardy are assuming to be {\it already known} in order 
to carry out this proof.  Hint:  Think about the way the reasoning goes after the formation 
of the integer 
$$Q = 2\cdot 3 \cdot 5 \cdot \cdots \cdot P + 1.$$
\itemitem{4.}  A relatively subtle point: What is it about the process of dividing one 
integer into another that lets Euclid and Hardy conclude that the primes $2,3,\ldots, P$ {\it do not
divide} $Q$?
\itemitem{5.}  Exactly where does the contradiction that proves the result come from?  If we had just
``missed'' one or more primes appearing in the factorization of $Q$, 
why couldn't we just include them in our list and say that we had the 
complete list of primes now?
\bigskip
\item{B.}  The second proof, sometimes ascribed to Pythagoras or his school, 
shows that the number $\sqrt{2}$ cannot be written in the form
$\sqrt{2} = {a \over b}$ for integers $a,b$.  (We say now that $\sqrt{2}$ is an {\it irrational number}
to express this more succinctly.)
\bigskip
\itemitem{1.}  How is this proof similar to the first one?  What is the key starting point for
this journey?  Hint:  The most important thing here is a key assumption about the integers $a,b$.
\itemitem{2.}  How is a contradiction reached here?
\itemitem{3.}  A related but slightly different proof would be to consider the equation $a^2 = 2b^2$
where $a,b$ are integers.  
If we write out {\it the prime factorizations} for $a$ and $b$ and substitute 
them into the equation $a^2 = 2b^2$, then count the number of 2's appearing on both sides, it can be seen that
we get another contradiction.  Explain how that proof would work.  Does this seem easier or harder to 
understand to you than the proof Hardy describes?  Why do you suppose Hardy presents the proof the
way he does?
\bigskip
\item{C.}  Hardy states on page 101 that ``There is no doubt at all, then, of the `seriousness'
of either theorem.  It is therefore the better worth remarking that neither of them has the 
slightest `practical' importance.''  What evidence does Hardy give to justify this statement?
The {\it RSA public key encryption system} is what almost all of today's web browsers use to 
make secure transmission of information over the internet possible.  Look this up and try to 
identify the role of prime numbers in RSA.  Was Hardy right about the lack of practical importance
of the fact that there are infinitely many primes? 
\bigskip
\noindent
{\it Assignment}
\bigskip
One writeup from each group, due in class on September 23.  These can be typed or 
hand-written as you prefer.  
\end
