Help finding the common factor of $q^{n-1}-p$ and $kq-p$

Question

let $p,q$ be 2 non-zero coprime integers,$n\in\mathbb{Z}>1$ and $k$ any integer. For what $k$ do $q^{n-1}-p$ and $kq-p$ have a common factor?

So far, I have been able to come up only with the obvious solution $k=q^{n-2}$ by brute force. Please help.

Answer 1

From the way the problem is stated I understand that for given $p,q,n$ you want to find the $k$' which work.

Hint If $d \neq 1$ is a divisor of $q^{n-1}-p$ then $d$ is a common factor if and only if

$$kq \equiv p \pmod{d} \,.$$

Now, using the coprime condition you can prove that $p$ and $d$ must also be coprime, therefore $p$ is invertible $\mod{d}$.

This shows that $$k \equiv q^{-1}p \pmod{d}$$ for some divisor $d \neq 1$ of $q^{n-1}-p$.