# Using Dirichlet's theorem to show existence of number coprime to $n$

I have the following question: Let $$n$$ be a positive integer and $$d$$ be divisor of $$n$$. Use Dirichlet's theorem to show that there exists an integer $$k$$, where $$1\le k\le d-1$$ such that the number $$m:=1+\frac{nk}{d}$$ is coprime to $$n$$.

My idea is to show that if we can find such a $$m$$ that is prime, then $$m$$ is coprime to $$n$$ necessarily. Let us suppose on the contrary for all $$k=1,\cdots, d-1$$, the number $$m$$ is not prime. Then (perhaps?) This will show that there exists finitely many numbers of the form $$1+\frac{nk}{d}$$ that is not prime, contradicting Dirichlet's theorem. I am stuck here. Any ideas how to proceed?

• Dirichlet's theorem is not necessary. Try using Chinese remainder theorem. – i707107 Apr 18 at 3:03
• @i707107 the question insists we use Dirichlet's theorem so I would like to see an approach on that method though. Thanks for the comment nonetheless! – thedilated Apr 18 at 3:26
• @thedilated As my answer shows, what you're asking to prove is not necessarily always true as it's currently stated. – John Omielan Apr 18 at 6:37

Using a sledgehammer to kill a flea...

Hint: by Dirichlet's theorem, there is some $$k$$ (not necessarily $$\le d-1$$) such that $$p = 1 + nk/d$$ is prime. Note that if $$k' \equiv k\; (\bmod d)$$, $$1 + n k'/d \equiv p\; (\bmod n)$$.

• Yes, I agree it's overkill. However, as my answer shows, Direchlet's Theorem is not necessarily sufficient by itself. The question request is not necessarily always true, but my suggested change would then allow Dirichlet's Theorem to work as you state in your answer. – John Omielan Apr 18 at 6:22

Unfortunately, using Dirichlet's Theorem is not necessarily sufficient by itself to give a prime $$p = 1 + nk/d$$ which you can use (such as described in the the answer hint of Robert Israel) given your problem restrictions. In particular, this is because it doesn't exclude the possibility that $$k \equiv 0 \pmod d$$. In fact, Dirichlet's Theorem can even require this if, for example, $$d = 2$$ and $$n/d$$ is odd and greater than $$1$$.

Also, note that what you're asking to prove isn't even always true! For example, if $$n = 6$$ and $$d = 2$$, then the restriction $$1 \le k \le d - 1$$ means that $$k = 1$$ is the only value allowed. However, $$1 + \frac{6 \times 1}{2} = 4$$ is not coprime to $$n = 6$$. To avoid the trivial example of $$k = 0$$, I believe a better question would be to have $$1 \le k \le d$$. However, using $$k = d$$ gives $$m = 1 + n$$, so it's also fairly trivial to solve. Nonetheless, at least with my example, $$k = 2$$ will then be allowed, giving $$1 + \frac{6 \times 2}{2} = 7$$. Also, Dirichlet's Theorem could then be appropriately used as well.

Another option is that I believe just simply requiring $$d \gt 2$$ is sufficient for your statement to then always be true. However, there would then still remain the issue of Dirichlet's Theorem not necessarily guaranteeing (as far as I know) any primes apart from those where $$k \equiv 0 \pmod d$$.