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


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.

  • $\begingroup$ I agree with everything, except the following: "we go back to the previous case". Could you be more explicit? $\endgroup$ – Paolo Leonetti Mar 24 at 15:15
  • $\begingroup$ 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}}$. $\endgroup$ – TBTD Mar 24 at 15:20
  • $\begingroup$ The fact is that $m$ may depend on, at most, one $a_j^\prime$.. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.