Общие сведения о ТЧ

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

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

Важно запомнить, что если задача на какой-то странный вид чисел, то их, скорее всего, намного

Числа Ферма - это числа, представимые в виде 2^2^n+1. Простыми среди чисел вида 2^n+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^4 + 6^4 + 3^4 + 4^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... С одним из алгоритмов поиска таких чисел Вы можете ознакомиться здесь(http://acmp.ru/article.asp?id_text=198).