\documentclass{article}
\usepackage{amsmath,amssymb,amsthm,enumerate}
\usepackage{fullpage}
\usepackage{color}
\newcommand{\st}{{\text{\huge {.}}}\;}
\newcommand{\xmod}{\!\!\!\mod}
\DeclareMathOperator{\im}{Im}
\newcounter{theproblem} \setcounter{theproblem}{1}
\newenvironment{problem}[1][]
{\noindent{{\color{blue}\large\bf
\arabic{theproblem}. #1} \stepcounter{theproblem}\vspace{0.3cm}}\\}
{\vspace{0.5cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}\newpage}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\noindent{\color{blue}{\Large\bf Homework 6 \hfill 21-127 Concepts of Math \hfill due 10.18.2012}\\
\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% Assignment begins here! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\color{blue}\large\bf Name:} % WRITE YOUR NAME HERE
\vspace{0.3cm}\\
{\color{blue}\large\bf Andrew ID:} % WRITE YOUR ANDREW ID HERE
\vspace{0.3cm}\\
{\color{blue}\large\bf Section:} % WRITE YOUR RECITATION SECTION HERE
\vspace{0.3cm}\\
{\color{blue}\large\bf Collaborators:} % LIST ANYONE YOU WORKED WITH HERE
\vspace{0.3cm}\\
{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
\begin{problem}[Spoofs and Truths (10 pts)]
For each of the following two {\it spoofs}, identify which claim in the {\it argument} is incorrect. Then, provide an explanation (including an example, in {\bf\color{blue}(a)}, as well) as to why the {\it conclusion} of the argument is also incorrect.
\begin{enumerate}[{\color{blue}\bf(a)}]
\item Let $n\in\mathbb{N}$ and let $a,b,x\in\mathbb{Z}$. Suppose that $ax\equiv bx\xmod n$. We claim that we can ``cancel'' and deduce that $a\equiv b\xmod n$.\vspace{0.2cm}\\
Since $ax\equiv bx\xmod n$ then, by definition, $n\mid ax-bx$. Thus, $n\mid x(a-b)$, and so $n\mid a-b$. By definition, then, $a\equiv b\xmod n$.
\item Consider the system of congruences
\begin{align*}
x &\equiv 1\xmod 2\\
x&\equiv 2\xmod 6
\end{align*}
The {\bf Chinese Remainder Theorem} (see Problem \#6) guarantees the existence of a solution $X$.
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[There's A Reason We Make You Prove Things \ldots (15 pts)]
Define the relation $T$ on $\mathbb{R}$ by setting
\[ \forall x,y\in\mathbb{R}\st\;(x,y)\in T\;\iff\; \left(\;\frac{y}{x}\in\mathbb{R}\;\wedge\; \frac{y}{x}\geq 0\right) \]
\begin{enumerate}[{\color{blue}\bf(a)}]
\item For every $x\in\mathbb{R}$, let the set $S(x)$ be
\[ S(x) = \{ y\in\mathbb{R}\mid (x,y)\in T\}\]
Write down what the sets $S(-1)$, $S(0)$, and $S(1)$ are.
\item Use the three sets from part {\bf\color{blue}(a)}, as well as some result you have proven previously (Hint: {\it I} didn't prove it, you did!), to deduce that $T$ is {\bf not} an equivalence relation.
\item Verify this result by showing that $T$ is not reflexive and not symmetric.
\item Is $T$ transitive or not? Prove your claim.
\end{enumerate}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Function Junction (15 pts)]
For each of the following ``rules'' and proposed domains and codomains, determine whether the ``rule'' defines a {\bf well-defined function}. Explain your answer using examples, if necessary.
\begin{enumerate}[{\color{blue}\bf(a)}]
\item Let $a:\mathbb{Z}-\{1\}\to\mathbb{R}$ be defined by $a(x)=\displaystyle{\frac{x^2}{x-1}}$.
\item Let $b:\mathbb{Q}\to\mathbb{Q}$ be defined by $b(x)=\sqrt{|x|}$.
\item Let $c:\mathbb{Z}\to\mathbb{Z}$ be defined by outputting an $s$ such that $x\equiv s\!\!\!\mod 3$.
\item Let $d:\mathbb{N}\to\mathbb{N}$ be defined by $d(x)=\displaystyle{\left\lfloor \frac{x}{10}\right\rfloor}$.
\item Let $e:\mathcal{P}(\mathbb{N})\to\mathcal{P}(\mathbb{Z})$ be defined by taking in a set of natural numbers and outputting the set of all integer multiples of the least element of that set.
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[$\mathbb{R}$ You $S$e$\mathbb{R}$iou$S$? (15 pts)]
Define the set $S=\{x\in\mathbb{R}\mid 0<x<1\}$. Define the function $g: S\to\mathbb{R}$ by
\[ g(x) = \frac{2x-1}{2x(1-x)}\]
Prove that $\im_g(S)=\mathbb{R}$.\vspace{0.2cm}\\
(Hint: You can cite the quadratic formula, since we proved it in Lecture 2. This is probably helpful \ldots)
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Imag(in)e That! (20 pts)]
Let $A,B$ be sets and let $f:A\to B$ be a function. Suppose $X,Y\subseteq A$.
\begin{enumerate}[{\color{blue}\bf(a)}]
\item Is it necessarily true that the following equality holds?
\[ \im_f(X\cup Y)=\im_f(X)\cup\im_f(Y)\]
State your claim and prove it.
\item Is it necessarily true that the following equality holds?
\[ \im_f(X\cap Y)=\im_f(X)\cap\im_f(Y)\]
State your claim and prove it.
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Only One Problem Remain(der)ing \ldots (25 pts)]
In this problem, we will consider the {\bf Chinese Remainder Theorem} and work through some of the steps of its proof.\vspace{0.2cm}\\
{\bf CRT:} Suppose $r\in\mathbb{N}$ and we have $r$ natural numbers, $n_1,n_2,\dots,n_r$, that are pair-wise relatively prime. (That is, no two of the numbers have any common factors, besides 1.) Suppose we also have $r$ integers, $a_1,a_2,\dots,a_r$. Then there exists a solution $X$ to the system of congruences defined by the $n_i$ and $a_i$; that is,
\[ \exists X\in\mathbb{Z}\st \forall i\in[r]\st X\equiv a_i\xmod n_i\]
Furthermore, if we define $\displaystyle{N=\prod_{i\in[r]}n_i}$, then all of the infinitely-many solutions $Y$ to the system of congruences satisfy $X\equiv Y\xmod N$.
\begin{enumerate}[{\color{blue}\bf(a)}]
\item Throughout, we use $N$ as given by the definition in the Theorem statement: $\displaystyle{N=\prod_{i\in[r]}n_i}$\vspace{0.2cm}\\
For every $i\in[r]$, define $N_i=\frac{N}{n_i}$. Notice that this means $n_i$ and $N_i$ are relatively prime (i.e. they share no common factors), since all of the $n_i$ numbers were assumed to be relatively prime.\vspace{0.2cm}\\
Cite a result from lecture that guarantees (for every $i\in[r]$) the existence of an integer $y_i$ that satisfies $y_iN_i\equiv 1\xmod n_i$.
\item Define
\[ X=\sum_{j=1}^r a_jN_jy_j\]
Let $i\in[r]$ be arbitrary and fixed. Show that for every $j\neq i$, the corresponding term in the sum above that defines $X$ is 0.
\item For that same fixed value of $i$, show that when $j=i$, the corresponding term in the sum above that defines $X$ is $a_i$.
\item Explain why parts {\bf\color{blue}(b)} and {\bf\color{blue}(c)} have shown that $X$ satisfies the given system of congruences.
\item Now, consider the following system of congruences:
\begin{align*}
x&\equiv 2\xmod 3\\
x&\equiv 2\xmod 5\\
x&\equiv 4\xmod 7
\end{align*}
That is, $n_1=3,n_2=5,n_3=7$, and $a_1=2,a_2=2,a_3=4$.\vspace{0.2cm}\\
Following the definitions in the steps above, find $N$ and $N_i$ and $y_i$ (for every $i\in[3]$) and use these to find a solution $X$.
\item Use the other conclusion of the {\bf CRT} to write down the set of {\it all} solutions to the system in {\bf\color{blue}(d)} using set-builder notation, and use this to find the {\bf smallest} natural number that is a solution.
\item {\bf\color{blue}[Bonus]} Prove the second conclusion of the {\bf CRT}, that all solutions are congruent modulo $N$.
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Challenge Problem: Investigating Primes and Congruences (0 pts)]
{\bf Definition:} We say $a,b\in\mathbb{Z}$ are {\bf relatively prime} if they have no common factors, other than 1.
\begin{enumerate}[{\color{blue}\bf(a)}]
\item Suppose $a,b\in\mathbb{Z}$ are relatively prime. Prove that there exist $m,n\in\mathbb{Z}$ such that $ma+nb=1$. (Hint: Use induction on $a+b$. Think about why this is a valid use of induction.)
\item Use {\bf\color{blue}(a)} to prove the following: Suppose $a,b\in\mathbb{Z}$ are relatively prime and $q\in\mathbb{Z}$ and $a\mid qb$. Then $a\mid q$.
\item Use {\bf\color{blue}(b)} (and induction on $k$) to prove that if a prime number $p$ divides a product of $k$ integers, $a_1,a_2,\dots,a_k$, then $p$ must divide {\it at least one} of the $a_i$.
\item Suppose $a,b\in\mathbb{Z}$ are relatively prime and $a\mid n$ and $b\mid n$. Prove that $ab\mid n$.
\item Suppose $a,b\in\mathbb{Z}$ are relatively prime and $x\in\mathbb{Z}$. Consider the set
\[ S=\{x,x+b,x+2b,\dots,x+(a-1)b \}\]
Show that all of the elements of $S$ have {\it distinct} remainders upon division by $a$.
\item Let $p$ be a prime. Define $\mathbb{Z}_p$ to be $\mathbb{Z}/\!\!\equiv_p$, i.e. the set of equivalence classes of the integers when considering the equivalence relation that is {\it congruence modulo $p$}.\vspace{0.2cm}\\
Let $a\in\mathbb{N}$ be given with $1<a<p$. Consider the function $f:\mathbb{Z}_p-\{0\}\to\mathbb{Z}_p-\{0\}$ defined by $f(x)=ax$ (subsequently reduced modulo $p$). Prove that $f$ is a {\it bijection}. (See me and/or the textbook for a definition.)
\item {\bf Fermat's Little Theorem:} Suppose $p$ is a prime number and $a\in\mathbb{Z}$ is not a multiple of $p$. Prove that $a^{p-1}\equiv 1\xmod p$.
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\end{document}