I know that Dirichlet's theorem says that there are infinitely many primes $p$ such that $p\equiv a$ (mod $n$) when gcd$(a,n)=1$. I'm wondering more generally about a system of power congruences

$x^{k_1}\equiv a_1$ (mod $n_1$)

$x^{k_2}\equiv a_2$ (mod $n_2$)


$x^{k_m}\equiv a_m$ (mod $n_m$)

Given fixed positive integers $k_i,a_i,n_i$ as above, is there a condition, e.g., $gcd(a_i,lcm(n_1,\ldots,n_m))=1$, that guarantees the existence of infinitely many primes $p$ such that $p^{k_i}\equiv a_i$ (mod $n_i$) for all $1\leq i\leq m$?

Maybe this should be a separate post, but I'm also wondering about conditions that guarantee that the above system has any solutions $x\in\{0,1,\ldots,L-1$}, prime or not, where $L=lcm(n_1,\ldots,n_m)$.

  • $\begingroup$ There are many variables here. Is $x$ the desired prime number ? Which of those variables are assumed to be given ? $\endgroup$
    – Peter
    Commented Feb 2, 2023 at 9:00
  • $\begingroup$ I'll edit the post. $\endgroup$ Commented Feb 2, 2023 at 9:02
  • 2
    $\begingroup$ I don't think there's any simple condition on $n$ guaranteeing there's a solution to $x^3\equiv2\bmod n$. But if $n$ is odd, and if there is a solution, then Dirichlet guarantees there's a solution with $x$ being prime. $\endgroup$ Commented Feb 2, 2023 at 10:19
  • 1
    $\begingroup$ Why did you delete your previous similar question? Your congruences constraints are equivalent to $x \bmod L \in S$ for some finite subset $S\subset 0\ldots L-1$ that you have to compute. Then the density of primes satisfying those congruences is $\frac{\# A}{\phi(L)}$ where $A = \{ s\in S, \gcd(s,L)=1\}$ and if $A=\emptyset$ then only finitely primes satisfy it (as they'll divide $L$). $\endgroup$
    – reuns
    Commented Feb 2, 2023 at 11:00
  • $\begingroup$ I deleted that one because it was a slight variant of - yet another - question that I'd posted previously. I think I understand everything now. Thank you. $\endgroup$ Commented Feb 2, 2023 at 12:18

1 Answer 1


(1) Assume $(a_i,n_i)=1$.
Solve each $$x^{k_i}\equiv a_i\pmod {n_i}$$ individually, see this.

Let $x\equiv b_i\pmod {n_i}$ be one of the solutions with $(b_i,n_i)=1$.

(2) Assume $(n_i,n_j)=1$, for all $i\neq j$.

Then it becomes $$\left\{\begin{align} x&\equiv b_1\pmod {n_1}\\ &\vdots\\ x&\equiv b_s\pmod {n_s} \end{align}\right.$$ Then use the Chinese Remainder Theorem, the solution is unique with $$x\equiv c\pmod{ \prod_{i=1}^s n_i}.$$

(3) To have infinitely many prime solutions, we only need $$(c,\prod_{i=1}^s n_i)=1.$$ We see that $(c,\prod_{i=1}^s n_i)=1$ if and only if $$(c,n_i)=1\iff (b_i,n_i)=1,\quad i=1,\ldots,s,$$ which follows from (1).

(4)In conclution, with $(a_i,n_i)=1$ and $(n_i,n_j)=1$ $(1\leq i\neq j\leq s)$, if the system of congruences has a integer solution, then it has infinitely many prime solutions.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .