\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}