Number of solutions for $x^2 \equiv x \pmod m$

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


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.


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.

Tags:

Congruences

Related

Proof of equivalence of conformal and complex structures on a Riemann surface. What's $\alpha+\beta$ if we have: $\alpha^3-6\alpha^2+13\alpha=1$ and $\beta^3-6\beta^2+13\beta=19$ ($\alpha$ and $\beta$ are Real) Computing $\sum _{ k=1 }^{ \infty }{ \sum _{ n=0 }^{ \infty }{ \frac { 1 }{ { k\left( k+n \right) }^{ 2 } } } } $ How to evaluate $\displaystyle \int_{0}^{\infty }\frac{\cos x}{\left ( x^2+a^{2} \right )\left ( x^2+b^{2} \right )}~\mathrm{d}x$ Prove $\frac{a^3+b^3+c^3}{3}\frac{a^7+b^7+c^7}{7} = \left(\frac{a^5+b^5+c^5}{5}\right)^2$ if $a+b+c=0$ Convergence of the powers of a Markov transition matrix Polynomials that pass through a lot of primes Pattern in twin primes Circle enclosing all but one of $n$ points A combinatorial proof of the identity $\sum\limits_{k=0}^n\binom{2k}{k}\binom{2(n-k)}{n-k}=4^n$ Determine $x$ such that $\lim\limits_{n\to\infty} \sqrt{1+\sqrt{x+\sqrt{x^2…+\sqrt{x^n}}}} = 2$ Are there Möbius transformations of arbitrary group-theoretic order?

Recent Posts