Proof of Impossibility - The Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic

Gödel used these theorems in his proof (see below, more in Nagel and Newman p. 68). He figured out a way to express any mathematical formula or proof (in arithmetic) as a product of prime numbers raised to powers. And because he could factor any number into its unique primes, he was able to recover a formula or proof intact from its number by factoring it.

A prime number is defined as a counting number that is divisible only by itself and 1.

First theorem (cf Hardy and Wright, p. 2):

"Every positive integer (counting number), except 1, is a product of primes" OR Excepting 1, it is impossible to find a positive integer that is not a product of primes.

Second theorem: fundamental theorem of arithmetic (cf Hardy and Wright p. 3):

Every integer (counting number) has a unique expression as a product of primes. OR: It is impossible to factor an integer into primes in more than one way. (This does not include "permutations" of the primes).

Thus, if we pick a number e.g. 85, we see that it has prime factors 5 and 17, and this is unique (85 = 5×17 or 17×5), or 8 = 2×2×2 = 23.

Neither proof is particularly trivial. Hardy and Wright attribute an explicit statement of the Fundamental Theorem to Gauss. "It was, of course, familiar to earlier mathematicians" (Hardy and Wright, p. 10).