\documentclass[11pt,onecolumn,fleqn]{article}

\usepackage[latin1]{inputenc}
\usepackage{bbm}
\usepackage{enumerate}
\usepackage[hang,flushmargin]{footmisc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{stmaryrd}
\usepackage{xcolor}
\usepackage{pdflscape}
\usepackage{tikz-cd}
\usepackage{hyperref}

\usepackage{bussproofs}
\newcommand{\TagC}[1]{\RightLabel{\scriptsize #1}}

\theoremstyle{definition}
\newtheorem*{theorem}{Theorem}
\newtheorem*{lemma}{Lemma}
\newtheorem*{corollary}{Corollary}
\newtheorem*{proposition}{Proposition}
\newtheorem*{definition}{Definition}
\newtheorem*{example}{Example}

\setlength{\oddsidemargin}{0px}
\setlength{\textwidth}{460px}
\setlength{\voffset}{-1.5cm}
\setlength{\textheight}{20cm}
\setlength{\parindent}{0px}
\setlength{\parskip}{10pt}

\newcommand{\TT}{$\checkmark$}
\newcommand{\FF}{$\times$}

\newcommand{\points}[1]{\hfill {\bf \color{darkgray} [#1 points]}}

\DeclareMathOperator{\circhat}{\widehat{\circ}}

\begin{document}
\thispagestyle{empty}
\begin{center}
{\Huge
15-151 Homework 6
}

Please submit in class at 8:00am on Tuesday 25th July
\end{center}

\subsection*{Exercises}

\begin{enumerate}[1.]
\item Let $S : \mathbb{Z} \to \mathcal{P}(\mathbb{Z})$ be any function, and define a subset $B \subseteq \mathbb{Z}$ by
$$B = \{ n \in \mathbb{Z} \mid n \not \in S(n) \}$$
Prove that there is no $k \in \mathbb{Z}$ such that $B=S(k)$.
\points{6}

\item Let $A,B,X$ be sets such that $A \cap B = \varnothing$, and let $f : A \to X$ and $g : B \to X$ be functions. Define $h : A \cup B \to X$ by letting
$$h(t) = \begin{cases} f(t) & \text{if } t \in A \\ g(t) & \text{if } t \in B \end{cases}$$
Prove that $\mathrm{Gr}(h) = \mathrm{Gr}(f) \cup \mathrm{Gr}(g)$.
\points{6}

\item Use the Euclidean algorithm to compute the greatest common divisors of the following pairs of integers:
$$(42, 30) \qquad (363, 154) \qquad (8085, 3094)$$
Include the steps of the computation in your written solution.
\points{9}

\item For each $n \in \mathbb{Z}$, let $D_n \subseteq \mathbb{Z}$ be the set of divisors of $n$. Prove that $D_a \cap D_b = D_{\mathrm{gcd}(a,b)}$ for all $a,b \in \mathbb{Z}$.
\points{7}

\item Let $a,b \in \mathbb{Z}$ and suppose that $d_1$ and $d_2$ are greatest common divisors of $a$ and $b$. Prove that either $d_1=d_2$ or $d_1=-d_2$.
\points{7}
\end{enumerate}

\end{document}