Minimum value of $n$ such that $nq+k$ is divisible by $p$

Question

Given two primes $p$ and $q$ where $q > p$ and a positive integer $k<q$, if $nq+k$ is divisible by $p$ then what's the minimum value of $n$ if one such $n$ exists?

Also do there exist any $k$ such that $nq+k$ is never divisible by $p$ for any $n$? If such $k$ exists how to find that?

Answer 1

For your second question, Dirichlet's theorem on prime in arithmetic progressions tells us that if $q$ does not divide $k$ then there exists $n$ such that $p$ divides $nq+k$.

Answer 2

Using Bezout's lemma we have $\gcd(p,q)=1 \Rightarrow \exists x,y \in \mathbb{Z}$ s.t. $$xp+yq=1 \tag{1}$$ or $$kxp+kyq=k \Rightarrow p \mid (-ky)q+k \tag{2}$$ Moreover, if $(x_0,y_0)$ satisfies $(1)$ then $(x_0+tq,y_0-tp)$ satisfies $(1)$ as well, $\forall t\in \mathbb{Z}$. Then $(kx_0+ktq,ky_0-ktp)$ will satisfy $(2)$ and $n_t=ktp-ky_0$. As a result, there will be an infinity of $n_t$ s.t. $p \mid n_tq+k$, both positive and negative. So, looking for a minimum may be troublesome, unless we are looking for a positive minimum.

This also answers the 2nd question, no such $k$ exists. If it existed, all of the above would lead to an immediate contradiction.