Squaring modulo n -- is there a systematic way to generate the fixpoints?

Question

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$?

Answer 1

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. $$

Answer 2

$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.

Answer 3

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\}$.