# Linear minimization over two integers

Given $$x\in]0,1[$$, let the function $$f:\mathbb{N}^+\times\mathbb{N}\to\mathbb{R}$$ be defined by

$$f(p,q) := x p - q$$

Is there an analytic formula for the minimum of $$f$$ under the constraint

$$f(p,q) > 0$$

(together with $$p$$ being a positive integer and $$q$$ a nonnegative integer)?

For a rational $$x$$, there is a minimum. Suppose $$x = \frac rs$$ with $$\gcd(r,s)=1$$. Then $$f(p,q) = \frac{rp - sq}{s}$$, so it is a positive multiple of $$\frac1s$$; in particular, it must be at least $$\frac1s$$.
This is always achievable by the extended Euclidean algorithm: for integer $$r,s$$ it finds a solution $$(m,n)$$ to $$rm + sn = \gcd(r,s)$$, which is $$1$$ in this case. We'll get $$f(m,-n)=\frac1s$$. If $$m>0$$ and $$n<0$$, this is the solution we want. Otherwise, we also have $$f(m+ks,kr-n)=\frac1s$$ with $$m-ks, kr-n>0$$ for large enough $$k$$.
When $$x$$ is irrational, take the sequence $$\frac{h_1}{k_1}, \frac{h_2}{k_2}, \dots$$ of continued fraction approximations of $$x$$. In general, it is true that the even terms in this sequence give a close approximation to $$x$$ from below: $$\frac{h_{2n}}{k_{2n}} < x < \frac{h_{2n}}{k_{2n}} + \frac{1}{k_{2n}^2}$$. Rearranging, $$0 < k_{2n} x - h_{2n} < \frac1{k_{2n}}$$ so $$f(k_{2n}, h_{2n})$$ is positive but can be made as small as we want.