I'm on the controversial side that Gowers's overall argument is unfair to laymen, but this is indeed a circular argument. It can be modified to make it more ro

I'm on the controversial side that Gowers's overall argument is unfair to laymen, but this is indeed a circular argument. It can be modified to make it more robust while keeping the structure of the argument fairly close to what you have here, but it requires a bit more sophistication. Specifically, suppose that n is the smallest integer with two different prime factorizations, and write these factorizations as p_1 * ... * p_n and q_1 * ... * q_m. Now first you might imagine that these two factorizations could be different and yet share at least one prime in common. But this is impossible. If they shared a prime in common, we might as well assume it's the first, so that p_1 = q_1 (i.e., we're just reordering the indices). But then n / p_1 has the two different factorizations p_2 * ... * p_n and q_2 * ... * q_m, but since n / p_1 is smaller than n this is a contradiction. So we can assume that these two factorizations share no primes in common. In particular, we can assume without loss of generality that p_1 < q_1. Consider now the quantity n' = n - p_1 * q_2 * ... * q_m. This is positive but smaller than n. Now we already know that p_1 divides n, so we can actually factor out p_1 here to obtain n' = p_1 * (n / p_1 - q_2 * ... * q_m). This gives us one factorization of n' < n in which p_1 occurs. Now here is the critical observation. Because n' is smaller than n, n' must have a unique factorization due to the choice of n as the smallest number which does not have a unique factorization. (This is the point where the proof will fail for many other more exotic rings which lack the intrinsic well-ordering principle enjoyed by the integers.) But we can also write n' = q_1 * q_2 * ... * q_m - p_1 * q_2 * ... * q_m = (q_1 - p_1) * q_2 * ... * q_m. This is another factorization of n', and by uniqueness it must contain p_1. This is only possible if p_1 divides q_1 - p_1, which is only possible if p_1 divides q_1, which is not possible since q_1 is prime. --- This highlights why I disagree with Gowers here. He's looking at other rings which violate the basic ordered structure of the integers, but this structure plays a critical role in our intuition about the integers, and I believe it's precisely why we feel something like unique factorization is "obvious" (or intuitive) for the positive integers, but it remains very elusive for, say, Z[sqrt(-n)] (where it's true if n = 1,2 and false if n >= 3).