
\documentclass[12pt, onepage]{article}
\usepackage[margin=0.75in]{geometry}
\usepackage{amsmath,amsfonts,amsthm}

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


\def\mod{{\rm mod}\, }

\begin{document}
\openup 1\jot
\large
\centerline{\rm \bf  Math 301   Homework 3 (due on September 13, 2023)}\vskip.1in

\vskip.2in
\noindent{\Large\bf Section 2.1}

\vskip.1in
\noindent{\bf 6.}  If $a\equiv b\ (\mod n)$ and $k|n$, is it true that  $a\equiv b\ (\mod k)$? Justify your answer. 
\vskip.1in
 \noindent{\bf  12.} If $p\ge 5$ and $p$ is prime, prove that $[p]=[1]$ or $[p]=[5]$ in $\Z_6$. [Hint:Theorem 2.3 and Corollary 2.5.]

\vskip.1in

\noindent{\bf 14.}  
\begin{itemize}
 
\item[(a)] Prove or disprove: If  $ab\equiv      0\ (\mod n)$, then $ a \equiv      0\ (\mod n)$ or   $ b \equiv      0\ (\mod n)$ 
\vskip.1in

\item[(b)]  Do part (a) when $n$ is prime.

\end{itemize}
\vskip.1in
 \noindent{\bf  16.}   If $[a]=[1]$ in $\Z_n$, prove that $ (a,n)=1$. Show by example that the converse may be false.
\vskip.1in
\noindent{\bf  20.}  

\begin{itemize}
 
\item[(a)] Prove or disprove: If  $a^2\equiv    b^2 \ (\mod n)$, then $ a \equiv      b\ (\mod n)$ or   $ a \equiv     -b\ (\mod n)$.  

\item[(b)]  Do part (a) when $n$ is prime.


\end{itemize}





 \noindent{\bf  22.}
\vskip.1in
   

\begin{itemize}
 
\item[(a)] Give an example to show that the following statement is false: If  $ab\equiv    ac \ (\mod n)$ and  $ a\not\equiv      0\ (\mod n)$, then    $ b \equiv    c\ (\mod n)$. 

\item[(b)]  Prove that the statement in part (a) is true whenever $ (a,n)=1$.

\end{itemize}






\vskip.1in
\noindent{\Large\bf Appendix C}\vskip.1in

\noindent{\bf 15.}  	What is wrong with the following ``proof'' that all roses are the same color?

It suffices to prove the statement: In every set of n roses, all the roses in
the set are the same color. If $n=1$, the statement is certainly true. Assume the statement is true for $n=k$. Let $S$ be a set of $k+1$ roses. Remove one rose (call it rose $A$) from $S$; there are $k$ roses remaining, and they must all
be the same color by the induction hypothesis. Replace rose $A$ and remove a different rose (call it rose $B$). Once again there are $k$ roses remaining that must all be the same color by the induction hypothesis. Since the remaining roses include rose $A$, all the roses in $S$ have the same color. This proves that
the statement is true when $n=k+1$. Therefore, the statement is true for all
$n$ by induction.
 \vskip.1in



\noindent{\bf 17.} Let $x$ be a real number greater than $-1$. Prove that for every positive integer $n$, $(1+x)^n\ge 1+nx$.


 \vskip.1in

\noindent{\Large\bf Appendix D}\vskip.1in

\noindent{\bf 11.} Let $\sim $ be defined on the set   $\R^*$ of nonzero real numbers by $a\sim b$ if and only if $a/b\in\Q$. Prove that $\sim$ is an equivalence relation.    \vskip.1in



\noindent{\bf 17.} Let $\sim $ be a symmetric and transitive relation on a set $A$. What is wrong with the following ``proof'' that $\sim$ is reflexive: $a\sim b$ implies $b\sim a$ by symmetry; then $a\sim b$ and $b\sim a$  implies $a\sim a$ by transitivity. [Also see Exercise 8(f).]
\end{document}

