Which step in the proof succeeds on the integers, but fails when applied to the ring of {a + b*sqrt(-5)} ?
The particular proof given of Bezout's theorem here uses the fact that modding out the ambient ring by one of its prime (in the sense of not further factorable) elements yields a resulting ring with a prime (in the sense of not further factorable) cardinality, and therefore no nontrivial additive subgroups.
However, in the ring Z[sqrt(-5)], there are irreducible elements such that modding out by them produces a ring with non-prime cardinality; for example, 2 is irreducible in this ring, but there are 4 values mod 2 in this ring. 4 is not a prime cardinal, of course. Thus, the provided proof of Bezout's Theorem can and does fail in this context. [Indeed, if we look at the range of multiplication by 2 on this particular additive group of size 4, we see that it is neither trivially of size 1 nor trivially of size all 4. It is an intermediate subgroup of size 2, which can exist because 4 has an intermediate factor of 2]
The provided proof works in the integers because integers can be lined up with cardinals so that A) integer arithmetic mod n has cardinality corresponding to n, and B) also, factorizations or lack thereof for an integer are the same as for the corresponding cardinal. This ensures that integer arithmetic mod a prime integer has a prime cardinality. This fails in other contexts.
[The proof of Bezout's theorem provided, incidentally, is not my favorite because it generalizes so very little. A nicer proof of Bezout's theorem, in my mind, is via the Euclidean algorithm, which then generalizes to all Euclidean domains (and, with minor modification, slightly beyond those as well, to principal ideal domains axiomatized in a manner analogous to Euclidean domains)]
This is the concept that is relevant to the provided proof: Gowers argues that, if a group's size is an unfactorable cardinal, then, by Lagrange's Theorem (which tells us |G'| divides |G| whenever G' is a subgroup of G), it has no intermediate subgroups. Thus, if the additive group mod whatever has size an unfactorable cardinal, then every homomorphism into it is either constantly identity or surjective (as its range is a subgroup); accordingly, multiplication by any non-identity element would have to be invertible (modulo whatever), which is the desired instance of Bezout's Theorem.
Usually, one says an element p of a general ring is prime if p|ab implies p|a or p|b. This property does not necessarily hold for the "smallest" divisor of a given element of your ring, as used in proof 1.
On the other hand, you might be interested in irreducible elements, i.e. those p for which a|p implies a = 1 or p, up to a unit (i.e. a divisor of 1). In fact, you can write any element of your ring as a product of irreducible elements, but not uniquely, not even uniquely up to units. In other words, you can have irreducible elements a, b, c, d, such that ab = cd, but none of them divides any of the others.
So, denoting x = a + b sqrt(-5) in Z[sqrt(-5)], we define the norm[1] of x as follows:
N(x) = a^2 + 5b^2
For x, y in Z[sqrt(-5)], it turns out that the following properties of the norm hold (proving them is fairly straightforward, as it's essentially "plug-and-chug" combined with a bit of reasoning about how things work in the natural numbers):
1. N(xy) = N(x)N(y)
2. N(x) = 0 if and only if x = 0
3. N(x) = 1 if and only if x = 1 or -1 (ie x is a unit).
So, if x is a nonzero nonunit that isn't irreducible, then we can, by definition, write x = y*z where y and z are also nonzero nonunits. Applying strong induction via the norm, we can show that x can be written as a product of irreducibles. Of course this product is, in general, not uniquely determined.