Squaring modulo n -- is there a systematic way to generate the fixpoints? The natural function
$$f_k(n) = n^2 \bmod k,\quad f_k(n) \in [0;k-1]$$
has at least the fixpoints $n\in\{0;1\}$ for each $n$, but for some $k$ there are other fixpoints. For instance, $f_{100}$ has the fixpoints $\{0;1;25;76\}$. Apart from trying out every possible value for $n$, is there a systematic way to get all fixpoints for a given $k$?
 A: You would like 
$$n^2\equiv n\mod{k}$$
Which is the same as 
$$\begin{align}
n^2-n&\equiv0\mod{k}\\
n(n-1)&\equiv0\mod{k}
\end{align}$$
So 
$$k| n(n-1)$$
This means each maximal prime power factor of $k$ need to divide either $n$ or $n-1$. 
If I had to solve this for some explicit $k$, I'd start by taking the largest prime power of $k$, $p^m$, and enumerate every multiple of $p^m$ less than $k$. For example, with $k=100$, we would enumerate 25, 50, and 75. 
Recognizing that $p^m$ either divides $n$ or $n-1$, either $n$ is one of these enumerated values, or $n-1$ is. In the example, we've already narrowed the list of possible nontrivial solutions from $\{2,3,\ldots 99\}$ to $\{25, 26, 50, 51, 75, 76\}$.
For this example, I'd just check by hand the six possible solutions. But in general for larger $k$, I'd cross this list against a similar list built using the next largest prime power dividing $k$, sieving the list of potential solutions down further. With this example, $4$ is the next prime power, so $n$ needs to be $0$ or $1$ mod $4$. This leaves only $\{25, 76\}$.
A: Along with the Chinese Remainder theorem, you need to be able to factor your $k$ into prime powers. It is a theorem requiring induction that the only solutions to
$$  n^2 \equiv n \pmod {p^t}  $$ for a prime $p$ and $t \geq 1$ are
$$   n \equiv 0,1 \pmod {p^t}. $$
As a result, if your $k$ is divisible by exactly $r$ distinct primes, there are exactly $2^r$ of your fixpoints. For $100,$ note that you got precisely the four numbers from $0$ to $99$ that are $0,1 \pmod 4$ and $0,1 \pmod {25}.$
Let's see, the theorem mentioned is straightforward for odd $p,$ induction on $t.$ Slightly different for $p=2$ but easy enough and still true. 
Induction, odd $p$: with $0 \leq j \leq p-1,$ then $\delta = 0,1,$ and $t \geq 1,$ we are solving
$$  (j p^t + \delta)^2 \equiv j p^t + \delta \pmod {p^{t+1}},  $$
$$ j^2 p^{2t} + 2 j \delta p^t + \delta^2 \equiv  j p^t + \delta \pmod {p^{t+1}}.   $$
Note $\delta^2 = \delta,$ and $2t \geq t + 1.$ So
$$    2 j \delta p^t      \equiv  j p^t  \pmod {p^{t+1}},       $$
$$  (2 \delta - 1) j p^t  \equiv  0 \pmod {p^{t+1}},   $$
$$  (2 \delta - 1) j  \equiv  0 \pmod {p},   $$
$$   j  \equiv  0 \pmod {p},   $$
$$  j = 0.  $$
Induction,  $p=2$: with $j = 0,1,$ then $\delta = 0,1,$ and $t \geq 1,$ we are solving
$$  (j 2^t + \delta)^2 \equiv j 2^t + \delta \pmod {2^{t+1}},  $$
$$ j^2 2^{2t} + 2 j \delta 2^t + \delta^2 \equiv  j 2^t + \delta \pmod {2^{t+1}}.   $$
Note $\delta^2 = \delta,$ and $2t \geq t + 1.$ So
$$    2 j \delta 2^t      \equiv  j 2^t  \pmod {2^{t+1}},       $$
$$     j \delta 2^{t+1}      \equiv  j 2^t  \pmod {2^{t+1}},       $$
$$     0      \equiv  j 2^t  \pmod {2^{t+1}},       $$
$$   0  \equiv  j \pmod {2},   $$
$$  j = 0.  $$
A: $n(n-1)$ must be a multiple of $k$, that is for each prime power $p^m$ dividing $k$, either $n$ or $n-1$ must be a multiple of $p^m$. However the choice may differ per prime. Hence there are $2^r$ solutions if $k$ is divisible by $r$ primes.
With $k=100= 2^25^2$, the fixpoints are $0$ and $1\pmod 4$ and $0$ and $1\pmod {25}$. The combinations of these (via chinese remainder theorem) give the four solutions you mention.
