\Question {Modular Arithmetic Solutions}
Find all solutions (modulo the corresponding modulus) to the following equations. Prove that there are no other solutions (in a modular setting) to each equation.
\begin{Parts}
\Part $2x \equiv 5 \pmod{15}$
\Part $2x \equiv 5 \pmod{16}$
\Part $5x \equiv 10 \pmod{25}$
\end{Parts}
\Question{Euclid's Algorithm}
\begin{Parts}
\Part Use Euclid's algorithm from lecture to compute the greatest common divisor of 527 and 323. List the values of $x$ and $y$ of all recursive calls.
\Part Use extended Euclid's algorithm from lecture 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 \pmod{27}$ if $5x + 2 6 \equiv 3 \pmod{27}$. You can use the result computed in (b).
\Part Assume $a$, $b$, and $c$ are integers and $c>0$. Prove or disprove: If $a$ has no multiplicative inverse mod $c$, then $ax \equiv b \pmod{c}$ has no solution.
\end{Parts}
\Question{Modular Exponentiation}
Compute the following:
\begin{Parts}
\Part $13^{2018} \pmod {12}$
\nosolspace{1.5cm}
\Part $8^{11111} \pmod 9$
\nosolspace{1.5cm}
\Part $7^{256} \pmod {11}$
\nosolspace{1.5cm}
\Part $3^{160} \pmod {23}$
\nosolspace{1.5cm}
\end{Parts}
\Question{Euler's Totient Function}
Euler's totient function is defined as follows:
$$\phi(n) = | \{i: 1 \leq i \leq n, \texttt{gcd}(n,i) = 1\} |$$
In other words, $\phi(n)$ is the total number of positive integers less than or equal to $n$ which are relatively prime to it.
Here is a property of Euler's totient function that you can use without proof:
For $m,n$ such that \texttt{gcd}($m,n$) = 1, $\phi(mn) = \phi(m) \cdot \phi(n)$.
\begin{Parts}
\Part
Let $p$ be a prime number.
What is $\phi(p)$?
\Part
Let $p$ be a prime number and $k$ be some positive integer.
What is $\phi(p^k)$?
\Part
Let $p$ be a prime number and $a$ be a positive integer smaller than $p$.
What is $a^{\phi(p)} \pmod{p}$?\\\emph{(Hint: use Fermat's Little Theorem.)}
\Part
Let $b$ be a positive integer whose prime factors are $p_1,p_2,\hdots, p_k$.
We can write $b = p_1^{\alpha_1}\cdot p_2^{\alpha_2} \hdots p_k^{\alpha_k}$.
Show that for any $a$ relatively prime to $b$, the following holds:
$$\forall i \in \{1,2,\hdots,k\}, \hspace{0.2cm} a^{\phi(b)} \equiv 1 \pmod{p_i}$$
\end{Parts}
\Question{FLT Converse}
Recall that the FLT states that, given a prime $n$, $a^{n-1} \equiv 1 \pmod{n}$ \textit{for all $1 \leq a \leq n-1$}. Note that it says nothing about when $n$ is composite.
Can the FLT condition ($a^{n-1} \equiv 1 \mod n$) hold for some or even all $a$ if $n$ is composite? This problem will investigate both possibilities.
It turns out that unlike in the prime case, we need to restrict ourselves to looking at $a$ that are relatively prime to $n$. (Note that if $n$ is prime, then every $a