4
$\begingroup$

What is the number of solutions of $x^2 \equiv x \pmod m$ for any positive integer $m$?

$\endgroup$
15
  • $\begingroup$ look at basic cases and guess the general solution, prove it then. note that you are looking at number that are equal to its square (of course modulo n!) $\endgroup$ – GA316 Feb 18 '16 at 16:16
  • 3
    $\begingroup$ $x^2\equiv x$ implies $x^2-x=x(x-1)\equiv 0$. That should tell you that the factors of $m$ and whether any of them have multiples that are adjacent play a huge role in how many solutions there are. $\endgroup$ – Arthur Feb 18 '16 at 16:18
  • $\begingroup$ @Arthur Could you please explain a bit more please? $\endgroup$ – Yogesh Ghaturle Feb 18 '16 at 16:23
  • 3
    $\begingroup$ @YogeshGhaturle I know you are new to the site, but you must understand that this page is not an "instant full solution" black box. This site is here to help you learn, not to solve everything for you. So when you get a helpful answer (like the one by Arthur), don't just say "can you explain a bit more". Instead, look at the answer, take a piece of paper and a pencil, and try to work from there on. And for a bit longer than 5 minutes. Then, if you are still stuck, explain what you tried and where you are stuck. $\endgroup$ – 5xum Feb 18 '16 at 16:28
  • $\begingroup$ sad to see such a good question downvoted. i added my positive vote $\endgroup$ – Brennan.Tobias Feb 18 '16 at 16:52
7
$\begingroup$

The problem is to count the roots of $x^2 - x \equiv 0 \pmod m$.

Exploring the problem for specific numbers of $m$ first, we see it can have:

  • $2$ roots mod $2$: 0,1
  • $4$ roots mod $6 = 2\cdot 3$: 0,1,3,4
  • $8$ roots mod $30 = 2\cdot 3\cdot 5$: 0,1,6,10,15,16,21,25,30
  • $16$ roots mod $210 = 2\cdot 3\cdot 5\cdot 7$

A good guess is it has $2^r$ roots, for some $r$ depending on $m$.

With some more exploring you can notice that:

  • There is $2$ roots modulo a prime power.
  • There is $2^r$ roots, where $r$ is the number of prime factors of $m$.

A degree $d$ polynomial can only have at most $d$ roots mod some prime $p$. It can have more roots than its degree modulo prime powers though. We need to prove that this special polynomial has exactly $2$ roots mod each prime power $p^k$.

Lemma $x^2-x \equiv 0$ has $2$ roots $\pmod {p^k}$.

proof: Clearly $x=0$ and $x=1$ are roots, as you have pointed out. We just need to show now that if $z$ is a root then $z=0$ or $z=1$. To prove that we can split into two cases: When $z|p^k$ and when $z$ is coprime to $p^k$. The coprime case is easy because $z$ is zero or invertible. For the case $z|p^k$: Put $z = p^h$ (with $h < k$) and consider $$p^{2h} - p^h \equiv 0 \pmod {p^k}.$$ this is impossible of $2h \le k$ so suppose $2h > k$, we have $k < 2h < 2k$ and $p^{2h-k} \equiv p^k$ but this implies $2h-k = k$, so $2h = 2k$, but this contradicts $h < k$.

Secondly we can use the chinese remainder theorem to put together the $2$ roots mod each prime power of $m$ to get $2^r$ roots mod $m$.

Lemma If $a,b$ are coprime then if $P(x)$ has $m$ roots mod $a$ and $n$ roots mod $b$ then it has $mn$ roots mod $ab$.

proof: Label the roots mod $a$ as $\{r_i\}$ and the roots mod $b$ as $\{s_j\}$ then the roots mod $ab$ are $\{(r_i, s_j) \}$ of which there are $|\{r_i\}|\cdot|\{s_j\}| = nm$.


Putting these two lemmas together lets you conclude: There are $2^r$ roots, where $r$ is the number of prime factors of $m$.

$\endgroup$
0
2
$\begingroup$

As I said in my comment above, we have $$ x^2 \equiv x \pmod m\\ x^2 - x \equiv 0 \pmod m\\ x(x-1) \equiv 0 \pmod m $$ What if $m$ was a prime $p$, how many solutions would the equation have? What if $m$ was the power $p^n$ of some prime? Here it pays off to think about divisibility and what being a prime means (hint: there are two solutions either way).

Now, for an $m$ that is not the power of a prime, then it can still be written as a product of such: $$ m = p_1^{n_1}\cdots p_k^{n_k} $$ At this point, you have either heard about the Chinese remainder theorem or you haven't. If you have, you should know what to do at this point, especially since I just told you about it. Assuming that $p_i \neq p_j$ when $i \neq j$, you get $k$ different congruence relations, each with $2$ solutions, which means that the total number of solutions to the original problem is...?

If you haven't heard about it, then I suggest reading up on it. It is a very important result in number theory and you shouldn't be without it. You could start here, or use google, or if you have a favourite textbook, it's probably in there as well.

$\endgroup$
5
  • 1
    $\begingroup$ This is what i understood. Correct me if I am wrong. $x(x-1) \equiv 0 mod m $ can be written as two equations $x \equiv 0modm $ or $ x \equiv 1modm$. Now if m is prime or not doesn't matter there would only one solution for each equation . $\endgroup$ – Yogesh Ghaturle Feb 18 '16 at 16:59
  • $\begingroup$ @YogeshGhaturle So either $x \equiv 0$ or $x \equiv 1$. That looks like two solutions to me. But if $m$ is composite, then there might be other solutions as well. For instance, in the case $m = 12$ you also have $x \equiv 4$ or $9$. $\endgroup$ – Arthur Feb 18 '16 at 17:02
  • $\begingroup$ How to solve using CRT for composite m. I am not getting these solution if I try to solve for m=12. Could you tell how did you reach this solution. I know that guessing could give me the answer. $\endgroup$ – Yogesh Ghaturle Feb 18 '16 at 17:18
  • $\begingroup$ Not prime matters. As x(x-1) = 0 = m mod m etc. If m = jk for example then x = j; x-1 = k (if possible) so if m = k(k+1) i.e. 6, 12, 20, 30 etc you can have solutions 2,3; 4,5 etc. Also as x(x-1) = 0 = km you could have (if possible x = km' and y = m/m'. For example if m = 10 then 20 = 4*5 so x =5 and x - 1 = 4 would be a solution. $\endgroup$ – fleablood Feb 18 '16 at 17:32
  • $\begingroup$ nice solution / hints ! It helped a lot $\endgroup$ – Sunaina Pati Nov 3 '20 at 12:16
2
$\begingroup$

So we get $x(x-1) \equiv \mod m$ so $m|x(x-1)$. If $m$ is prime then either $m|x$ and $x \equiv 0 \mod m$ or $m|x -1$ and $x \equiv 1 \mod m$.

But what if $m$ is not prime. If $m = \prod p_i^{k_i}$ then as $x$ and $x-1$ are relatively prime (they have only a difference of 1) then each $p_i^{k_i}|x$ or divides $x -1$.

In other words we need to find $x \equiv 0 \mod k$ and $x \equiv 1 \mod (j)$ where $m = j*k$ and $\gcd(j,k) = 1$ (Note if $m = \prod p_i^{k_i}$ there will by $2^i$ such sets of equations). According to the chinese remainder theorem there will be one solution to each set of problems. (So $2^i$ solutions total).

Example 1

Solve $x^2 = x \mod 12 \iff x(x-1) \equiv 0 \mod m$. $12 = 3 \times 4$ so there will be the following solutions:

A) $x \equiv 0 \mod 12$ and $x \equiv 1 \mod 1$ which has one solution. via CRT.

B) $x \equiv 0 \mod 1$ and $x \equiv 1 \mod 12$ which has one solution.via CRT.

C) $x \equiv 0 \mod 3$ and $x \equiv 1 \mod 4$ which has one solution.via CRT.

D) $x \equiv 0 \mod 4$ and $x \equiv 1 \mod 3$ which has one solution. via CRT.

The solution to A) is $x= 0$, B) is $x =1$, C) $x = 9$ D)$ x = 4$

Example 2

Solve $\ x^2 = x \mod 360$. $360 \equiv 8 \times 9 \times 5$ so there will be 8 solutions:

$ (x \equiv 0 \mod 360) \rightarrow x = 0$

$ (x \equiv 1 \mod 360) \rightarrow x = 1$

$ (x \equiv 0 \mod 8) \ AND \ \ (x \equiv 1\mod 45) \rightarrow x = 136$

$ (x \equiv 0 \mod 45) \ AND \ \ (x \equiv 1 \mod 8) \rightarrow x = 225$

$ (x \equiv 0 \mod 9) \ AND \ \ (x \equiv 1 \mod 40) \rightarrow x = 81$

$ (x \equiv 0 \mod 40) \ AND \ \ (x \equiv 1 \mod 9) \rightarrow x = 280$

$ (x \equiv 0 \mod 5) \ AND \ \ (x \equiv 1 \mod 72) \rightarrow x = 145$

$ (x \equiv 0 \mod 72) \ AND \ \ (x \equiv 1 \mod 5) \rightarrow x = 216$.

Which would have been practically impossible by trial and error.

$\endgroup$

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