Просто́е число́ это натуральное число, которое имеет ровно два натуральных делителя (только 1 и самого себя). Простые числа близнецы это пара простых чисел, отличающихся на 2. Два целых числа называются взаимно простыми, если у них нет общих делителей (не считая единицы). Составно́е число́ натуральное число большее 1, имеющее 2 и более делителя. Любое составное число может быть единственным способом разложено в произведение простых множителей. Таким образом, все натуральные числа больше единицы разбиваются на простые и составные. Изучением свойств простых чисел занимается теория чисел (или высшая арифметика раздел математики, изучающий целые числа и сходные объекты).

Примеры чисел, не превосходящие 200:

По определению составное число раскладывается в произведение двух меньших чисел. Эти числа не обязаны быть простыми. Если они составные, то их можно разложить дальше - до тех пор, пока не останутся только простые множители. Скажем, число составное: 1001 = 7 · 143. Число 7 простое и дальше не делиться, а вот 143 разлагается в произведение двух простых чисел: 143 = 11 · 13. В итоге получаем 1001 = 7 · 11 · 13. Так же можно действовать иначе, заметив, что 1001 = 11· 91. Число 11 простое, а 91 - нет: 91 = 7 · 13. Получаем: 1001 = 11 · 91 = 11 · 7 · 13 и дальше уже ничего не разлагается.

В примере с числом 1001 мы двумя способами получили в итоге одно и то же разложение. Но всегда ли так будет? Чтобы убедиться рассмотрим пример. Два разложения одного и того же числа ( ) на два множителя: · = = 99599· На первый взгляд, в этих двух разложениях нет ничего общего. Не противоречит ли это единственности разложения на простые множители? Нет, поскольку никто не гарантирует, что выписанные множители - простые. На самом деле они составные = 137 · 571; = 137 · 727; = 337 · 727; = 337 · 571; Оба разложения получаются при различной группировке множителей в произведении: 137 · 337 · 571 · 727. Теорема о единственности разложения на множители («основная теорема арифметики»). Два разложения одного и того же числа на простые множители отличаются лишь порядком сомножителей. Другими словами, в эти два разложения входят одни и те же множители и в одном и том же количестве, в разном порядке.

Лемма. Если произведение ab двух целых чисел a и b делится на простое число p, то хотя бы один из сомножителей делится на p. Ту же самую лемму можно сформулировать и иначе: если два числа не делятся на p, то и их произведение не делится на p; если произведение ab делится на p, а первый сомножитель a не делится на p, то второй сомножитель b делится на p. Все эти три формулировки разными словами говорят одно и то же: Не может быть, чтобы одновременно число a не делилось на p, число b не делилось на p и произведение ab делилось на p.

В лемме говориться, что число p простое. Скажем, при p = 6 утверждение леммы неверно: произведение чисел 2 и 3 делится на 6, а ни один из сомножителей на 6 не делится. Из леммы следует аналогичное утверждение для произвольного числа сомножителей: если их произведение делится на простое p, то хотя бы один из сомножителей делится на p. Пусть произведение abc делится на p. Записав его как (ab)· c, заключаем по лемме, что либо ab делится на p, либо c делится на p. В первом случае надо применить лемму ещё раз и заключить, что либо a делится на p, либо b делится на p.

Числа Мерсенна получили известность в связи с эффективным критерием простоты Люка Лемера, благодаря которому простые числа Мерсенна давно удерживают лидерство как самые большие известные простые числа. На данный момент самым большим известным простым числом является число Мерсенна M = , найденное в августе 2008 года в рамках проекта распределённых вычислений GIMPS. Всего известно 46 простых числа Мерсенна, причём порядковые номера с уверенностью установлены только у первых 39-ти. Интересно отметить, что 46-е найденное простое число Мерсенна было найдено на две недели позднее 45-го найденного простого числа Мерсенна и оказалось меньше его. Последовательность простых чисел Мерсенна и их показателей начинается так: M p : 3, 7, 31, 127, 8191, , , , , ,... p : 2, 3, 5, 7, 13, 17, 19, 31, 61, 89,...