With some help, I figured out how to show $\mathrm{Hom}_{R-\mathsf{Mod}}(R/I, N) \cong \{n \in N \mid \forall a \in I, an=0\}$. I would like to use this result for the current problem.
We can translate this into the current problem by having $R=\mathbb Z$ (and so $\mathbb Z- \mathsf{Mod}=\mathsf{Ab}$), $I=a\mathbb Z$ and $N=\mathbb Z/b\mathbb Z$.
So, we want to show that $\{x+(b) \in \mathbb Z/b\mathbb Z \mid \forall y \in (a), yx+(b)=(b)\} \cong \mathbb Z / (a,b)\mathbb Z$.
Equivalently, we want to show that $\{x+(b) \in \mathbb Z/b\mathbb Z \mid \forall y \in (a), yx \in (b)\} \cong \mathbb Z / (a,b)\mathbb Z$.
As you mentioned, take $I = a\mathbb{Z}$ and $N= \mathbb{Z}/b\mathbb{Z}$. Also, let $d = \gcd(a,b)$. Then, $d$ divides both $a$ and $b$. In particular, $b = dk$ for some integer $k$. I claim that the submodule/subgroup of $N=\mathbb{Z}/b\mathbb{Z}$ that you are looking for is exactly $k\mathbb{Z}/b\mathbb{Z}$ (which is a subgroup of order $d$). You can even just do containment both ways. Can you finish from there?