Existence of solutions for $pq^m \equiv k\bmod{n}$

Question

Let $k,n$ be positive given positive integers. Is it true that there exist a prime $p$ and a perfect power $q^m$ (with $q\ge 1, m\ge 2$) such that $$ pq^m \equiv k\bmod{n}\,\,\,? $$

---

Partial observations. The solution is positive if:

1. If $k$ is coprime with $n$ the answer is positive: choose $q=1$ and use the prime number theorem in arithmetic progressions.

2. If $n$ is a power of a prime, let us say $n=r^t$ with $r\ge 3$ a prime and $t\ge 1$. By point 1, let us assume that $k=rh$ with $h\ge 1$. Set $p=r$, then the congruence becomes: $$ q^m \equiv h\bmod{r^{m-1}} $$ If $h$ is not a multiple of $r$ then just choose a primitive root $q$ in $\mathbf{Z}_r$ and a suitable $m$. Otherwise $h=r^ij$ with $i\ge 1$ and $j$ coprime with $r$. If $i\ge m-1$ choose $q=r$. Otherwise $i \in [1,m-2]$ and the congruence becomes $$ q^m \equiv r^i j \bmod{r^{m-1}}. $$ By force $r^i$ divides $q^m$. And, this case (i.e., choosing $p=r$) is impossible if $i=1$ and $m-1 \ge 2$.

Answer 1

Paolo: I believe the answer is yes. Here is a sketch.

Let $n=\prod_{j=1}^K p_j^{a_j}$. We shall prove that, for any fixed $k,n$ with $n$ having the prime decomposition above, there is a prime $p$, and integer $q$, and a positive integer $m$, such that $pq^m \equiv k\pmod{p_j^{a_j}}$, for every $1\leq j\leq K$.

Fix a prime $p_j\mid n$. Assume first that, $(k,p_j)=1$, for every $j$. Now, the construction is as follows. We will let the prime $p$ to have $p\equiv k\pmod{p_j^{a_j}}$, for every $j$. Existence of such a prime follows from Chinese remainder theorem, and Dirichlet's theorem on arithmetic progressions. Having chosen $p$, it now remains to construct $q$. For this, simply take $q\equiv 1\pmod{n}$.

Now, we inspect the case, if $k\equiv 0\pmod{p_j}$ for some of $j\in \{1,2,\dots,K\}$. If the largest power of $p_j$ dividing $k$ is at least $a_j$, the exponent in $n$, life is good; we can simply let $q\equiv 0\pmod{p_j^{a_j}}$, and construct $p$, by simply focusing on primes $p_j\mid n$ with $(p_j,k)=1$, and using the case CRT+Dirichlet construction. To finish construction of $q$, we set $q\equiv 1\pmod{p_j^{a_j}}$ if $p_j\nmid k$, and $q\equiv 0\pmod{p_j^{a_j}}$, and apply CRT.

The only case that remains is, what if $p_j\mid k$ such that, the largest exponent of $p_j$ dividing $k$ is strictly smaller than $a_j$? Now, suppose $p_j^{a_j}\mid \mid n$, and $p_j^{a_j'}\mid \mid k$ with $a_j'<a_j$. Letting $k=p_j^{a_j'}k'$ with $p_j\nmid k'$, the requirement is: $$ p_j^{a_j}\mid pq^m - p_j^{a_j'}k'. $$ Now, if the largest power of $p_j$ dividing $pq^m$ has to be exactly $a_j'$, otherwise, this condition is void. For that, it has to hold that, $m\mid a_j'$ (or else, $a_j\equiv 1\pmod{m}$, in which case we set $m=p_j$. Notice also that, there can be at most one such prime). Now, let $q=p_j^{a_j'/m}q'$ with $p_j\nmid q'$, we go back to the previous case.

Answer 2

The answer is no. (This was too long for a comment; the main credit goes to Aaron.)

I continue from Aaron's centered formula at the end: $$ p_j^{a_j} \mid pq^m-p_j^{a_j^\prime}k^\prime $$ for every $j$ such that $a_j^\prime < a_j$. At this point, for such indexes $j$, we need to have that the $p_j$-adic valuation of $pq^m$ is exactly $a_j^\prime$. Suppose for the moment that $a_j^\prime \ge 2$. We have two possibilities: Case 1: $p_j$ divides both $p$ and $q$. Case 2: $p_j$ divides only $q$.

In the first case, we are fixing $p=p_j$ and we are left with the condition $p^{a_j^\prime-1}|| q^m$. However, this happens for at most one index $j$ of this type.

In the second case, we have $p\neq p_j$ (which holds for all $j$ of this type but at most one) and $p_j^{a_j^\prime}|| q^m$, hence in particular $m \mid a_j^\prime$. In particular, since $m\ge 2$ then $m=a_j^\prime$ if $a_j^\prime$ is prime.

Counterexample. The congruence $pq^m \equiv 2^2\cdot 3^3 \cdot 5^5\bmod{(2\cdot 3\cdot 5)^6}$ has no solutions.