The role of primes in Gödel's Incompleteness Theorem can be better understood by looking at Robinson's Q, which is one of the weakest theories of arithmetic for which Gödel's Incompleteness Theorem holds. Robinson derived his original axioms for Q by looking at the axioms of PA that were used in the proof that every computable function can be represented in PA, which is the key part of Gödel's argument.
A simple theory that interprets Robinson's Q is the theory of discrete ordered rings with induction for open formulas, i.e. the schema φ(0) ∧ ∀x(φ(x) → φ(x+1)) → ∀x(x ≥ 0 → φ(x)), where φ is a quantifier-free formula in the language of ordered rings which may contain free variables other than x. (The only existential quantifier in the axiomatization of Q, namely in the axiom x = 0 ∨ ∃y(x = Sy), can be eliminated using subtraction by 1.since we now have subtraction.)
The theory of discrete ordered rings with open induction has interested many logicians. The first to study this theory was Shepherdson (A non-standard model for a free variable fragment of number theory, MR161798) who showed that this theory cannot prove that √2 is irrational. It follows that Robinson's Q also cannot prove the irrationality of √2. Since the irrationality of √2 is a consequence of unique factorization into primes, Robinson's Q cannot prove that either.
Shepherdson's model where √2 is rational is the ring S whose elements are expressions of the form $$a_0 + a_1T^{q_1} + \cdots + a_kT^{q_k}$$ where T is an indeterminate, the exponents 0 < q1 < ... < qk are positive rationals, the coefficient a0 is an integer, and the remaining coefficients a1,...,ak are real algebraic numbers. Positivity is determined by the sign of the leading coefficient ak; this corresponds to making T infinitely large. The fact that this satisfies open induction is very remarkable. In this ring S, the only primes are the primes from ℤ, so there are simply no infinite primes. Therefore, Robinson's Q cannot prove that the primes are unbounded.
Still stranger discrete ordered rings with open induction have been constructed by Macintyre and Marker (Primes and their residue rings in models of open induction, MR1001418). For example, they construct such a ring where there are unboundedly many primes, but all infinite primes are congruent to 1 modulo 4.
It is apparently still unknown whether the induction axiom for bounded quantifier formulas (IΔ0) proves the unboundedness of prime numbers. This problem was raised by Wilkie and the first partial answer came from Alan Woods who linked it to a pigeonhole principle, together Paris, Wilkie, and Woods (Provability of the pigeonhole principle and the existence of infinitely many primes, MR973114) showed that the unboundedness of prime numbers is provable in a very small extension of IΔ0. (See also this recent article by Woods and Cornaros MR2518806.)
Although the
The above shows that a sound theory of primes and factorization is not necessary , doesn't mean that primes are not at all important for Gödel's Incompleteness Theorem. IndeedHowever, the this should be taken with a grain of salt. The key feature of Robinson's Q is that it correctly interprets the basic arithmetic of as far as the true standard natural numbers are concerned, and nothing more. The fact that Robinson's Q doesn't say much about what is happening outside the standard integers does not mean that the certain features, like primality, that make up the rich and complex structure of the standard integers is completely irrelevant to Gödel's Incompleteness Theorem.
