Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 49 стр.

                                                                               50

      В теории чисел изучаются также обобщенные числа Мерсенна. Такими
являются числа вида

          M (k, n) = k · 2n ± 1,

где n–простое число, а k –небольшое простое число.

Числа Кармайкла

       Малая теорема Ферма утверждает, что ap−1 ≡ 1 (mod p ) для
простых p и произвольных натуральных a, взаимно–простых с p. Обратное
утверждение неверно, есть небольшое количество составных чисел n таких,
что для всех не сравнимых с n чисел a выполняется an−1 ≡ 1( mod n). Такие
числа называются числами Кармайкла (Carmichael’ Numbers).
      Эквивалентное      определение     чисел    Кармайкла     дает    критерий
Корсельта.

Теорема 1.12. (Корсельт, 1899) Составное число n является числом
Кармайкла тогда и только тогда, когда n свободно от квадратов, и для
каждого простого делителя p числа n число p − 1 делит число n − 1.

      В частности, из теоремы Корсельта следует, что все числа Кармайкла
нечётны, так как любое чётное составное число, свободное от квадратов,
имеет, по крайней мере, один нечётный простой делитель, и поэтому из
делимости (p−1) | (n−1) следует, что чётное делит нечётное, что невозможно.
      Корсельт был первым, кто заметил это свойство, но он так и не смог
найти какие-либо примеры. В 1910 г. Кармайкл нашел первое и наименьшее
такое число 561. Последовательность чисел Кармайкла начинается так:

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633,
62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601,
278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461.

Числа Каннингама

       Числа Каннингама (Cunningham’ Numbers) – числа вида bn ± an .
Проект Каннингама – это проект создания таблиц разложения чисел