\documentclass{article}
\usepackage{amssymb, mathrsfs, enumitem}
\usepackage{tikz-cd}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig, colortbl}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{cor}{Corollary}
\theoremstyle{definition}
\newtheorem{prop}{Proposition}
\newtheorem{fact}{Fact}
\newtheorem{example}{Example}
\newtheorem{definition}{Definition}
\renewcommand{\today}{}


\addtolength{\topmargin}{-.875in}
\addtolength{\oddsidemargin}{-.8in}
\addtolength{\textwidth}{1.6in}
\addtolength{\textheight}{1.75in}


\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\la}{\Leftarrow}
\newcommand{\ra}{\Rightarrow}
\renewcommand{\iff}{\Leftrightarrow}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1\right\rceil}
\DeclareMathOperator{\MOD}{mod}
\renewcommand{\mod}[1]{\ (\MOD\ #1)}
\DeclareMathOperator{\lcm}{lcm}

\newcommand{\inv}[1]{#1^{-1}}

\newcommand{\eps}{\epsilon}
\newcommand{\N}{\mathbb{N}}

\newcommand{\ba}{\backslash}


\begin{document}
\title{Math 127 Homework}
\author{Mary Radcliffe}
\date{Due 25 April 2019}
\maketitle

Complete the following problems. Fully justify each response. You need only turn in those problems marked with a (*).
\begin{enumerate}

\item Prove Propositions 1 and 2 from \href{http://math.cmu.edu/~mradclif/teaching/127S19/Notes/Division.pdf}{Division} notes.

\item Prove Proposition 3 from \href{http://math.cmu.edu/~mradclif/teaching/127S19/Notes/Division.pdf}{Division} notes.

\item (*) Suppose $p_1, p_2, \dots, p_r\in\Z$ are distinct primes. Let $a=p_1^{k_1}p_2^{k_2}\dots p_r^{k_r}$, and let $b=p_1^{j_1}p_2^{j_2}\dots p_r^{j_r}$, where $k_1, k_2, \dots, k_r, j_1, j_2, \dots, j_r$ are nonnegative integers. Prove that $\gcd(a, b)=p_1^{m_1}p_2^{m_2}\dots p_r^{m_r}$, where $m_i=\min\{k_i, j_i\}$ for all $1\leq i\leq r$.

\item For each of the following equations: determine if the equation has solutions. If so, write an expression for all possible solutions to the equation. If not, explain how you know there are no solutions.
\begin{enumerate}
\item $12a+9b=15$.
\item $12a+9b=1$.
\item $2a+3b=1$.
\item $50000a+18412b=1$.
\end{enumerate}

\item (*) Let $a, b, c\in\Z$. Prove that if $a\perp b$ and $a|(bc)$, then $a|c$.

\item Given $a, b\in\Z$, define the {\it least common multiple} of $a, b$ to be the unique nonnegative integer $m$ such that
\begin{itemize}
\item $a|m\wedge b|m$.
\item $(a|q\wedge b|q)\ra m|q$.
\end{itemize}
We write $m=\lcm(a, b)$.
\begin{enumerate}
\item Prove that this definition of $\lcm$ is well-defined.
\item Prove that if $a, b\in\Z$, $m=\lcm(a, b)$ and $d=\gcd(a,b)$, then $md=|ab|$.\end{enumerate}

\item Define a relation $\sim$ on $\N$ by $x\sim y$ if $\gcd(x, y)=1$. Is this an equivalence relation? If so, prove it. If not, explain why not.

\item Let $X, Y$ be sets, and let $f:X\to Y$ be a function. Define a relation $\sim$ on $X$ by $x_1\sim x_2$ if $f(x_1)=f(x_2)$. Is this an equivalence relation? If so, prove it. If not, explain why not.

\item (*) Let $X$ be a set, and let $\sim_1$ and $\sim_2$ be two equivalence relations on $X$. Define a relation $~$ on $X$ by $x\sim y\equiv (x\sim_1 y)\wedge (x\sim_2 y)$. Prove that $\sim$ is an equivalence relation. Describe the classes of $\sim$ in terms of the classes of $\sim_1$ and $\sim_2$.

\item (*) Let $a, b\in\Z$, $n\in\N$, and $k, \ell\in \N$, such that $k\equiv \ell \mod{n}$ and $a\equiv b\mod n$.
\begin{enumerate}
\item Is it true that $a^k\equiv b^k\mod n$? If so, prove it. If not, find a counterexample.
\item Is it true that $a^k\equiv a^\ell \mod n$? If so, prove it. If not, find a counterexample.
\end{enumerate}

\item Let $a\in \Z$ and let $n\in\N$. Suppose that $a\perp n$. Show that $u, u'$ are both multiplicative inverses for $a\mod n$ if and only if $u$ is a multiplicative inverse for $a\mod n$ and $u\equiv u'\mod n$.

\item (*) Let $p$ be a positive prime, and $k\in\N$. Prove that $\varphi(p^k)=p^k-p^{k-1}$.

\end{enumerate}
\end{document}