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