If $n$ is coprime to $10$ i.e. ends with $1,3,7,9$
If $n$ is coprime to $10$, then infact there is a multiple of $n$ which ends in $006$. This is because $n$ is coprime to $1000$, therefore the remainders that $1000k + 6$ leave when divided by $n$, for $0 \leq k \leq n-1$ are all different. (If not, then $1000(k-l)$ is a multiple of $n$ for some $0 < |k-l| < n$ so $n$ must be a multiple of $1000$, a contradiction).
Therefore, for some $k$,$1000k + 6$ is a multiple of $n$. Of course, $1000k + 7$ will be coprime to $1000k+6$ and hence to $n$.
For multiples of $2$ and $5$
For numbers that are possibly multiples of $2$ and $5$, one doesn't need to think much.
Indeed, note that a number of the form $..007$ is already coprime to $2$ and $5$. Therefore, we can actually deal with a new number formed by deleting all instances of $2$ and $5$ from the prime factorization of the given number.
Indeed, if $n$ is the given number, create $l$ by removing $2$ and $5$ from the prime factorization of $n$.
Now, we can find a $..007$ which is coprime to $l$. It is also coprime to $\frac nl$, because $\frac nl$ only has $2,5$ as its prime factors, none of which divides $..007$.
If $n$ is coprime to $a$ and coprime to $b$, then $n$ is coprime to $ab$.
To see why, $xn+ya = 1$ and $wn + zb = 1$, so multiplying , $n(xwn + xzb+yaw) + (yz)ab = 1$, so some linear combination of $n$ and $ab$ is $1$ hence their gcd is $1$.
Use of Lemma
Using the lemma, one sees that $..007$ is coprime to the product of $l$ and $\frac nl$, which is $n$!
Therefore, this $..007$ is as desired.
Let $n = 23$. Then $n$ is coprime to $10$. Find a multiple of $23$ which ends with $006$. By what we know, one of $6,1006,...,22006$ is a multiple of $23$. We check that $12006$ is a multiple of $23$. Therefore, $12007$ is coprime to $23$.
- Let $n = 850$. Then, $n = 17 * 50$, so our $l$ is $17$,and $\frac nl$ is $50$. We run our algorithm with $17$ : we know that one of $6,1006,2006,...,16006$ is a multiple of $17$. You can check that $2006$ is a multiple of $17$. Hence, $2007$ is coprime to $17$, and hence to $850$.