Let $g=\text{gcd}(a,b)$
$\therefore\exists x,y\in\mathbb{Z}$ such that $\text{gcd}(x,y)=1$ and $a=gx, b=gy$.
By
Bézout's identity, $\exists k_1,k_2\in\mathbb{Z}$ such that $k_2x-k_1y=1$.
Claim : Choosing $m=a+Nk_1,n=b+Nk_2$ satisfies the necessary condition.
Proof :
It's sufficient to prove that $\text{gcd}(m,n)=1$.
Assume for the sake of contradiction, there exists a prime number $p$ such that $p\mid m$ and $p\mid n$
$\therefore p\mid k_2m-k_1n$
$\Rightarrow p\mid g(k_2x-k_1y)$
$\Rightarrow p\mid g$
Since $\text{gcd}(a,b,N)=1$, $p\nmid N$.
$\therefore p\mid m-gx$ and $p\mid n-gy$
$\Rightarrow p\mid Nk_1$ and $p\mid Nk_2$
$\Rightarrow p\mid k_1$ and $p\mid k_2$
$\Rightarrow p\mid k_2x-k_1y$
$\Rightarrow p\mid 1$
Which is a contradiction. So, $m$ and $n$ has no common prime factor.
$\therefore \text{gcd}(m,n)=1$. $\text{Q.E.D.}$