Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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