\documentclass[12pt]{article}

\usepackage{amssymb,amsmath,amsthm} 
\usepackage{color}
\usepackage{verbatim}

%%% Margins %%%
\setlength{\topmargin}{0pt}
\setlength{\headheight}{0pt}
\setlength{\headsep}{0pt}
\setlength{\topskip}{0pt}
\setlength{\footskip}{0pt}
\setlength{\oddsidemargin}{-20pt}
\setlength{\textheight}{9in}
\setlength{\textwidth}{6.7in}
\setlength{\parindent}{0pt}
\setlength{\parskip}{4ex}

%%% Macros %%%
% Some macros to get you started
\DeclareMathOperator{\Vol}{Vol}
\DeclareMathOperator{\im}{im}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\QQ}{\mathbb{Q}}




\begin{document}

\pagestyle{empty}

\begin{center}
{\large MATH 108 Fall 2019 \ -  \ {\bf Problem Set 4}}

% Put your name and section here.
{\large due October 25}
\end{center}


\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item Let $n = a_1a_2 \cdots a_k$ with $k \geq 1$ and $a_1,a_2,\ldots,a_k$ positive integers and let $p$ be a prime.  Use Euclid's Lemma and induction on $k$ to prove that if $p$ divides $n$, then $p$ divides $a_i$ for some $1 \leq i \leq k$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item A positive integer $n$ is called {\em square-free} if it is not divisible by any perfect square except for 1.  Prove that $n$ is square-free if and only if $n$ is a product of distinct primes. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item For positive integers $x$ and $y$, the {\em greatest common divisor} of $x$ and $y$ is the largest postive integer that divides both $x$ and $y$, denoted $\gcd(x,y)$.  Let $a,b,c$ be postive integers.
	\begin{enumerate}
	 \item Prove that $a/\gcd(a,b)$ and $b/\gcd(a,b)$ are integers that have no common factor.
	 \item For $p$ a prime, prove that $p$ divides $a$ and $p$ divides $b$ if and only if $p$ divides $\gcd(a,b)$.
	\end{enumerate}
     
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item For positive integers $a$ and $b$ with $\gcd(a,b) = d$, prove that
	   \[ \{as + bt \mid s,t \in \ZZ\} = d\ZZ. \]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item For each relation, list which of the following properties it has: symmetric, antisymmetric, transitive, reflexive, irreflexive.
	 \begin{enumerate}
	  \item $\leq$ on $\ZZ$.
	  \item $\neq$ on $\ZZ$.
	  \item $\subseteq$ on $\mathcal{P}(\ZZ)$.
	  \item ``is the child of'' on people.
	  \item $\{(1,5),(5,1),(1,1)\}$ on $A = \{1,2,3,4,5\}$.
	  \item $\{(x,y) \in \ZZ \times \ZZ \mid x+y = 10\}$ on $\ZZ$.
	 \end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	
	\item Let $A = \{1,2,3,4,5\}$ and let $\sim$ be the relation on $\mathcal{P}(A)$ defined by $S \sim T$ if $|S| = |T|$.
	\begin{enumerate}
	 \item Prove that $\sim$ is an equivalence relation.
	 \item How many equivalence classes does $\sim$ have and how many elements are in each class?
	\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item Let $\sim$ be a relation on set $A$ with the property that for all $a \in A$, there exists $b \in A$ such that $a \sim b$.  Prove that if $\sim$ is transitive and symmetric, then $\sim$ is reflexive.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{enumerate}
\end{document}


