\documentclass[12pt]{article}

\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{csquotes}

\usepackage{tikz}
\usetikzlibrary{positioning, scopes} 			%always use these
\usetikzlibrary{backgrounds}

%table spacing
\newcommand{\T}{\rule{0pt}{2.6ex}}
\newcommand{\B}{\rule[-1.2ex]{0pt}{0pt}}


\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\xor}{\operatorname{xor}}


\newtheorem{theorem}{Theorem}
\renewcommand*{\thetheorem}{I.\arabic{theorem}}
\newtheorem{exercise}[theorem]{Exercise}
\theoremstyle{definition}
\newtheorem*{definition}{Definition}

\setlength{\oddsidemargin}{0in} \setlength{\evensidemargin}{0in}
\setlength{\marginparwidth}{0in} \setlength{\marginparsep}{0in}
\setlength{\topmargin}{0in} \setlength{\headheight}{0pt}
\setlength{\headsep}{0in} \setlength{\footskip}{.3in}
\setlength{\textwidth}{6.5in} \setlength{\textheight}{8.2in}%\setlength{\textheight}{9.2in}
\setlength{\parskip}{4pt}


\begin{document}

\begin{center}
{\large{\textsc{Homework 15}}} \\
\textsc{Math 3345 -- Autumn 2022 -- Kutler}
\end{center}

\thispagestyle{empty}

Please complete the following problems on your own paper. Solutions should be written clearly, legibly, and with appropriate style.

\begin{enumerate}
\item \begin{enumerate}
\item Let $x \in \ZZ$ and let $p$ be a prime number. Prove that
\[ \gcd(p,x) = \begin{cases}
p & \text{\ if \ $p | x$;} \\
1 & \text{\ if \ $p \! \nmid \! x$.}
\end{cases} \]
\item Let $p$ and $q$ be distinct prime numbers (i.e., $p \neq q$). Use part (a) to show that $\gcd(p,q) = 1$.
\end{enumerate}

\item
\begin{enumerate}
\item Use the Euclidean algorithm to compute $\gcd(350, 168)$.
\item Find integers $x_1$ and $y_1$ such that $350x_1 + 168y_1 = 14$.
\item Find integers $x_2$ and $y_2$ such that $350x_2 + 168y_2 = 42$. [\textsc{hint:} $42 = 3 \cdot 14$.]
\item Prove that there do not exist integers $x$ and $y$ such that $350x + 168y = 15$.
\end{enumerate}

\end{enumerate}

\vspace{.05 in}

\begin{center}
\textbf{Practice Problems}
\end{center}

It is strongly recommended that you complete the following problems. There is no need to write up polished, final versions of your solutions (although you may find this a useful exercise). Please do not submit any work for these problems.

\begin{enumerate}
\item Let $a \in \ZZ$. Prove that
\begin{enumerate}
\item $\gcd(a,1) = 1$.
\item $\gcd(a,0) = |a|$.
\end{enumerate}

\item Let $a,b \in \ZZ$ be integers which are not both zero. Prove that $\gcd(a,b) = \gcd(|a|, |b|)$.

\item Let $a, b \in \ZZ$ with $b \neq 0$. Prove that the fraction $\frac{a}{b}$ is in lowest terms if and only if $\gcd(a,b) = 1$.]
\end{enumerate}




\end{document}
