\documentclass{article}
\input{../notes/preamble.tex}
\usepackage{url}
\title{Assignment 5}
\date{Tuesday June 12, 2012}
\newcommand{\df}{\textbf}
\begin{document}
	\maketitle
	
	\section{Algebra}
	This section is intended to completed on Friday June 11th. 
	
	Let $p$ be a prime number for the following two problems. Recall for every $a$ where $a\not\equiv 0 \mod p$, there is an inverse; ie. there is some $b$ such that $a\cdot b \equiv 1 \mod n$. This result will come in handy for the next two problems. 
	
	\begin{prob}
		Fix $p$ a prime number, and $a$ such that $0<a<p$. 
		\begin{enumerate}
			\item Argue by contradiction that all the following are in distinct equivalence classes mod $p$:
			\[
				a,\,2a,\,3a,\,\ldots,\, (p-1) a
			\]
			\item Recall there are $p$ congruence classes mod $p$. Use this and the previous part to argue that
			\[
				a \cdot (2a) \cdot (3a) \cdot \cdots \left((p-1)a\right) \equiv (p-1)! \mod p
			\]
			\item This does not use the previous parts of the problem. Argue that \[a \cdot (2a) \cdot (3a) \cdot \cdots \left((p-1)a\right) \equiv a^{p-1} (p-1)! \mod p\]
			\item Argue that $a^{p-1} \equiv 1 \mod p$ using the previous two parts.
		\end{enumerate}
		You just proved {\bf Fermat's Little Theorem}
	\end{prob}

	\begin{prob}
		Let $p$ be a prime number larger than $2$
		\begin{enumerate}
			\item Take $a\in \Z$ such that $a \not\equiv 0 \mod p$. By the handy result above, $a$ has an inverse. Prove that this inverse is unique. {\it Hint: Suppose it had two inverses; show they are equal}
			
			As inverses are unique, we can make a notation for them: call the inverse of $a$, whenever $a$ is nonzero, $a^{-1}$. So for nonzero $a$, we have $a\cdot a^{-1} \equiv 1 \mod n$. 
			
			\item Prove that $(a^{-1})^{-1} = a$; that is the inverse of $a$'s inverse is $a$. 
			\item Note that $a^2 - 1 \equiv (a+1)(a-1)\mod p$. Prove that $a^2 \equiv 1 \mod p$ if and only if ($a\equiv 1\mod p$) or ($a\equiv -1\mod p$). 
			\item Prove that 
			\[
				(p-1)! \equiv (p-1) \mod p
			\]
			{\it Hint: Look at $2\cdot 3\cdot \cdots \cdot p-2$. Everything on this list has an inverse. Use the previous results to show that the inverse is on this list, cannot be itself, and that its inverse's inverse is itself. So what is this product congruent to mod p?  }
		\end{enumerate}
		
		You just prove {\bf Wilson's Theorem}
	\end{prob}
	
	\section{Relations}
	This section is intended to be completed on Friday June 11th. 
	
	\begin{prob}
		Consider the following theorem and proof:
		\begin{quote}
			\begin{thm}
				If $R$ is a symmetric and transitive relation on $A$, then $R$ is reflexive. 
			\end{thm}
			\begin{proof}
				Take $a\in A$. We want to show that $aRa$. Well, as $aRb$ then we have by symmetry $bRa$. We have $aRb$ and $bRa$, so by transitivity we have $aRa$. Thus $R$ is reflexive. 
			\end{proof}
		\end{quote}
		Give the error of this proof. 
	\end{prob}
	

	
	\section{Basic Functions}
	This section is intended to be completed on Monday June 11th. 
	
	\begin{prob}
		Tell me if the following relations are functions; if they are then give the range. 
		\begin{enumerate}
			\item $\set{ (0,1), (5,6), (2,2)}$
			\item  $\set{ (0,2), (5,3), (0,3), (1,2) }$
		\end{enumerate}
	\end{prob}
	
	\begin{prob}
		For each of the following rules, decide whether they are well-defined functions. Explain why. 
		\begin{enumerate}
			\item $f:\Q\to \Q$ defined by
			\[
				f\left(\frac{a}{b}\right) = a
			\]
			\item $f:\Q \to \Q$ defined by 
			\[
				f\left(\frac{a}{b}\right) = \frac{b}{a}
			\]
			\item $g:Z_3 \to Z$
			\[
				g( [x]_3 ) = x + 2
			\]
			\item $k: \Z \to \Z_7$
			\[
				k(n) = 7n
			\]
		\end{enumerate}

	\end{prob}

	
	\begin{prob}
		Give the range of the following functions:
		\begin{enumerate}
			\item $f:\N\to \N$ defined by
			\[
				f(x) = 2x+3
			\]
			\item $f:\R \to \R$ defined by
			\[
				f(x) = \sqrt{2} \cdot x
			\]
		\end{enumerate}
	\end{prob}
	
	\begin{prob}
		Fix $f: \R\to \R$ by 
		\[
			f(x) = 2x + 1
		\]
		And $g:\R \to \R$ by 
		\[
			g(x) = \sin(x)
		\]
		
		Determine the following
		\begin{enumerate}
			\item $f[ (0,1) ]$
			\item $f^{-1}[ (0,1) ]$
			\item $g[ [0,\frac{\pi}{2}] ]$
			\item $g^{-1}[ [-1,1) ]$
		\end{enumerate}
	\end{prob}



	
	\section{A Preview of Cardinality}
	This section is intended to be completed on Monday June 11th. Here we will just try to preview what we will do with the rest of our week. 
	
	\begin{prob}
		Write down a function from $\N$ to $\Z$ such that for every $y\in \Z$. \[f^{-1}[ \s{y} ] \neq \emptyset\]
	\end{prob}

	
	
	
	
\end{document}
