jmc

Suppose $n$ is a solution to the congruence $$(12,500,000)\cdot n\equiv 111(\mathrm{mod}999,999,999).$$Then, by multiplying both sides by $80$, we see that $n$ satisfies $$(1,000,000,000)\cdot n\equiv 8,880(\mathrm{mod}999,999,999).$$The left side of this congruence is equivalent to $1\cdot n=n(\mathrm{mod}999,999,999)$, so we have $n\equiv 8,880(\mathrm{mod}999,999,999)$.

Since $80$ is relatively prime to $999,999,999$, it has an inverse $(\mathrm{mod}999,999,999)$. (In fact, we know this inverse: it's $12,500,000$.) Thus we can reverse the steps above by multiplying both sides by $80^{-1}$. So, any integer $n$ satisfying $n\equiv 8,880(\mathrm{mod}999,999,999)$ is a solution to the original congruence.

The smallest positive integer in this solution set is $n=\boxed{8,880}$.