Splitting congruence equation? $x^2 \equiv x \pmod {b^m}$

modular arithmetic

I have this equation

$x^2 \equiv x \pmod {b^m}$

Now I have found something interesting. I could somehow "split" this, but I don't quite understand if it is always working and how to prove it.

Here is what I have done:

First I factorize $b$ into its canonical form:

$b = \prod \limits_{i=1}^{\omega(b)} (p_i)^{(e_i)}$

(with $\omega(b)$ being the number of unique prime factors and $p_i$ being a prime and $e_i$ being the valuation.)

I found out that I can calculate $x$ with this congruence equation:

\begin{matrix}
x & \equiv & a_1 & \pmod {({p_1}^{e_1})^m} \\
x & \equiv & a_2 & \pmod {({p_2}^{e_2})^m} \\
& \vdots & & \\
x & \equiv & a_{\omega(b)} & \pmod {({p_{\omega(b)}}^{e_{\omega(b)}})^m} \\
\end{matrix}

I have found out that if I define $a_i = \{0,1\}$ and apply the congruence equation with all possible $(a_1, a_2, …, a_{\omega(b)})$ permutations, I get all $x$ solutions from the initial quation.
$x^2 \equiv x \pmod{b^m}$

Example for $b=10$

$b = 10 = 2^1 \cdot 5^1$

Therefore:

\begin{matrix}
x & \equiv & a_1 & \pmod {(2^1)^m} \\
x & \equiv & a_2 & \pmod {(5^1)^m} \\
\end{matrix}

The $(a_1, a_2)$ permutations generate different branches:

  • Tuple $(0,0)$ generates branch 0 (only one element: $\{0\}$ for all
    $m$)

  • Tuple $(0,1)$ generates branch 6 (elements $\{6, 76, 376, …\}$ for
    $m=1,2,3,…$)

  • Tuple $(1,0)$ generates branch 5 (elements $\{5, 25, 625, …\}$ for
    $m=1,2,3,…$)

  • Tuple $(1,1)$ generates branch 1 (only one element: $\{1\}$ for all
    $m$)

Questions:

(1) Can you please help me understand why this is the case and how to prove it?

(2) What do I need to do, to make it work with
$x^q \equiv x \pmod {b^m}$ as well ?

Best Answer

You have the congruence equation

$$\begin{equation}\begin{aligned} x^2 & \equiv x \pmod {b^m} \\ x^2 - x & \equiv 0 \pmod {b^m} \\ x(x - 1) & \equiv 0 \pmod {b^m} \end{aligned}\end{equation}\tag{1}\label{eq1A}$$

Consider your prime decomposition of

$$b = \prod \limits_{i=1}^{\omega(b)} (p_i)^{(e_i)} \tag{2}\label{eq2A}$$

Note $\gcd(x, x - 1) = 1$. Thus, each $({p_i}^{e_i})^m$, for $1 \le i \le \omega(b)$, must divide into either just $x$, giving that $x \equiv 0 \pmod{({p_i}^{e_i})^m}$; or $x - 1$, giving that $x \equiv 1 \pmod{({p_i}^{e_i})^m}$. This is basically equivalent to what your set of congruence equations represents, and shows why they give all of the solutions.

As for using $x^q$ for some $q \gt 2$ instead of $x^2$, note you will then get

$$\begin{equation}\begin{aligned} x^q & \equiv x \pmod {b^m} \\ x^q - x & \equiv 0 \pmod {b^m} \\ x(x^{q-1} - 1) & \equiv 0 \pmod {b^m} \\ x(x - 1)(\sum_{i = 0}^{q-2}x^i) & \equiv 0 \pmod {b^m} \\ \end{aligned}\end{equation}\tag{3}\label{eq3A}$$

Now you have $3$ values to consider instead of $2$. Also, another complication is that although $\gcd(x, \sum_{i = 0}^{q-2}x^i) = 1$, it's not always true that $x - 1$ is relatively prime to $\sum_{i = 0}^{q-2}x^i$. For example, if $x - 1 = 2 \implies x = 3$ and $q = 3$, then $\sum_{i = 0}^{q-2}x^i = 1 + x = 1 + 3 = 4$. As such, I don't see any relatively simple way to extend your technique to handle cases where $q \gt 2$.

Related Question