$ax+by$ when a,b are relatively prime and $x,y\geq 0$ I was solving below question in Automaton theory 
$$L=\{a^m|m=3x+5y; x,y\geq 0\}$$ then the number of states in minimal dfa is?
What I observed is that $3x+5y$ generated every number after $7(8,9,10,11,12 ------)$
and is there any property that I can use to see why this is so or at least could someone provide source from which I can learn more about this
I put the title "$ax+by$ when a,b are relatively prime" because I thought this might be due to 3,5 are relatively prime (correct me if I am wrong) , I don't know anything about this except that it might be related to number theory.
 A: You are asking about The coin problem, which is reasonably well-studied. I encourage you to check out the Wiki article I linked there.
The "Frobenius" of a set of numbers is the smallest one that you can't make as a sum of the numbers in the set - in a land with 3-penny pieces and 5-penny pieces only, you can't pay 7 pennies, but you can pay any amount larger than that.
The Frobenius of a two number set $\{m,n\}$ is given by the formula $F=mn-m-n$. In this case, $15-3-5=7$.
How do we know that every number greater than $7$ is accessible? Here's a not-too-technical proof: If you have enough $5$'s, you can "add $1$" to your total by getting rid of a $5$ and replacing it with two $3$'s $(1=-5+6)$. If you have enough $3$'s, you can add $1$ to your total by getting rid of three of them and replacing them with two $5$'s $(1=-9+10)$.
Thus, if you have at least one $5$ or at least three $3$'s in your sum expressing $n$, then you can also express $n+1$. For numbers over $7$, there is always at least one $5$ or at least three $3$'s in its composition. This is particularly clear for numbers $\ge 15$, and it can be seen with a little more work, for the numbers $8,9,\ldots,14$.
A: This is a consequence of Bezout's Identity, which implies that for $a,b$ relatively prime, there are $\hat{x},\hat{y}$ such that $a\hat{x} + b\hat{y} = 1$. Then for any integer $n$, we choose $x = n\hat{x}$ and $y= n\hat{y}$ and we have $ax + by = n$.
These $x,y$ aren't necessarily $\geq 0$. However, we can determine a lower bound for which we can find a solution with $x,y  \geq 0$. We can always adjust a solution by changing $x$ to $x \pm b$ and $y$ to $y \mp a$. If we can guarantee that some value $x = n\hat{x} \pm mb$ satisfies $0 \leq x\leq \frac{n}{a}$, the corresponding value of $y$ will be nonnegative. This is possible if $\frac{n}{a} \geq b-1$. Similarly, we can guarantee a nonnegative solution if $\frac{n}{b} \geq a -1$. So If $n \geq ab - \max\{a,b\}$, we can guarantee a nonnegative solution.
Clearly this isn't always the best lower bound; in your case this gives $n \geq 10$, while you've showed it possible for $n \geq 8$.
EDIT: As Jyrki Lahtonen pointed out in the comments, robjohn does a much better job doing what I was trying to do (and he actually gets the best bound) in his answer here. For an answer without Bezout's identity, see my other answer to this question, which gets the best bound.
A: Here's an easier way to see this:
Let $b>a$. Consider the sequences of numbers:


*

*$0$, $a$, $2a$, $3a$, $\dots$

*$b$, $b+a$, $b+2a$, $b+3a$, $\dots$

*$2b$, $2b+a$, $2b+2a$, $2b+3a$, $\dots$

*$\dots$

*$(a-1)b$, $(a-1)b+a$, $(a-1)b+2a$, $(a-1)b+3a$, $\dots$


The first row contains integers congruent to $0 \mod a$, the second row congruent to $b \mod a$, etc. Since $b$ and $a$ are coprime, each row represents a different modulus, and the $a$ rows exhaust all moduli $\mod a$.
Now every number has some modulus $\mod a$, and a number appears in some row iff it is $\geq$ the lowest number in that row. Thus all numbers $\geq (a-1)b$ appear somewhere, as I showed in my other answer.
We can now improve on this bound. The number $(a-1)b -a = ab - b - a$ does not appear because it has modulus $-b$ and is less than $(a-1)b$. However, $(a-1)b-a > (a-1)b - b = (a-2)b$, so all numbers greater than $ab - b - a$ with modulus other than $-b$ appear. Since the next number with modulus $-b$ is $(a-1)b$, which appears, all numbers greater than $ab - b - a$ appear.
So if $n \geq ab - b - a + 1 = (a-1)(b-1)$, we can write $n = ax + by$ with $x,y \geq 0$.
A: Indeed, as you write, since $3$ and $5$ are relatively prime, there are integers $x, y$ such that $3x + 5y = 1$ (this is Bézout's identity).
In particular, this means that, to generate an integer $k$, you have the pair $(kx, ky)$, so that
$$3kx + 5ky = k.$$
