Need example from number theory

[Timothy Y. Chow]

If I understand what Joe Shipman is asking, the responses so far don't 
really answer his question.  But I think that it's not so easy to come up 
with an example.  The trouble is that "number theory" at the undergraduate 
level deals primarily with the natural numbers, which of course comes 
equipped with a well ordering.  That well ordering means that we rarely 
have to invoke the axiom of choice for anything.

If we broaden our scope from elementary number theory to finitary 
combinatorics, then we have a better chance of sneaking in AC.  We can 
find examples of statements that are equivalent if you assume AC, but 
which are distinct if you don't assume AC.  For example, consider the 
"chromatic number of the plane," meaning the chromatic number of the graph 
whose vertices are the points of R^2 and in which two vertices are 
adjacent if and only if they are a unit distance apart.  If AC is in play 
then we have compactness, and the chromatic number of the plane is the 
same as the maximum chromatic number of any finite subgraph.  There is a 
paper by Shelah and Soifer (J. Combin. Theory Ser. A 103 (2003), 387-391) 
that shows that the chromatic number of the plane depends on your 
set-theoretic axioms.

But one could argue that this type of example is cheating, and that the 
"real" combinatorial question here is the finitary question about finite 
graphs, where the irrelevance of AC is clear.

Along similar lines, one can phrase some theorems in terms of *unlabeled* 
combinatorial objects, and then AC may sneak in if you assume that you can 
simultaneously label a countably infinite family of unlabeled objects. 
But again, arguably the "real" statement is the statement about the 
labeled objects, and so AC isn't really needed.

I honestly can't think of anything at the undergraduate level that "feels 
like number theory" and yet where the invocation of AC doesn't feel like a 
red herring.

Tim