For $y\in \mathbb{R}$ and $P \subset \mathbb{R}$, consider the distance $d(y,P) = \inf\_{x\in P} |x-y|$.


Given arbitrary $\alpha, \beta, \gamma \in \mathbb{R}$, I am interested to know how to find the smallest $k \in \mathbb{N}$ s.t. $d(\alpha + \beta k,\mathbb{Z}) < \gamma$. 


There are some special cases where the problem is easy to solve, but I'm not able to come up with an elegant (or attractively computable) answer to what seems like an elementary question. 



Elementary question about 'Progressions avoiding sets'
I like this question and the answer, which doesn't seem to appear on either of the pages referenced above, comes from what is called the *Ostrowski expansion* of a real number (some references use other names for this expansion). This is an analogue of the base $p$ expansion which does for the $d(\cdot, \mathbb{Z})$ distance essentially the same thing that the base $p$ expansion does for the $p$-adic absolute value. I will explain it briefly here.


Assume that $\beta\in [0,1)$ is irrational, let $\beta=[a\_0;a\_1,\ldots]$ be the simple continued fraction expansion of $\beta$, and for each $n\ge 0$ let $p\_n/q\_n=[a\_0;a\_1,\ldots ,a\_n]$ be the $n$th principal convergent. Also for each $n\ge 0$ let $$D\_n=q\_n\beta-p\_n=(-1)^nd(q\_n\beta ,\mathbb{Z}).$$ Then, modulo some minor technical details, there is an essentially unique expansion of the form
$$\alpha=\sum\_{n=0}^\infty b\_{n+1}D\_n$$
with $0\le b\_{n+1}\le a\_{n+1}$ for each $n$ (please note that I said "essentially unique", you can work out the details yourself and I will give a reference at the end of the post).


Next if $k\in\mathbb{N}$ then there is an essentially unique expansion of the form
$$k=\sum\_{n=0}^\infty c\_{n+1}q\_n,$$
with $0\le c\_{n+1}\le a\_{n+1}$ for each $n$.


Now since the quantity $d(\cdot,\mathbb{Z})$ is invariant under integer translation we have that
$$d\left(\alpha-k\beta,\mathbb{Z}\right)=d\left(\alpha-k\beta+\sum\_{n=0}^Nb\_{n+1}p\_n,\mathbb{Z}\right),$$
for any $N\ge 0$. Thus if $c\_{n+1}=b\_{n+1}$ for all $n< M$ (actually I think you technically have to assume $M\ge 4$ here) then it follows that
$$d\left(\alpha-k\beta,\mathbb{Z}\right)=d\left(\sum\_{n=M}^\infty (b\_{n+1}-c\_{n+1})D\_n,\mathbb{Z}\right).$$


Finally since the quantities $D\_m$ decrease at least exponentially it is not difficult to show that for $M\ge 4$ or $5$, 
$$d\left(\sum\_{n=M}^\infty (b\_{n+1}-c\_{n+1})D\_n,\mathbb{Z}\right)\asymp |b\_{M+1}-c\_{M+1}|\cdot |D\_M|\asymp \frac{1}{q\_M}.$$
The $\asymp$ sign here means that the left hand side is bounded above and below by positive constants times the right hand side.


So that in a nutshell is the answer to your question. You start with the Ostrowski expansion of $\alpha$ with respect to the continued fraction expansion of $\beta$, choose $M$ so that $1/q\_M<\gamma$, and then any integer of the form 
$$k=\sum\_{n=0}^{M-1}b\_{n+1}q\_m+\sum\_{n=M}^Nc\_{n+1}q\_n,$$
with $0\le c\_{n+1}\le a\_{n+1}$ will be a solution to your inequality, modulo some universal constant and the minor technical points about the expansion that I mentioned above.


In particular to answer your question about the smallest integer which satisfies your inequality, assuming $\gamma$ is not too large (otherwise the problem is easy anyway), it will be given by choosing $M$ to the first integer such that
$$k=\sum\_{n=0}^{M-1}b\_{n+1}q\_m$$
satisfies the inequality. Also, everything here is explicitly computable from the continued fraction expansion of $\beta$.


For more technical details about the universal constants involved and about the restrictions on the digits necessary to get a unique Ostrowski expansion, see the book *Continued Fractions* by Rockett and Szusz. They call this the $t$-expansion of a real number.


