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

Question

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?

Answer 1

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

Answer 2

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

Please check your source to see if you made a mistake in your question text.