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$.
 A: 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>3\cdot5-3-5$, that is, $n>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>2$, then we can write $n=3\cdot(k-3)+5\cdot2$.
If $n=3k+2$ with $k>1$, then $n=3\cdot(k-1)+5\cdot1$.
This covers all integers $n>7$.
All other solutions can now be derived from these using Bézout's identity.
A: 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.
