Maximal ideals are prime (history answer please!) Please can someone tell me the history of the simple argument that any maximal ideal of a commutative ring or distributive lattice is prime?  (It is understood that we have found the maximal one using Zorn's Lemma.)
How were prime ideals found before the enactment of the Axiom of Choice? How do constructive algebraists find them now? What similar arguments (directly referring to polynomials or algebraic numbers) were used before ideals were invented?
My own interest is really in distributive lattices and locales, from a constructive point of view, but I am aware that these notions appeared much earlier for commutative rings.
Incorporating my comments:
For locales/frames, (the relevant analogue of) prime ideals are (formal) points.
To be precise, these are completely coprime filters.
In the draft paper [http://www.paultaylor.eu/ASD/loccbv] on which I am working (and a propos of which I asked this question) I have a partly constructive argument that I also use to find points of inhabited overt subspaces.
I am really more interested in the history of the arguments than the definitions (or even concepts). Maybe factorisation is the relevant idea to pursue in order to answer my history question. As Mamuka says, it all comes from prime numbers and therefore probably from the argument by infinite descent in Elements VII 31.
 A: It is perhaps worth mentioning that you only need a choice function for nonempty subsets of the ring that you are working with.  Indeed, given such a function $c$ and an ideal $I$ you can define $d(I)=\{x\not\in I : I + Rx \neq R\}$ and then 
$$ e(I) =
   \begin{cases}
     I + R c(d(I)) & \text{ if } d(I)\neq\emptyset \\
     I & \text{ if } d(I) = \emptyset
   \end{cases} 
$$
You can then iterate transfinitely by the rule
$$ e^\alpha(I) = 
   \begin{cases}
     e(e^\beta(I)) & \text{ if } \alpha = \beta + 1 \\
     \bigcup_{\beta<\alpha}e^\beta(I) & \text{ if } \alpha \text{ is a limit ordinal}. 
   \end{cases}
$$
Now $e^\alpha(I)$ will be independent of $\alpha$ when $\alpha$ is large enough, equal to $I^*$ say; and $I^*$ will be maximal provided that $I$ is proper.
If you prefer a description without ordinals, we can say that $a\in I^*$ if for each family $\mathcal{J}$ of ideals such that


*

*$I\in\mathcal{J}$

*$e(J)\in\mathcal{J}$ whenever $J\in\mathcal{J}$

*The union of any nonempty chain in $\mathcal{J}$ is also in $\mathcal{J}$


there exists $J\in\mathcal{J}$ such that $a\in J$.
Moreover, the class of rings for which one can write down a choice function is quite large.  It certainly contains all rings for which we have an explicit enumeration $\mathbb{N}\to R$, and is closed under taking quotients, products, tensor products, finitely generated algebras and so on.
Of course we do not have choice functions for nontrivial algebras over $\mathbb{R}$ or $\mathbb{Q}_p$.  However, in some cases like this the ring will have a topology and it will be sufficient to have a choice function for nonempty open subsets of nonempty closed subsets, which can be arranged explicitly.
A: In general, one cannot expect commutative rings (with unit) to have prime ideals if the axiom of choice fails.  For a specific example, consider the ring obtained from the direct product $(\mathbb Z/2)^{\mathbb N}$ (i.e., infinite sequences of $0$'s and $1$'s with addition and multiplication componentwise mod $2$) by dividing by the ideal of sequences that have only finitely many $1$ entries.  A prime ideal in this quotient ring amounts to a nonprincipal ultrafilter on $\mathbb N$, and it is known that the existence of such things is not provable in ZF set theory without choice (not even if one adds certain weak choice principles like, for example, the axiom of dependent choice).
