|
Страница 1 из 4
Малая теорема Ферма. Пусть p -- простое число. Тогда для всякого целого числа b, отличного от нуля, справедливо сравнение bp-1 == 1 (mod p). Малая теорема Ферма является непосредственным следствием теоремы Лагранжа (порядок любого элемента группы делит порядок группы) и того факта, что кольцо Zp в случае простого p является полем, т.е. все его ненулевые элементы принадлежат группе обратимых элементов. Порядок группы обратимых элементов кольца Zp равен p-1. Простейший тест проверки простоты числа m состоит в проверке малой теоремы Ферма. Выберем произвольное целое число b (например, b = 2), и возведем его в степень m - 1 по модулю m. Если мы получим не единицу, то по малой теореме Ферма число m составное. Беда состоит в том, что если bm-1 == 1 (mod m), то ничего нельзя сказать об m. Древние греки ошибочно полагали, что все числа m, удовлетворяющие обращению малой теоремы Ферма для основания 2, простые: если 2m-1 == 1 (mod m), то m -- простое число. Минимальный контрпример к этому утверждению был найден только в XVII веке: 2340 == 1 (mod 341), но число 341 -- не простое, 341 = 11 * 31. (Действительно, 2340 = (2^10)34 = 102434, но 1024 = 3 * 341 + 1 == 1 (mod 341), поэтому 102434 == 1 (mod 341).) То, что 341 не удовлетворяет малой теореме Ферма, может быть показано с помощью других оснований: 3340 == 56 (mod 341) Тем не менее существуют числа, которые не являются простыми, но которые ведут себя как простые в малой теореме Ферма. Такие числа называются кармайкловыми. Определение. Число m называется кармайкловым, если оно не простое и для всякого b, взаимно простого с m, выполняется утверждение малой теоремы Ферма: bm-1 == 1 (mod m). Минимальные кармайкловы числа -- это 561, 1105, 1729, ... Множество кармайкловых чисел бесконечно, и их плотность стремится к нулю на бесконечности. Несложно доказать следующее утверждение. Предложение 5. Пусть m = p1e1 * p2e2 * ... * pkek -- представление целого числа m в виде произведения степеней простых. Число m является кармайкловым тогда и только тогда, когда 1) для всякого i показатель степени ei = 1; 2) k >= 3; 3) для всякого i число pi - 1 делит m - 1. Доказательство. Докажем только обратную, наиболее интересную импликацию. Пусть число m удовлетворяет условиям 1-3. Рассмотрим произвольное b, взаимно простое с m. По Китайской теореме об остатках, кольцо Zm представляется в виде прямой суммы Zm == Zp1 + Zp2 + ... + Zpk. При этом изоморфизме элемен b представляется в виде строки b == (b1, b2, ..., bk) Тогда bm-1 == (b1m-1, b2m-1, ..., bkm-1. По малой теореме Ферма, для всякого i bim-1 == 1 (mod pi), поскольку (m - 1) делится на (pi - 1). Поэтому bm-1 == (1, 1, ..., 1) т.е. bm-1 == 1 (mod m). Пример. Покажем, что число 561 является кармайкловым. Действительно, 561 = 3 * 11 * 17. Имеем (3 - 1) | 560, (11 - 1) | 560, (17 - 1) | 560. Следовательно, число 561 удовлетворяет условиям предложения 5. Итак, для кармайкловых чисел тест простоты, основанный на теореме Ферма, не работает. Тем не менее его модификация, предложенная Рабином, применима к любым целым числам. |