Is there exist $x,y \in \mathbb{Z}$ such that $nx+ly=\gcd(n,l)$ and $\gcd(n,y) = 1$? 
Prove or disprove that for any positive integers $n,l,k$  such that $\gcd(n,l)=k$, there exist $x,y \in \mathbb{Z}$ such that $nx+ly=k$ and $\gcd(n,y) = 1$.

I believe this is not the case, but I couldn't find a counterexample.
I want to find $n,k,y$ such that $\gcd(\frac{n}{k},y) = 1$ and for any $s\in\mathbb{Z}$, the inequality $\gcd(n,y+s\cdot\frac{n}{k})>1$ hold.
How can we prove or disprove it? Please give me advice.
 A: Let $n,l \in \mathbb{N} \setminus \{0\}$. Then we can find $x,y \in \mathbb{Z}$ such that $nx + ly = \gcd(n,l)$ and $\gcd(n,y)=1$.
Proof: At first, we shall mention that there always exist $x_0,y_0 \in \mathbb{Z}$ such that $nx_0 + ly_0 = \gcd(n,l)$. $x_0$ and $y_0$ can be determined by the extended Euclidean algorithm. 
If $x,y \in \mathbb{Z}$ satisfy $nx + ly = \gcd(n,l)$, then there exists an integer $t$ such that $x = x_0 - \frac{l}{\gcd(n,l)} \cdot t$ and $y = y_0 + \frac{n}{\gcd(n,l)} \cdot t$. To see this, you just have to notice that for a solution $(x_1,y_1)$ to $nx + l y = \gcd(n,l)$, the difference $(x_1-x_0,y_1-y_0)$ is a solution to $nx + ly = 0$. So in fact, we are looking for $t \in \mathbb{Z}$ such that $\gcd(n,y_0 + \frac{n}{\gcd(n,l)} \cdot t)=1$. 
Claim: $\gcd(y_0, \frac{n}{\gcd(n,l)})=1$. Proof of the claim: By the definition of $x_0,y_0$, we have $\frac{n}{\gcd(n,l)} \cdot x_0 + \frac{l}{\gcd(n,l)} \cdot y_0 = 1$. Note that $\frac{n}{\gcd(n,l)}$ and $\frac{l}{\gcd(n,l)}$ are integers. So any common divisor of $y_0$ and $\frac{n}{\gcd(n,l)}$ is a divisor of $\frac{n}{\gcd(n,l)} \cdot x_0 + \frac{l}{\gcd(n,l)} \cdot y_0 = 1$, which implies $\gcd(y_0, \frac{n}{\gcd(n,l)})=1$ immediately.
Now consider the "arithmetic progression" $\frac{n}{\gcd(n,l)} \cdot t + y_0\ (t = 0,1,2,...).$ Since $\gcd(y_0, \frac{n}{\gcd(n,l)})=1$, Dirichlet's prime number theorem tells us that this sequence contains infinitely many prime numbers. So we can find $t_0 \in \mathbb{N}$, such that $y_0 + \frac{n}{\gcd(n,l)} \cdot t_0$ is a prime number larger than $n$. Hence this prime number is too big to divide $n$ and $\gcd(n,y_0 + \frac{n}{\gcd(n,l)} \cdot t_0)=1$ follows. 
