3

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 ?

user26857
  • 52,094
Daniel Marschall
  • 265
  • 2
    Chinese Remainder Theorem? – Angina Seng Dec 26 '19 at 11:48
  • @LordSharktheUnknown I understand that the Chinese Remainder Theorem can be used to solve the congruence equation, but that is not my question. I cannot see how the splitting (or however I should call it) works and if it is correct at all. – Daniel Marschall Dec 26 '19 at 11:54
  • Why can't $x^2\equiv x\pmod{p^m}$ have more solutions other than $0,1$ if $m>1$? – Berci Dec 26 '19 at 11:57
  • $x$ does have more solutions (for $b=10$ and $m=1$ : 0,1,5,6 and for $m=2$ they are 0,1,25,76, ...) . I found out that $a_i$ has to be $a_i = {0,1}$ . With the permutations of $(a_1, a_2)$, I get the different partial results : $(0,0)$ gives $0$ and $(0,1)$ gives $6$ and $(1,0)$ gives $5$ and $(1,1)$ gives $1$ . – Daniel Marschall Dec 26 '19 at 12:00
  • (I have added an example for $b=10$) – Daniel Marschall Dec 26 '19 at 12:10
  • You can change it and split it potentially infinitely many ways ... why should we care ? –  Dec 26 '19 at 15:34
  • @RoddyMacPhee There is a specific reason why I want the form with the "branches" (permutations as $a_i$) instead of the one-line expression at the very top. But I don't want to include unnecessary much information into this question which has nothing to do with the question itself. The question itself is very clear, I think: Is that splitting correct and how can it be proven, and can I somehow do it for $x^q$, or is it only possible with $x^2$ . – Daniel Marschall Dec 26 '19 at 18:46

1 Answers1

1

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

John Omielan
  • 47,976
  • Thank you very much for your answer! It helped me very much. There is just one part which I didn't fully understand. You write "Thus, each $({p_i}^{e_i})^m$, for $1 \le i \le \omega(b)$, must divide into either just ..." . Why is that? – Daniel Marschall Dec 27 '19 at 12:50
  • @DanielMarschall You're welcome for my answer. As for my statement you're asking about, it's due to $\gcd(x, x - 1) =1$ (i.e., $x$ and $x-1$ have no common factors between them) I mentioned earlier. Since $x(x -1) \equiv 0 \pmod{b^m}$, every factor of $b^m$ must divide into $x(x-1)$. Take any $p_i$ prime factor. It must divide either $x$ or $x - 1$. However, all of the $p_i$ factors must divide the same value, i.e., you can't have one $p_i$ factor divide $x$ & another divide $x - 1$. This is why I wrote my statement you're asking about. I hope this is now more clear to you. – John Omielan Dec 27 '19 at 17:00