Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
Using the chinese remainder theorem is a good start. –  Chris Eagle Oct 18 '12 at 21:09
add comment

3 Answers

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.