Теория чисел — раздел математики, занимающийся изучением чисел непосредственно как таковых, их свойств и поведения в различных ситуациях. Достаточно сложно дать полное определение теории чисел, т.к. точного определения и не существует вовсе. Мы же будем рассматривать только ту ее часть, которая используется при решении олимпиадных задач. В большей степени будем уделять внимание целым числам. Для этого определим некоторые разновидности чисел ...

Множество всех целых чисел обычно обозначают буквой Z и понимают под ним набор всех действительных чисел без дробной части: {... , -3, -2, -1, 0, 1, 2, 3, ...}. Натуральные числа являются подмножеством целых чисел и образуют множество N: {1, 2, 3, ...}.

Простым числом называют натуральное число, большее единицы, которое делится только на 1 и на само себя. Все остальные числа называют составными. Первые 10 простых чисел: 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29. Перечислим несколько свойств простых чисел:

• любое составное число представляется уникальным образом в виде произведения простых чисел; иначе еще говорят, что разложение числа на простые множители однозначно.
• простых чисел бесконечно много, причем существует примерно n/ln(n) простых чисел, меньших числа n.
• наименьший простой делитель составного числа n не превышает sqrt(n), поэтому для проверки простоты числа достаточно проверить его делимость на 2 и все нечетные (а еще лучше простые) числа, не превосходящие sqrt(n).
• любое четное число, большее двух представимо в виде суммы двух простых чисел; а любое нечетное, большее чем 5 представимо в виде суммы трех простых чисел
• для любого натурального n, большего единицы существует хотя бы одно простое число на интервале (n, 2*n)

Числа Мерсенна - это числа, представимые в виде 2ⁿ-1. Особый интерес представляют простые числа Мерсена, которые получаются при n=2, 3, 5, 7, 13, 17, 19, 41, 47, 61, 89, 107, 127, ... На сегодняшний день известно 44 простых числа Мерсена и самое большое из них получается при n=32582657 и содержит в себе почти 10 миллионов цифр, оно же является самым большим из найденных на сегодняшний день. Это же число является наибольшим среди всех известных простых чисел. На сегодняшний день неизвестно: конечно ли число простых чисел Мерсена.

Числа Ферма - это числа, представимые в виде 2²ⁿ+1. Простыми среди чисел вида 2ⁿ+1 могут быть только числа Ферма. На данный момент известно всего 5 простых чисел Ферма: 3, 5, 17, 257, 65537; так же известно, что для 5<=n<=32 все числа Ферма - составные.

Совершенное число - это натуральное число, равное сумме всех своих делителей, не включая самого себя. Например число 28 - совершенное число, т.к. 28=1+2+4+7+14. Вот первые 10 совершенных чисел: 6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128, 2658455991569831744654692615953842176, 191561942608236107294793378084303638130997321548169216. Известно, что любое четное совершенное число может быть представлено в виде 2^p-1(2^p-1), где число 2^p-1 является простым числом Мерсена. На сегодняшний день не известно: конечно ли количество совершенных чисел и существуют ли нечетные совершенные числа.

Дружественные числа - два натуральных числа, для которых сумма всех делителей первого числа (кроме него самого) равна второму числу и сумма всех делителей второго числа (кроме него самого) равна первому числу. Иногда частным случаем дружественных чисел считаются совершенные числа: каждое совершенное число дружественно себе. Обычно же, говоря о дружественных числах, имеют в виду пары из двух разных чисел. Первые 8 пар таких чисел: 220 и 284, 1184 и 1210, 2620 и 2924, 5020 и 5564, 6232 и 6368, 10744 и 10856, 12285 и 14595, 17296 и 18416.

Число Армстронга - натуральное число, которое равно сумме своих цифр, возведённых в степень, равную количеству его цифр. Например, 1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴. Последовательность чисел Армстронга начинается так: 1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834, 1741725, 4210818, 9800817, 9926315, 24678050, 24678051, 88593477, 146511208, 472335975, 534494836, 912985153, 4679307774, 32164049650, 32164049651 ... С одним из алгоритмов поиска таких чисел Вы можете ознакомиться здесь.

m-самовлюбленное число - натуральное число, которое равно сумме своих цифр, возведённых в степень m, где m - некоторое натуральное число. Числа Армстронга - частный случай таких чисел.

Число Смита — такое составное число, сумма цифр которого (в данной системе счисления) равняется сумме цифр всех его простых сомножителей. Так, примером числа Смита может служить 202, поскольку 2 + 0 + 2 = 4, и 2 + 1 + 0 + 1 = 4 (202 = 2 * 101). У. Л. МакДэниел доказал, что существует бесконечно много чисел Смита. Насчитывается 29 928 чисел Смита в пределах до 1 000 000. Первые 50 чисел Смита: 4, 22, 27, 58, 85, 94, 121, 166, 202, 265, 274, 319, 346, 355, 378, 382, 391, 438, 454, 483, 517, 526, 535, 562, 576, 588, 627, 634, 636, 645, 648, 654, 663, 666, 690, 706, 728, 729, 762, 778, 825, 852, 861, 895, 913, 915, 922, 958, 985, 1086.