2
$\begingroup$

I am about to solve the following congruence for $x$: $$\begin{align*} x^n\equiv x&\pmod m\quad(1)\end{align*}$$

Where $n\in\mathbb{N},$ and $n$ is coprime to $m$ and $x\in \{0,1,2\dots,m-1\}$.

Another question here, which is almost similar to this one, has already answers for $m\in\text{Primes}$. But I would like to consider a wider case where $m$ can be any odd number which is coprime to $n$. Please guide me if you know of methods for solving this congruence. I think I have to start with checking to see if a solution exists for a given $m$ and $n$.

Examining all possible $x$ is not an option because $m$ is supposedly very big integer.

As a small integer illustration I have calculated (programmatically) $x=69, 70, 91, 92$ for the following congruence (total 4 solutions): $$\begin{align*} x^{158}\equiv x&\pmod {161}\quad(2)\end{align*}$$

please note that we cannot reduce $(2)$ to the following form: $$\begin{align*} x^{157}\equiv 1&\pmod {161}\quad(3)\end{align*}$$ because it seemingly has no solutions because solutions above have no modular inverse modulo $161$.

#EDIT 1: Using chinese remainder theorem is not an option here. Because $p$, as I have mentioned above, is supposed to be a very large integer for which we don't know the factors.

$\endgroup$
6
  • 1
    $\begingroup$ Do you know the Chinese remainder theorem? $\endgroup$ Aug 9, 2021 at 21:30
  • $\begingroup$ $69^{158}\not\equiv69\bmod 161$ and $91^{158}\not\equiv91\bmod 161$, but $70$ and $92$ are solutions, as are $0$ and $1$ $\endgroup$ Aug 9, 2021 at 21:38
  • $\begingroup$ @J.W.Tanner It is not an option for large integers. Because factorization is not feasible. $\endgroup$
    – PouJa
    Aug 10, 2021 at 12:23
  • $\begingroup$ I see that you have edited your question to change the exponent from $158$ to $159$, and also edited my answer to change the exponent. However you did not change my work, and now my answer is wrong. Don't do that. If you must make a significant change, ask a new question. There are $9$ solutions when the exponent is $159$, as there are three solutions each mod $7$ and $23$. I'm reverting both the question and my answer. $\endgroup$
    – davidlowryduda
    Aug 10, 2021 at 14:44
  • $\begingroup$ @davidlowryduda Sorry I made a mistake. I thought this way I can fix my original typos. when the exponent is equal to 159 I calculated using a python code all values $x\in \{0,1,2\dots,m-1\}$ and only 4 solutions were returned. How is it 9 solutions there? $\endgroup$
    – PouJa
    Aug 10, 2021 at 14:53

1 Answer 1

3
$\begingroup$

As $161 = 7 \cdot 23$, a modular equation modulo $161$ can be determined (by the Chinese Remainder Theorem) from its behavior mod $7$ and mod $23$.

The theme is that you solve this for each prime separately and then combine the answers together.

For your particular example, solving $x^{158} \equiv x \bmod 161$ reduces to solving $$\begin{align} x^{158} &\equiv x \bmod 7, \\ x^{158} &\equiv x \bmod 23. \end{align}$$ By Fermat's Little Theorem, these are equivalent to

$$\begin{align} x^{2} &\equiv x \bmod 7, \\ x^{4} &\equiv x \bmod 23. \end{align}$$

Using your preferred methods (possibly using the ideas in this question and its answers), you can see that the answers to these are

$$\begin{align} x &\equiv 0, 1 \bmod 7, \\ x &\equiv 0, 1 \bmod 23. \end{align}$$

As $4 \cdot 23 \equiv 1 \bmod 7$ and $10 \cdot 7 \equiv 1 \bmod 23$, the Chinese Remainder Theorem indicates that the solutions to these pair of congruences take the form

$$ a \cdot 7 \cdot 10 + b \cdot 23 \cdot 4 \bmod 161,$$

where $a, b \in \{0, 1\}$. These are

$$0, 1, 70, 92.$$

(I'll note that your solutions $69$ and $91$ are not actually solutions to the congruence).

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. For small integers where factorization is feasible it is correct. But when it comes to large integers that are not easy to factorize we cannot use the chinese remainder theorem, $\endgroup$
    – PouJa
    Aug 10, 2021 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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