\documentclass{article}

\usepackage{fancyhdr}
\usepackage{extramarks}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{tikz}
\usepackage[plain]{algorithm}
\usepackage{algpseudocode}
\usepackage[shortlabels]{enumitem}
\usepackage{mathtools}
\usepackage{amssymb}

\usetikzlibrary{automata,positioning}

%
% Basic Document Settings
%

\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9.0in
\headsep=0.25in

\linespread{1.1}

\pagestyle{fancy}
\lhead{\hmwkAuthorName}
\chead{\hmwkClass\ (\hmwkClassInstructor\ \hmwkClassTime): \hmwkTitle}
\lfoot{\lastxmark}
\cfoot{\thepage}

\renewcommand\headrulewidth{0.4pt}
\renewcommand\footrulewidth{0.4pt}

\setlength\parindent{0pt}

%
% Create Problem Sections
%

\newcommand{\enterProblemHeader}[1]{
    \nobreak\extramarks{}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
    \nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
}

\newcommand{\exitProblemHeader}[1]{
    \nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
    \stepcounter{#1}
    \nobreak\extramarks{Problem \arabic{#1}}{}\nobreak{}
}

\setcounter{secnumdepth}{0}
\newcounter{partCounter}
\newcounter{homeworkProblemCounter}
\setcounter{homeworkProblemCounter}{1}
\nobreak\extramarks{Problem \arabic{homeworkProblemCounter}}{}\nobreak{}

\newcommand{\hmwkTitle}{Homework 8}
\newcommand{\hmwkDueDate}{November 16, 2023}
\newcommand{\hmwkClass}{Discrete Math}
\newcommand{\hmwkClassTime}{Section 003}
\newcommand{\hmwkClassInstructor}{Reese Lance}
\newcommand{\hmwkAuthorName}{\textbf{Rushil Umaretiya}}

%
% Title Page
%

\title{
    \vspace{2in}
    \textmd{\textbf{\hmwkClass:\ \hmwkTitle}}\\
    \normalsize\vspace{0.1in}\small{\textbf{Due\ on\ \hmwkDueDate\ at 11:59pm}}\\
    \normalsize\text{Tuesday/Thursday 11:00-12:15, Phillips 383}\\
    \vspace{0.1in}\large{\textit{\hmwkClassInstructor\ - \hmwkClassTime}}
    \vspace{3in}
}

\author{\hmwkAuthorName\\\small{rumareti@unc.edu}}
\date{}

\renewcommand{\part}[1]{\textbf{\large Part \Alph{partCounter}}\stepcounter{partCounter}\\}

%
% Various Helper Commands
%

% Useful for algorithms
\newcommand{\alg}[1]{\textsc{\bfseries \footnotesize #1}}

% For derivatives
\newcommand{\deriv}[1]{\frac{\mathrm{d}}{\mathrm{d}x} (#1)}

% For partial derivatives
\newcommand{\pderiv}[2]{\frac{\partial}{\partial #1} (#2)}

% Integral dx
\newcommand{\dx}{\mathrm{d}x}

% Alias for the Solution section header
\newcommand{\solution}{\textbf{\large Solution}}

\newcommand{\unit}[1]{\section{Unit #1}}
\newcommand{\problem}[1]{\textbf{\##1}}
\newcommand{\prob}[1]{\problem{#1}}


% Probability commands: Expectation, Variance, Covariance, Bias
\newcommand{\E}{\mathrm{E}}
\newcommand{\Var}{\mathrm{Var}}
\newcommand{\Cov}{\mathrm{Cov}}
\newcommand{\Bias}{\mathrm{Bias}}

\renewcommand{\And}{\wedge}
\newcommand{\Or}{\vee}
\newcommand{\Xor}{\oplus}
\newcommand{\Not}{\neg}
\newcommand{\Implies}{\rightarrow}
\newcommand{\Iff}{\leftrightarrow}
\newcommand{\union}{\cup}
\newcommand{\intersection}{\cap}

\newcommand{\AllIntegers}{\mathbb{Z}}
\newcommand{\AllNaturals}{\mathbb{N}}
\newcommand{\AllRationals}{\mathbb{Q}}
\newcommand{\AllReals}{\mathbb{R}}
\newcommand{\AllComplexes}{\mathbb{C}}

\renewcommand{\mod}{\textbf{ mod }}
\renewcommand{\pmod}[1]{\textbf{ (mod }#1)}

\begin{document}

\maketitle

\pagebreak

\unit{4.1}
\prob{10}
Prove that if \(a\) and \(b\) are nonzero integers, \(a | b\), and \(a + b\) is odd, then \(a\) is odd.
\begin{proof}
    Direct proof. Assume \(a\) and \(b\) are nonzero integers, \(a | b\), and \(a + b\) is odd. Then, by definition of divisibility, \(\exists k \in \AllIntegers, ak = b\). We also know that \(a + b\) is odd, so \(\exists j \in \AllIntegers, 2j + 1 = a + b\). Substituting \(b\) for \(ak\), we get \(2j + 1 = a + ak\). Factoring out \(a\), we get \(2j + 1 = a(1 + k)\). Since \(1 + k\) is an integer, we know that \(a\) is odd.
\end{proof}
\pagebreak
\prob{26}
Evaluate these quantites:
\begin{enumerate}[a)]
    \item \(-17 \textbf{ mod } 2\) = \hspace{12pt} 1
    \item \(144 \textbf{ mod } 7\) = \hspace{14pt} 4
    \item \(-101 \textbf{ mod } 13\) = \hspace{5pt}3
    \item \(199 \textbf{ mod } 19\) = \hspace{9pt} 9
\end{enumerate}
\pagebreak
\prob{34}
Decide whether each of these integers is congruent to 3 modulo 7.
\begin{enumerate}[a)]
    \item 37
    \begin{align*}
        7 \nmid (37 - 3)\\
        37 \not\equiv 3 \pmod{7}
    \end{align*}
    \item 66
    \begin{align*}
        7 \mid (66 - 3)\\
        66 \equiv 3 \pmod{7}
    \end{align*}
    \item -17
    \begin{align*}
        7 \nmid (-17 - 3)\\
        -17 \not\equiv 3 \pmod{7}
    \end{align*}
    \item -67
    \begin{align*}
        7 \mid (-67 - 3)\\
        -67 \equiv 3 \pmod{7}
    \end{align*}
\end{enumerate}

\pagebreak
\prob{36}
Find each of these values.

\textbf{Note: } The following rules exist for modular arithmetic where \(a, b, n \in \AllIntegers, n \geq 2\):
\begin{align*}
    (a + b) \textbf{ mod } n &= ((a \textbf{ mod } n) + (b \textbf{ mod } n)) \textbf{ mod } n & \text{Addition Law}\\
    (a \cdot b) \textbf{ mod } n &= ((a \textbf{ mod } n) \cdot (b \textbf{ mod } n)) \textbf{ mod } n & \text{Multiplication Law}\\
\end{align*}

\begin{enumerate}[a)]
    \item \((177 \mod 31 + 270 \mod 31) \mod 31\)
    \begin{align*}
        (177 \mod 31 + 270 \mod 31) \mod 31 &= (177 + 270) \mod 31\\
        &= 447 \mod 31\\
        &= 13
    \end{align*}
    \item \((177 \mod 31 \cdot 270 \mod 31) \mod 31\)
    \begin{align*}
        (177 \mod 31 \cdot 270 \mod 31) \mod 31 &= (177 \cdot 270) \mod 31\\
        &= 47790 \mod 31\\
        &= 19
    \end{align*}
\end{enumerate}
\pagebreak
\unit{6.1}
\prob{8}
How many different three-letter initials with none of the letters repeated can people have?

\begin{align*}
    26 \cdot 25 \cdot 24 = 15600
\end{align*}

\pagebreak

\prob{22}
How many positive integers less than 1000,

\begin{enumerate}[a)]
    \item are divisible by 7?
    \begin{align*}
        \lfloor \frac{1000}{7} \rfloor = 142
    \end{align*}
    \item are divisible by 7 but not by 11?
    \begin{align*}
        \lfloor \frac{1000}{7} \rfloor - \lfloor \frac{1000}{77} \rfloor = 142 - 12 = 130
    \end{align*}
    \item are divisible by both 7 and 11?
    \begin{align*}
        \lfloor \frac{1000}{77} \rfloor = 12
    \end{align*}
    \item are divisible by either 7 or 11?
    \begin{align*}
        \lfloor \frac{1000}{7} \rfloor + \lfloor \frac{1000}{11} \rfloor - \lfloor \frac{1000}{77} \rfloor = 142 + 90 - 12 = 220
    \end{align*}
    \item are divisible by exactly one of 7 and 11?
    \begin{align*}
        \lfloor \frac{1000}{7} \rfloor + \lfloor \frac{1000}{11} \rfloor - 2 \lfloor \frac{1000}{77} \rfloor = 142 + 90 - 24 = 208
    \end{align*}
    \item are divisible by neither 7 nor 11?
    \begin{align}
        999 - 220 = 779
    \end{align}
    \item have distinct digits?
    \begin{align*}
        9 && \text{One digit}\\
        (10-1) \cdot 9 && \text{Two digits}\\
        (10-1) \cdot 9 \cdot 8 && \text{Three digits}\\
        9 + 9 \cdot 9 + 9 \cdot 8 \cdot 7 = 738 && \text{Total}
    \end{align*}
    \item have distinct digits and are even
    \begin{align*}
        4 && \text{One digit}\\
        9 + 8 \cdot 4 && \text{Two digits}\\
        9 \cdot 8 + 8 \cdot 8 \cdot 4 && \text{Three digits}\\
        4 + (9 + 8 \cdot 4) + (9 \cdot 8 + 8 \cdot 8 \cdot 4) = 373 && \text{Total}
    \end{align*}

\end{enumerate}
\pagebreak
\prob{28}
How many license plates can be made using either three digits followed by three uppercase English letters or three uppercase English letters followed by three digits?

\begin{align*}
    10^3 \cdot 26^3 + 26^3 \cdot 10^3 = 3.5152 \cdot 10^7
\end{align*}
\pagebreak
\end{document}