\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm,amsfonts,verbatim}
\usepackage{microtype}
\usepackage{url}

\addtolength{\evensidemargin}{-.6in}
\addtolength{\oddsidemargin}{-.6in}
\addtolength{\textwidth}{1.0in}
\addtolength{\textheight}{1.9in}
\addtolength{\topmargin}{-.7in}

\theoremstyle{plain}
\theoremstyle{definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{challenge}[theorem]{Challenge Problem}

\title{\vspace{-50pt}Elementary Number Theory\\
\normalsize Math 175, Section 30, Autumn 2010\\
\large Shmuel Weinberger ({\tt shmuel@math.uchicago.edu})\\
Tom Church ({\tt tchurch@math.uchicago.edu})\\
\url{www.math.uchicago.edu/~tchurch/teaching/175/}}
\author{}
\date{}

\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\C}{\mathbb{C}}

% \DeclareMathOperator{\sin}{sin}   %% just an example (it's already defined)
\DeclareMathOperator{\norm}{norm}


\renewcommand{\baselinestretch}{1.2}
\begin{document}
\maketitle
\setcounter{section}{2}
\vspace{15pt}
\begin{center}
{\huge \bf Script 2: Primes}
\end{center}

\vspace{40pt}

\renewcommand{\baselinestretch}{1.5}
\begin{definition}
Recall that if $g\in\Z$, an integer $a$ is called a {\em divisor} of $n$ if $a|n$.
An integer $p>1$ is called a {\em prime} provided that the only positive divisors
of $p$ are $1$ and $p$ itself.  An integer $n>1$ is called {\em composite} if it is
not prime.
\end{definition}

\begin{theorem}
Every integer $n>1$ has at least one prime factor.
\end{theorem}

\begin{theorem}
Every integer $n>1$ may be factored into a product of primes.
\end{theorem}

\begin{theorem}
Let $p$ be a prime number.  If $p|ab$, then $p|a$ or $p|b$.
\end{theorem}

\begin{theorem}[Fundamental Theorem of Arithmetic]
Every integer $n>1$ may be factored into a product of primes in a unique way up to the order
of the factors.  In other words, there exists a uniquely determined set of primes $\{p_1, \ldots, p_k\}$
and a uniquely determined set of corresponding positive integers $\{\alpha_1, \ldots, \alpha_k\}$
such that $n=p_1^{\alpha_1}\cdot\cdots\cdot p_k^{\alpha_k}$.
\end{theorem}

\begin{theorem}
If $a^2|b^2$, then $a|b$.
\end{theorem}

\begin{exercise}
For any positive real number $x\in \R$, there is a real number $\sqrt{x}$ (you may assume this). It is defined uniquely by the property that $\sqrt{x}>0$ and $(\sqrt{x})^2=x$.

Recall that a real number $x$ is defined to be {\em rational} (and we write $x\in\Q$) if there exist integers $p$ and $q$ such that
$q\cdot x=p$, and $x$ is called {\em irrational} otherwise.

Show that if $n$ is a positive integer that is not a perfect square (that is, there is no $a\in\Z$ such
that $a^2=n$), then $\sqrt{n}$ is irrational.
\end{exercise}\pagebreak

\begin{definition}
A positive integer $m\in \Z$ is called a \emph{square} if $m=d^2$ for some $d\in \Z$.
A positive integer $n\in \Z$ is called \emph{squarefree} if $n$ is not divisible by any square; formally, we say that $n$ is squarefree if $d^2|n \implies d^2=1$.
\end{definition}

\begin{theorem}
Prove that every positive integer $n$ can be written uniquely as $n=rs$, where $r>0$ is squarefree and $s>0$ is a square.
\end{theorem}

\begin{theorem}Prove that the number of integers $m>0$ for which $m\leq N$ and $m$ is a square is at most $\sqrt{N}$. (Hint: prove that the number is exactly $\lfloor\sqrt{N}\rfloor$, the integer you get if you round $\sqrt{N}$ down to the nearest integer.)
\end{theorem}

\begin{theorem}Let $\mathcal{S}=\{p_1,\ldots,p_k\}$ be a set of prime numbers. Prove that the number of squarefree integers $m>0$ for which all the prime factors of $m$ lie in the set $\mathcal{S}$ is $2^k$.
\end{theorem}

\begin{theorem}
Let $\mathcal{S}=\{p_1,\ldots,p_k\}$ be a set of prime numbers. Prove that the number of positive integers $m\leq N$ for which all prime factors of $m$ lie in the set $\mathcal{S}$ is at most $2^k\sqrt{N}$.
\end{theorem}

\begin{theorem}
\label{infinitude}
\underline{Use the preceding theorems} to prove that there are infinitely many primes. %(Hint: we didn't just do all that work for our health.)
\end{theorem}

\begin{theorem}
The prime-counting function $\pi(N)$ is defined to be the number of prime numbers less than or equal to $N$. Prove that $\pi(N)\geq \frac{1}{2}\log_2(N)$. (This is a stronger statement than Theorem~\ref{infinitude}---you should make sure you understand why.)
\end{theorem}

\begin{challenge} If you know another proof of Theorem~\ref{infinitude}: can you use your other proof to show that $\pi(N)\geq \frac{1}{2}\log_2(N)$? How about to show that $\pi(N)\geq \log_2(\log_2(N))$? What is the best bound on $\pi(N)$ which you can get from this other proof?
\end{challenge}
%
%\begin{exercise}
%Show that if $n>0$ is composite, then there is some prime $p$ dividing $n$
%such that $1<p\leq\sqrt{n}$.
%\end{exercise}
%
%\begin{exercise}
%Suppose $n>0$ is composite and that $p$ is the smallest prime dividing $n$. \\
%Show that if $p>\sqrt[3]{n}$, then the integer $n/p$ is also prime.
%\end{exercise}
%
%\begin{theorem}
%There exist arbitrarily large gaps between consecutive primes.
%\end{theorem}
%
%\begin{definition}  
%A prime number of the form $p=2^n-1$ is called a {\em Mersenne prime}.
%\end{definition}
%
%\begin{exercise}
%Show that if $p=2^n-1$ is a Mersenne prime, then $n$ itself it prime.
%\end{exercise}
%
%\begin{exercise}
%Find the smallest prime $n$ for which $p=2^n-1$ is not a Mersenne prime.
%\end{exercise}
%
%\begin{definition}  
%A prime number of the form $p=2^n+1$ is called a {\em Fermat prime}.
%\end{definition}
%
%\begin{exercise}
%Show that if $p=2^n+1$ is a Fermat prime, then $n$ has no odd divisors besides 1.  (And hence
%$n=2^k$ for some $k\geq 0$.)
%\end{exercise}
%
%\begin{exercise}
%Show that $p=2^{2^k}+1$ is a Fermat prime for $k=0, 1, 2, 3, 4$ but not for $k=5$.
%\end{exercise}

%\vspace{30pt}
%\hspace{2.5in}
%\copyright  {\tt 2010 Tom Church (based on script by John Boller)}

\end{document}