\Question{Bijective or not?}
Decide whether the following functions are bijections or not. Please prove your claims.
\begin{Parts}
\Part $f(x) = 10^{-5}x$
\begin{enumerate}[(i)]
\item for domain $\mathbb R$ and range $\mathbb R$
\item for domain $\mathbb Z \cup \{\pi\}$ and range $\mathbb R$
\end{enumerate}
%\Part $f(x) = p \bmod x$, where $p > 2$ is a prime
%\begin{enumerate}[(i)]
%\item for domain $\mathbb N \setminus \{0\}$ and range $\{0, \dots, p\}$
%\item for domain $\{(p+1)/2, \dots, p\}$ and range $\{0, \dots,
%(p-1)/2\}$
%\end{enumerate}
\Part $f(x) = \{x\}$, where the domain is $D = \{0,\dots, n\}$ and the range
is $\mathcal P(D)$, the powerset of $D$ (that is, the set of all subsets of
$D$).
\Part Consider the number $X = 1234567890$, and obtain $X'$ by shuffling the
order of the digits of $X$. Is $f(i) = (\text{i} + 1)^{\text{st}}$ \textit{digit
of} $X'$ a bijection from $\{0,\dots, 9\}$ to itself?
\Part $f(x) = x^5 \pmod{187}$, where the domain is $\{0, 1, 2, 3, \ldots, 186\}$
and the range is $\{0, 1, 2, 3, \ldots, 186\}$.
\Part $f(x) = x^3 \pmod{187}$, where the domain is $\{0, 1, 2, 3, \ldots, 186\}$
and the range is $\{0, 1, 2, 3, \ldots, 186\}$.
\end{Parts}
\Question{Functional Equation}
Usually, in math problems, we give you a function $f$ and ask you to prove some properties about it.
Here, we're going to flip it around: we tell you the property of the function $f$, and you will try to
find all functions that have said property.
Let $f:\mathbb{R} \to \mathbb{R}$ be a function that satisfies the following equation for all $x$ and $y$:
\begin{equation}\label{eq:func} f(f(x)^2 + f(y)) = xf(x) + y \end{equation}
We will find all functions $f$ that satisfy this property.
\begin{Parts}
\Part
First, show that there exists a $x_0$ such that $f(x_0) = 0$. As a hint, you know that equation (\ref{eq:func}) is
true for all $x$ and $y$, so try plugging in some specific values of $x$ and $y$ to see if you get
anywhere.
\nosolspace{.5cm}
\Part
Leverage the previous part to get that $f(f(y)) = y$ for all $y \in \mathbb{R}$.
\nosolspace{.5cm}
\Part
Prove that for any function $g$, if $g(g(y)) = y$, then $g$ is bijective.
\nosolspace{.5cm}
\Part
Plug in $x = f(t)$ into (\ref{eq:func}). Also plug in $x = t$ into (\ref{eq:func}). You can simplify
your equations using the fact proven in part (b). Combine these two equations, use the fact that
$f$ is bijective, to conclude that $f(t)^2 = t^2$ for all $t$.
\nosolspace{.5cm}
\Part
Use the previous part to find all functions $f$ that satisfy equation (\ref{eq:func}). Note that
it is not as simple as taking the square root of both sides! Justify your answer.
\end{Parts}
\Question{Euler's Totient Theorem}Euler's Totient Theorem states that, if $n$ and $a$ are coprime,
\begin{align*}
a^{\phi(n)} \equiv 1 \pmod{n}
\end{align*}
where $\phi(n)$ (known as Euler's Totient Function) is the number of positive
integers less than or equal to $n$ which are coprime to $n$ (including 1).
\begin{Parts}
\Part Let the numbers less than $n$ which are coprime to $n$ be $m_1, m_2, \cdots, m_{\phi(n)}$.
Argue that $am_1, am_2, \cdots, am_{\phi(n)}$ is a permutation of $m_1, m_2, \cdots, m_{\phi(n)}$.
In other words, prove that $f:\{m_1, m_2, ..., m_{\phi(n)}\} \to \{m_1, m_2, ..., m_{\phi(n)}\}$
is a bijection where $f(x) := ax \pmod{n}$.
\Part Prove Euler's Theorem. (Hint: Recall the FLT proof)
\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