The equation $3a+5b=n$. For a given number $n$, how can we find out whether we have any non-negative values for $a$ and $b$ for the equation
  $$3a+5b=n,$$
  where $1\le n\le 100,000$.


For example: If $n=5$, then $a=0, b=1$.
Your question is a special case of the Frobenius problem or coin problem. You want to know for which $n$ it is possible to find nonnegative integers $a,b$ such that $3a+5b=n$. Take a look at the two-variable case on the Wikipedia page: It is always possible if $n&gt;3\cdot5-3-5$, that is, $n&gt;7$.

For values smaller then or equal to $7$, it is known that exactly half of them can be written in the form $3a+5b$. All you have to do is check them manually:

$0=3\cdot0+5\cdot0$,

$3=3\cdot1+5\cdot0$,

$5=3\cdot0+5\cdot1$,

and $6=3\cdot2+5\cdot0$.

The other half ($1$, $2$, $4$ and $7$) indeed can't be written in the desired form.

These are explicit solutions:

If $n=3k$, then we have $n=3\cdot k+5\cdot0$.

If $n=3k+1$ with $k&gt;2$, then we can write $n=3\cdot(k-3)+5\cdot2$.

If $n=3k+2$ with $k&gt;1$, then $n=3\cdot(k-1)+5\cdot1$.

This covers all integers $n&gt;7$.

All other solutions can now be derived from these using Bézout's identity.
You should caclulate the coeficient of $x^n$ for the following generating function:
$$
G(x)=\frac{1}{(1-x^3)(1-x^5)}.
$$
If $[x^n]G(x) \neq 0$  then the equation $3a+5b=n$ has  solutions.