Напомним, что простые числа — это числа, которые делятся только на 1 и на самих себя: например, число 5 простое, так как не делится ни на 2, ни на 3, ни на 4, однако 6 не является простым, так как при делении на 2 дает 3. Первыми простыми числами являются 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Путем доказательства от противного, которое так не любили интуиционисты, можно установить, что этот перечень простых чисел можно продолжать бесконечно. Большинство усилий физиков второй половины XX века было направлено на определение элементарных частиц, из которых состоит материя и которые нельзя разделить на другие, более мелкие частицы. Математикам же со времен Евклида известно, что элементарными частицами арифметики являются натуральные числа. Действительно, для любого натурального n возможны два варианта: либо n является простым, либо существует число, отличное от 1 и n, которое является делителем этого числа. Если, например, n равно 23, то мы имеем дело с первым случаем, но если n равно 30, то его можно разделить на 2.
Следовательно, исходное число не является простым. Его можно представить в виде произведения: n = а·b (в нашем случае 30 = 2·15). Мы получили два числа, для которых повторим вышеописанные действия: если оба этих числа являются простыми, процесс на этом завершается, но если одно из них не является простым, мы вновь запишем его в виде произведения сомножителей. В нашем примере 2 является простым, однако 15 можно представить в виде произведения 15 = 3·5, таким образом, 30 = 2·3·5. Так как 2, 3 и 5 — простые числа, процесс на этом завершается. В общем случае мы либо находим простой сомножитель, либо найденные нами множители постепенно уменьшаются — это гарантирует, что описанный нами процесс рано или поздно завершится. Таким образом, мы доказали основную теорему арифметики, которая гласит, что любое число можно представить в виде произведения простых множителей, которые могут повторяться. Пример: 77220 = 2·2·3 x 3·3·5·11·13. В этом случае используется сокращенная запись: 77 220 = 22· З3 х 5·11·13, где показатели степеней указывают, сколько раз повторяется каждый сомножитель.
Основная теорема арифметики утверждает, что разложение на простые множители не только существует для любого натурального числа, но и является единственно возможным (порядок множителей при этом не имеет значения). Иными словами, мы можем записать число 77 220 другим способом, например 77 220 = 3· 22·11 x З3·13, однако и в новом разложении будут использоваться те же простые множители, возведенные в те же степени.
В предыдущей главе мы показали, что «алфавит» арифметики состоит из восьми символов: 0 (число ноль), s (функция следования), ¬ (отрицание), V (дизъюнкция «или»), 
(существование), = (равенство), открывающие и закрывающие скобки.
Мы также использовали переменные х, у, z для обозначения чисел. На первом этапе кодификации Гёдель предложил поставить в соответствие каждому из этих символов число от 1 до 8, переменным х, у, z — три первых числа, больших 8, как показано в таблице ниже.
После того как мы присвоили числа «основным идеям» арифметики, закодировать формулу очень просто: сначала нужно подсчитать число используемых в ней символов (с повторениями) и выбрать столько же простых чисел. Размеры формулы не имеют значения, так как простых чисел бесконечно много. Далее каждое простое число возводится в степень, соответствующую символу, согласно таблице, приведенной выше, после чего все множители перемножаются. Но вместо долгих объяснений рассмотрим один пример.