# solving modulo equation

How to solve this

$$x^a \equiv b \pmod n$$

I need to be able to find $x$, given $b$. $a$ is always $23407534262244700$ and $n$ is $465992738619896000$.

Someone mentioned I can use Fermat and Chinese Remainder Theorem together to solve this. Any ideas how?

-
If you want to use the Chinese Remainder Theorem, $465992738619896000= 2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 5\cdot 5\cdot 5\cdot 29\cdot 15107\cdot 132957529$. –  lhf Sep 20 '11 at 0:06
I would, but can't figure out how to use it. –  user16367 Sep 20 '11 at 0:20
You can reduce the exponent modulo $29$ to get the value modulo $29$ (since $x^{29}\equiv x \pmod{29}$ for all $x$), and solve the problem there. You can reduce it modulo $15107$ to get the answer modulo $15107$; and likewise with $132957529$. Modulo $125$ things are a bit trickier, as they are modulo $64$, but not too much. Does that help? –  Arturo Magidin Sep 20 '11 at 3:37
What do you mean 'reduce the exponent modulo'. I've tried finding solutions for x^a=b(mod 29), x^a=b(mod 15107), etc., but they don't always have solution. The original equation still has a solution, even if these do not. –  user16367 Sep 20 '11 at 10:03
If any of the congruences modulo the factors of $n$ has no solutions, then the original has no solutions: because if $q|n$, and $x^a\equiv b\pmod{n}$, then $n|x^a-b$, and therefore $q|x^a-b$, and therefore $x^a\equiv b\pmod{q}$. So it is false that the original can have solution if one of the congruences modulo the factors of $n$ has no solutions. –  Arturo Magidin Sep 20 '11 at 13:44
show 1 more comment

You claim that some of the congruences $x^a\equiv b\pmod{29}$, $x^a\equiv b\pmod{15107}$, etc. have no solutions while the original congruence does. That's impossible.

If $a\equiv b\pmod{n}$, and $m|n$, then $a\equiv b\pmod{m}$: for the former means that $n|b-a$, and if $m|n$, then $m|b-a$, hence $a\equiv b\pmod{m}$. So if the original congruence has a solution, then since $29|n$ and $15107|n$, etc., all those congruences have solutions. Conversely, if any of those congruences does not have a solution, then the congruence modulo $n$ has no solutions.

Now suppose that $n=rs$, with $\gcd(r,s)=1$. Then $y\equiv b\pmod{n}$ is if and only if $y\equiv b\pmod{r}$ and $y\equiv b\pmod{s}$, because for $\gcd(r,s)=1$, you have that $rs|b-y$ if and only if $r|b-y$ and $s|b-y$.

So one strategy is to use the factorization of the modulus, $$n = 2^6\times 5^3\times 29\times 15107\times 132957529,$$ and solve the congruences \begin{align*} x^a &\equiv b \pmod{2^6}\\ x^a &\equiv b \pmod{5^3}\\ x^a &\equiv b\pmod{29}\\ x^a&\equiv b \pmod{15107}\\ x^a &\equiv b \pmod{132957529} \end{align*} If you could find an $x$ that solves each of these congruences, that $x$ would solve the congruence modulo $n$.

But that is perhaps too much to be expected. What you might hope is to find one $x$ that solves the first congruence, call it $x_1$; one $x_2$ that solves the second, and so on. Well, then you can use the Chinese Remainder Theorem to find a single $x$ such that \begin{align*} x &\equiv x_1 \pmod{2^6}\\ x &\equiv x_2 \pmod{5^3}\\ x &\equiv x_3 \pmod{29}\\ x &\equiv x_4 \pmod{15107}\\ x &\equiv x_5 \pmod{132957529} \end{align*} And then that $x$ will solve all the congruences, and hence solve the original.

So that's the general strategy.

For the modulii $29$, $15107$, and $132957529$, you can use Fermat's Little Theorem: if $p$ is a prime, then $x^p\equiv x\pmod{p}$ for all $x$, and for $\gcd(x,p)=1$, $x^{p-1}\equiv 1 \pmod{x}$

So, for example, for $p=29$, you would check if $b\equiv 0\pmod{29}$ or not. If $b\equiv 0\pmod{29}$, then $x$ must be $0\bmod 29$ and you are done. If $b$ is not a multiple of $29$, then $x$ cannot be a multiple of $29$. Since $$a = 23407534262244700 =835983366508739\times 28 + 8 \equiv 8\pmod{28}$$ then $$x^a =x^{835983366508739\times 28 + 8} = (x^{28})^{835983366508739}x^8 \equiv 1^{835983366508739}x^8\equiv x^8\pmod{29}$$ by Fermat's Little Theorem; so you really want to solve $$x^8\equiv b\pmod{29}.$$ This will likely be a lot simpler than the original. You'll get a certain number of solutions, or that there is no solution. If there is no solution, you are done: there is no solution to the original.

For the moduli $5^3$ and $2^6$, things are a bit more complicated. If $b$ is odd, then you can use Euler's generalization to Fermat's Little Theorem, for $2^6$ says that if $x$ is odd, then $x^{2^5}\equiv 1\pmod{2^6}$ (in general, if $\gcd(x,n)=1$, then $x^{\varphi(n)}\equiv 1 \pmod{n}$, where $\varphi(n)$ is Euler's Totient function). If $b$ is even, then $x$ will have to be even and you can reduce the problem a bit.

Likewise, for $5^3$, if $b$ is not a multiple of $5$, then you can use the fact that $x^{100}\equiv 1\pmod{5^3}$ for every $x$ that is not a multiple of $5$. If $b$ is a multiple of $5$, then you know $x$ must be as well, and you can reduce the problem.

Once you have determined solutions for each of the five congruences (modulo $2^6$, $5^3$, $29$, $15107$, and $132957529$) each way to select one solution from each moduli will give you, via the Chinese Remainder Theorem, a solution to the original equation.

-
Thanks a lot for this. I've managed to use Chinese Remainder Theorem to combine the results of the smaller equations. Using Fermat's theorem is a nice trick. It doesn't help me a lot, though. I'm using this in a program and it computes the powers fast using squaring, so if a is 8 or 2 million, it's not a big difference for the computer. –  user16367 Sep 20 '11 at 17:01