1
$\begingroup$

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?

  • 0
    Moreover, if $q$ and $r$ are relatively prime, and you can find $x$ such that $x^a\equiv b\pmod{q}$ and $x^a\equiv b\pmod{r}$, then it follows that $x^a\equiv b\pmod{qr}$; because if $\gcd(q,r)=1$, and $q|(x^a-b)$ and $r|(x^a-b)$, then $qr|(x^a-b)$. So solving $x^a\equiv b\pmod{n}$ is equivalent to solving the system of congruences modulo the prime power factors of $n$, to wit $2^6$, $5^3$, $29$, $15107$, and $132957529$. By Fermat's Little Theorem, $x^p\equiv x\pmod{p}$ for any prime $p$, so if $a\equiv a'\pmod{p}$, then $x^a\equiv x^{a'}\pmod{p}$.2011-09-20

1 Answers 1

1

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.

  • 0
    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.2011-09-20