0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Neel Basu Jun 12 '18 at 21:11
0
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Yes n is always positive. And I am looking for a positive minimum $\endgroup$ – Neel Basu Jun 13 '18 at 6:22
  • $\begingroup$ 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|$. $\endgroup$ – rtybase Jun 13 '18 at 6:40
  • $\begingroup$ 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 ? $\endgroup$ – Neel Basu Jun 13 '18 at 13:02
  • $\begingroup$ Like $|y|\leq \left|\frac{a}{\gcd(a,b)}\right|$? Only in this case it's $|n|\leq \left|qk\right|$ $\endgroup$ – rtybase Jun 13 '18 at 13:08
  • $\begingroup$ 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. $\endgroup$ – Neel Basu Jun 14 '18 at 15:24

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.