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

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$$.

## 2 Answers

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'. 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.

• I agree with everything, except the following: "we go back to the previous case". Could you be more explicit? – Paolo Leonetti Mar 24 at 15:15
• Take $q=Q\prod_{j\in S}p_j^{a_j'/m}$ with $(Q,p_j)=1, \forall j\in S$, where $j\in S$ iff $p_j\mid k$, and $a_j'=v_{p_j}(k)<v_{p_j}(n)$. This would ensure, for every $j\in S$, it holds that $pq^m \equiv k\pmod{p_j^{a_j}}$. For $i\notin S$, $p_i\ nmid k$, and in this case, set $p\equiv (\prod_{j\in S}p_j^{a_j'/m})^{-1}\cdot k\pmod{p_i^{a_i}}$. CRT + Dirichlet shows existence of such a prime, and let $Q\equiv 1\pmod{p_i^{a_i}}$. – TBTD Mar 24 at 15:20
• The fact is that $m$ may depend on, at most, one $a_j^\prime$.. – Paolo Leonetti Mar 24 at 15:22

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.