\Question{Amaze Your Friends}
\begin{Parts}
\Part You want to trick your friends into thinking you can perform mental arithmetic with very large numbers.
What are the last digits of the following numbers?
\begin{enumerate}
\item[i.] \quad $11^{2017}$
\item[ii.] \quad $9^{10001}$
\item[iii.] \quad $3^{987654321}$
\end{enumerate}
\Part You know that you can quickly tell a number $n$ is divisible by $9$ if and only if the sum of the digits of $n$ is divisible by $9$. Prove that you can use this trick to quickly calculate if a number is divisible by $9$.
\end{Parts}
\Question{Euclid's Algorithm}
\begin{Parts}
\Part Use Euclid's algorithm in the lecture note to compute the greatest common divisor of 527 and 323. List the values of $x$ and $y$ of all recursive calls.
\Part Use the extended Euclid's algorithm in the lecture note to compute the multiplicative inverse of 5 mod 27. List the values of $x$ and $y$ and the returned values of all recursive calls.
\Part Find $x$ (mod $27$) if $5x+26\equiv 3$ mod $27$. You can use the result computed in (b).
\Part True or false? Assume $a$, $b$, and $c$ are integers and $c>0$. If $a$ has no multiplicative inverse mod $c$, then $ax \equiv b$ mod $c$ has no solution. Explain your answer.
\end{Parts}
\Question{Solution for $ax \equiv b \bmod m$}
In the lecture notes, we proved that when $\gcd(m, a) = 1$, $a$ has a unique multiplicative inverse, or equivalently $ax \equiv 1\bmod m$ has exactly one solution $x$ (modulo $m$). The proof of the unique multiplicative inverse (theorem 5.2) actually proved that when $\gcd(m, a) = 1$, the solution of $ax \equiv b\bmod m$ with unknown variable $x$ is unique. Now let's consider the case where $\gcd(m, a)>1$ and see why there is no unique solution in this case. Let's consider the general solution of $ax \equiv b\bmod m$ with $\gcd(m, a)>1$.
\begin{Parts}
\Part Let $\gcd(m, a) = d$. Prove that $ax \equiv b\bmod m$ has a solution (that is, there exists an $x$ that satisfies this equation) if and only if $b\equiv0\bmod d$.
\Part Let $\gcd(m, a) = d$. Assume $b \equiv 0\bmod d$. Prove that $ax \equiv b\bmod m$ has exactly $d$ solutions (modulo $m$).
\Part Solve for $x$: $77x \equiv 35 \bmod 42$.
\end{Parts}
\Question{Check Digits: ISBN} In this problem, we'll look at a real-world applications of check-digits.
International Standard Book Numbers (ISBNs) are 10-digit codes ($d_1d_2\ldots d_{10}$) which are assigned by the publisher. These 10 digits contain information about the language, the publisher, and the number assigned to the book by the publisher. Additionally, the last digit $d_{10}$ is a "check digit" selected so that $\sum_{i=1}^{10} i \cdot d_i \equiv 0 \mod 11$. (\textit{Note that the letter X is used to represent the number 10 in the check digit.})
\begin{Parts}
\Part Suppose you have very worn copy of the (recommended) textbook for this class. You want to list it for sale online but you can only read the first nine digits: 0-07-288008-? (the dashes are only there for readability). What is the last digit? Please show your work, even if you actually have a copy of the textbook.\\
\Part Wikipedia says that you can determine the check digit by computing $\sum_{i=1}^9 i\cdot d_i \mod 11$. Show that Wikipedia's description is equivalent to the above description. \\
\Part Prove that changing any single digit of the ISBN will render the ISBN invalid. That is, the check digit allows you to \textit{detect} a single-digit substitution error. \\
\Part Can you \textit{switch} any two digits in an ISBN and still have it be a valid ISBN? For example, could 01\underline{2}34\underline{5}678X and 01\underline{5}34\underline{2}678X both be valid ISBNs? \\
\end{Parts}