What axiom(s) do I need to prove that every nonempty set of natural numbers has a smallest element? Math people:

The title is the question.  I am not a logician, and to me, it seems self-evident that any nonempty set of natural numbers has a smallest element.  I am reading an analysis book that uses the Completeness Axiom of the real numbers to prove this "fact" (I put "fact" in quotes because a logician might not accept something so obvious as a fact but might require that I assume some axiom).  To me, this really seems like overkill, and that you should be able to prove it using something much weaker.

EDIT: I am not asking specifically about axioms of ZFC.  My question does not even mention ZFC.  I highly doubt that Choice is necessary here and I suspect it may not even be helpful.  I would like (i) confirmation that using the Completeness Axiom of the real numbers to prove that every nonempty set of natural numbers has a least element is massive overkill and (ii) some weaker axioms that give me the same conclusion, the weaker the better.
Most people, logicians included, will indeed agree that intuitively the claim that every non-empty subset of the natural numbers has a least element (which is knows as the well-ordering principle of the naturals) is self-evident. Another such self-evident property of the natural numbers is the principle of induction. 

As is often the case with self-evident things, actually proving them can be tricky. It turns out (and it's not hard to prove directly) that the well-ordering of the naturals is equivalent to the principle of induction (which is a second order principle). 

Now things become more complicated when one realizes that there exist first order models of arithmetic in which all of the Peano axioms hold as well as all the induction scheme axioms (that is, one axiom per first order formula) in which the second order principle of induction fails. That means that in such models of the naturals the well-ordering principle fails too. So things are not so simple, or self-evident, after all.

I do agree that using the completeness of the reals in order to prove the well-ordering of the naturals is a bit of an over kill as the former is less intuitively clear than the latter. But, it is instructive to see that imposing completeness on the reals (a second order property again) forces the naturals to obey the principle of induction.
Assume that for all natural numbers "a", (a+0)=a.  With both assumptions in place, it follows that (0+0)=0.  No other natural number has the property that (x+x)=x.  Thus, 0 comes as unique.  Addition comes as monotonically increasing.  That is, 

For all x, for all y belonging to the set of natural numbers

 If x&lt;y, then (c+x)&lt;(c+y), where c indicates any constant.

 Also, if (c+x)&lt;(c+y), then x&lt;y.


Now suppose that x=0.  By the second statement, it follows that

 if (c+0)&lt;(c+y), then 0&lt;y.


"y" qualifies as an arbitrary natural number, so 0 comes as the least natural number.  That gives us a "hint".

Now consider any arbitrary set of natural numbers.  Define a monotonicity relation for a function $ on that arbitrary set such that

 if (c $ x)&lt;(c $ y), then x&lt;y.  And if x&lt;y, then (c $ x) &lt; (c $ y)


Define another function # such that there exists some element j belonging to the arbitrary set of natural numbers such that for all x, (j # x)=j.  It follows that (j # j)=j.  Now consider the statement

 if (c $ j)&lt;(c $ y), then j&lt;y.  


Since y came as arbitrary, j comes as the least element of the set.  Since the set came as arbitrary it holds for all subsets of natural numbers.