\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 -- Spring 2023 -- Kutler}
\end{center}

\thispagestyle{empty}

\begin{center}
\textbf{Exercises}
\end{center}

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

\begin{enumerate}
\item Without using a calculator, find the natural number $k$ such that $0 \leq k \leq 14$ and $k$ satisfies the given congruence.
\begin{enumerate}
\item $2^{75} \equiv k \mod{15}$
\item $6^{41} \equiv k \mod{15}$
\item $140^{874} \equiv k \mod{15}$
\end{enumerate}

\item Let $a, b, c \in \NN$. Prove that if $\gcd(a,b) = 1$ and $\gcd(a,c) = 1$, then $\gcd(a,bc) = 1$.

[\textsc{hint:} First check that the statement is true if any of $a$, $b$, or $c$ is equal to $1$. Then, for the case where $a > 1$, $b > 1$, and $c > 1$, consider unique prime factorizations.]

\end{enumerate}

\vspace{.15 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 Recall that any positive integer $n \in \NN$ has a unique \textbf{base-10 expression:}
\[ n = \sum_{i=0}^k a_i \, 10^i, \]
where $k \geq 0$ and $0 \leq a_i \leq 9$ for all $i$. The integers $a_i$ are the \textbf{digits} of $n$. For example,
\[ 4592 = 2 \cdot 10^0 + 9 \cdot 10^1 + 5 \cdot 10^2 + 4 \cdot 10^3. \]
Prove the following:
\begin{enumerate}
\item $2|n$ if and only if $2$ divides the ``ones digit'' $a_0$.
\item $3|n$ if and only if $3$ divides the sum of the digits $\sum_{i=0}^k a_i$.
\item $5|n$ if and only if the ones digit $a_0$ is equal to $0$ or $5$.
\end{enumerate}

\item Formulate and prove divisibility criteria similar to those in the previous problem for the following conditions:
\begin{enumerate}
\item $4|n$.
\item $9|n$.
\item $11|n$.
\end{enumerate}
\end{enumerate}




\end{document}
