Solving a system of modular power congruences

Question

I have to find the $x$ value such that $x^k \equiv a_1 \pmod n$ and $x^q \equiv a_2 \pmod n$, where $k$, $q$, $a_1$, $a_2$ are known constants and $n$ is any number. Is there a method to find $x$ better than brute force approach?.

Answer 1

Particular case If $gcd(k,q)=1$ and $a_1,a_2$ are invertible, then the problem is easy to solve.

Write $1=kl+qm$ for integers $m,n$. Then $$x=x^1=x^{kl}x^{qm}=a_1^la_2^m \pmod{n}$$

Note that this works as long as one of $a_1, a_2$ is invertible, as $m,n$ can always be chosen so that one is positive and the other one is negative (with the choice belonging to the solver).

If neither is invertible, you can find positive integers $m,n$ so that $$kl=1+mq$$

Then $$a_1^l=x^{kn}=x x^{qm}=x a_2^m \pmod{n}\,.$$

Now this is a linear equation modulo $n$ and it is well known how to solve.

General case If $gcd(k,q)=d$ and $a_1,a_2$ are invertible, then exactly as before

Write $d=kl+qm$ for integers $m,n$. Then $$x^d=x^{kl}x^{qm}=a_1^la_2^m \pmod{n}$$

As $d|k,q$ we can write $k=dk', q=dq'$ and therefore, there is a solution if and only if $$\left( a_1^la_2^m \right)^{k'}=x^k = a_1 \pmod{n}$$ and $$\left( a_1^la_2^m \right)^{q'}=x^q = a_2 \pmod{n}$$

In this case, your system is equivalent to solving the single equation $$x^d=a_1^la_2^m \pmod{n}$$

If $a_1,a_2$ are not invertible, exactly as before you can find some positive $l,m$ so that $kl=d+qm$. Then $$a_1^l=x^d a_2^m \pmod{n}\,.$$

Now this is a linear equation modulo $n$ and it is well known how to solve.

Then proceed exactly as in the previous case.