Операция деления не всегда возможна в области натуральных чисел. Это дает нам право ввести отношение делимости: скажем, что число n делит число m, если m=nk для какого-либо подходящего k∈ ℕ . Обозначается это отношение так: . Среди всех натуральных чисел особо выделяются простые числа -- это числа n имеющие ровно два делителя -- единицу и само число n. Тем самым единица не будет простым числом – она имеет один делитель. Но по существу единца не причисляется к простым числам в силу своей обратимости: . Вот первые 99 простых чисел:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173,179,181,191, 193, 197, 199,
211,223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,307, 311,
313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431,
433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523.
Число, не являющееся простым, называется составным. Пусть k -- составное натуральное число. Тогда для некоторых натуральных чисел a,b, больших единицы. При этом получаем: . Число a (так же как и b) либо простое, либо составное. Во втором случае снова раскладываем , где p,q>1, и поэтому . В виду уменьшения делителей, этот процесс не может продолжаться бесконечно (см. свойство полной упорядоченности). Следовательно, в итоге получаем разложение числа k в произведение простых чисел. Тот факт, что такое разложение единственно с точностью до перестановки сомножителей мы докажем позже, а пока сформулируем
ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ 1. Любое натуральное число , большее единицы, разложимо в произведение простых чисел:
Такое разложение единственно.
ТЕОРЕМА 2. Множество простых чисел бесконечно.
Предположим противное: множество простых чисел исчерпывается числами . Образуем число . Это число по основной теореме арифметике имеет простой множитель p. Тем самым для какого-либо . Тогда из соотношений и вытекает, что p делит их разность, т.е. число 1 и, следовательно, p≤ 1. Это противоречие показывает, что предположение о конечности множества простых чисел неверно. Следовательно, верно отрицание этого утверждения, т.е. верно то, что утверждается в формулировке теоремы. □