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

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?

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

• q does not divide k. In fact k < q. I have updated my question. So such n always exist ? But how to find that n ? That's the first question. – Neel Basu Jun 12 '18 at 21:11

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.

• Yes n is always positive. And I am looking for a positive minimum – Neel Basu Jun 13 '18 at 6:22
• Have a look at the Wikipedia article I posted. You will see the boundary for $\min |y|$ there from which it should be easy to deduce the boundary for $\min |n_t|$. – rtybase Jun 13 '18 at 6:40
• Sorry I have gone through that page and I could not deduce any analytical form to figure out the minimum n. Can you please include that in your answer ? – Neel Basu Jun 13 '18 at 13:02
• Like $|y|\leq \left|\frac{a}{\gcd(a,b)}\right|$? Only in this case it's $|n|\leq \left|qk\right|$ – rtybase Jun 13 '18 at 13:08
• For Eq 1 to hold either of x or y has to be negetive. Because both p and q are positive. However in my problem everything is positive integer. I can't understand how it relates my problem. – Neel Basu Jun 14 '18 at 15:24