# Solving for $x$ in $x^k \equiv b \pmod n$ where $n$ is not prime and $\gcd(k, \phi(n)) > 1$

How does on solve for $x$ in

$x^k \equiv b \pmod n$

where $n$ is not prime and $\gcd(k,\phi(n)) > 1$

Can this be done using Euler's theorem and totient function?

-
Do you mean $\gcd(n,x) > 1$? –  Mikko Korhonen Oct 13 '11 at 14:48
No. There is a method to solve a congruence where you use the equation $ku - \phi(n)v = 1$ and find $u$ and $v$. Then use those numbers to solve for $x$. This method does not work, however, when $gcd(x,n) > 1$. –  redwoolf Oct 13 '11 at 14:53
ehh yeah, nevermind, I read that wrong. –  Mikko Korhonen Oct 13 '11 at 15:01
$x^k \equiv x^{k-\phi(n)}$, where $\phi(n)$ is Euler's totient function. At least as long as $x$ and $n$ are coprime. So you can assume that $k$ is smaller than $\phi(n)$. That is as much as the theorem and totient function can help you. –  Arthur Oct 13 '11 at 15:48
Which $\gcd$ is $>1$? In the post it is $\gcd(n,k)$, in a comment it is the puzzling $\gcd(x,n)$. But the equation $ku-\varphi(n)v=1$ implies $\gcd(k, \varphi(n))=1$, which raises the possibility that your assumption is meant to be the more natural $\gcd(k,\varphi(n))>1$. –  André Nicolas Oct 13 '11 at 16:11

The answer is probably no. Even for the simpler congruence
$$x^2 \equiv b \pmod{p}$$ with $p$ prime I don't know of any direct way to solve it except in exceptional cases (Though there are fast probabilistic algorithms to find it as Tonnelli and Shank's and also Schoof's algorithm which works in deterministic polynomial time algorithm). To solve your congruence I would do as follows:

I assume that $\gcd(b,n)=1$. Let $d = \gcd(k,n)$, and find $u,v$ such that $uk + v\phi(n) = d$. powering the congruence to the $u$-th power we get the congruence $$x^d \equiv b^u \pmod{n}$$ now if $b^{u\phi(n)/d} \not \equiv 1 \pmod{n}$ then you know that there is no solution (because the left hand side is $\equiv 1 \pmod{n}$.

If $b^{u\phi(n)/d} \equiv 1 \pmod{n}$ then you are not sure if there are solutions or not. To check it you should factor $n$ as a product of prime powers, $n = \prod p^t$.

Now, there are solutions to the orignial congruence if and only if for every prime power factor $p^t$ of $n$, we have $$b^{u \phi(p^t)/d'} \equiv 1 \pmod{ p^t} \quad \text{with } d' = \gcd(d,\phi(p^t))$$ if any of this congruence fails then there are no solutions.

The problem is reduced to find solutions to each congruence $$x^d \equiv b^u \pmod{p^t}$$ and then combine them using the Chinese reminder theorem.

Using the same argument that above we can reduce this to the congruence $$x^{d'} \equiv b' \pmod{p^t} \quad\text{ for certain }b'\text{ with }\quad b^{\phi(p^t)/d'} \equiv 1 \pmod{p^t}$$

In the affirmative case then the congruence $$x^{d'} \equiv b' \pmod{p^t}$$ has exactly $d'$ solutions, that is the polynomial $P(x) = x^{d'} - b'$ is the product of $d'$ linear factors, I don't know of any algorithm that factors modulo $p^t$ in guaranteed polynomial time but there are fast probabilistic ways ways to solve it, for example you can compute polynomial $\gcd$'s using several random values $a$ not divisible by $p$: $$\gcd( (x+a)^{\phi(p^t)/d'}-1, P(x) )$$ and using the results to descompose recursively the polynomial $P(x)$ in smaller ones until you get the linear factors.

-