Псевдопросты́е чи́сла Ферма́ — составные числа, проходящие тест Ферма. Названы в честь французского математика Пьера Ферма. В теории чисел псевдопростые числа Ферма составляют важнейший класс псевдопростых чисел.
Определение
Псевдопростые числа
Составное число называется псевдопростым, если оно удовлетворяет некоторому необходимому (но не достаточному) условию простоты числа, то есть если оно обладает некоторыми свойствами простого числа.
Малая теорема Ферма
Малая теорема Ферма гласит, что если n — простое число, то для каждого числа a взаимно простого с n справедливо сравнение .
Псевдопростые Ферма Составное число n называется псевдопростым числом Ферма по основанию a (взаимно простому с n), если выполнено сравнение . Иными словами, составное число называют псевдопростым, если оно проходит тест Ферма по основанию a. Число, являющееся псевдопростым Ферма по каждому взаимно простому с ним основанию, называется числом Кармайкла.
Вариации Существуют некоторые вариации определения:
Некоторые источники требуют, чтобы псевдопростое число было нечетным, так как четное число очевидно является составным. Каждое нечётное число удовлетворяет для , поэтому в таком случае новой информации о числе мы не получим. Это исключается в определении, данном Крэндаллом и Померансом: Составное число является псевдопростым числом Ферма по основанию , если и
Свойства
Распределение Существует бесконечно много псевдопростых чисел по данному основанию (более того, существует бесконечно много сильных псевдопростых и бесконечно много чисел Кармайкла), но они довольно редки. Есть только три псевдопростых числа Ферма по основанию 2, меньшие 1000, 245 — меньшие одного миллиона, и только 21 853 — меньшие, чем 25 миллиардов.
Таблицы с некоторыми псевдопростыми числами Ферма
Наименьшие псевдопростые Ферма Наименьшие псевдопростые Ферма для каждого основания a ≤ 200 приведены в таблице ниже; цвета различают числа по количеству различных простых делителей.
Наименьшие псевдопростые Ферма a Наименьшее п-пФ a Наименьшее п-пФ a Наименьшее п-пФ a Наименьшее п-пФ 1 4 = 2² 51 65 = 5 · 13 101 175 = 5² · 7 151 175 = 5² · 7 2 341 = 11 · 31 52 85 = 5 · 17 102 133 = 7 · 19 152 153 = 3² · 17 3 91 = 7 · 13 53 65 = 5 · 13 103 133 = 7 · 19 153 209 = 11 · 19 4 15 = 3 · 5 54 55 = 5 · 11 104 105 = 3 · 5 · 7 154 155 = 5 · 31 5 124 = 2² · 31 55 63 = 3² · 7 105 451 = 11 · 41 155 231 = 3 · 7 · 11 6 35 = 5 · 7 56 57 = 3 · 19 106 133 = 7 · 19 156 217 = 7 · 31 7 25 = 5² 57 65 = 5 · 13 107 133 = 7 · 19 157 186 = 2 · 3 · 31 8 9 = 3² 58 133 = 7 · 19 108 341 = 11 · 31 158 159 = 3 · 53 9 28 = 2² · 7 59 87 = 3 · 29 109 117 = 3² · 13 159 247 = 13 · 19 10 33 = 3 · 11 60 341 = 11 · 31 110 111 = 3 · 37 160 161 = 7 · 23 11 15 = 3 · 5 61 91 = 7 · 13 111 190 = 2 · 5 · 19 161 190=2 · 5 · 19 12 65 = 5 · 13 62 63 = 3² · 7 112 121 = 11² 162 481 = 13 · 37 13 21 = 3 · 7 63 341 = 11 · 31 113 133 = 7 · 19 163 186 = 2 · 3 · 31 14 15 = 3 · 5 64 65 = 5 · 13 114 115 = 5 · 23 164 165 = 3 · 5 · 11 15 341 = 11 · 13 65 112 = 2⁴ · 7 115 133 = 7 · 19 165 172 = 2² · 43 16 51 = 3 · 17 66 91 = 7 · 13 116 117 = 3² · 13 166 301 = 7 · 43 17 45 = 3² · 5 67 85 = 5 · 17 117 145 = 5 · 29 167 231 = 3 · 7 · 11 18 25 = 5² 68 69 = 3 · 23 118 119 = 7 · 17 168 169 = 13² 19 45 = 3² · 5 69 85 = 5 · 17 119 177 = 3 · 59 169 231 = 3 · 7 · 11 20 21 = 3 · 7 70 169 = 13² 120 121 = 11² 170 171 = 3² · 19 21 55 = 5 · 11 71 105 = 3 · 5 · 7 121 133 = 7 · 19 171 215 = 5 · 43 22 69 = 3 · 23 72 85 = 5 · 17 122 123 = 3 · 41 172 247 = 13 · 19 23 33 = 3 · 11 73 111 = 3 · 37 123 217 = 7 · 31 173 205 = 5 · 41 24 25 = 5² 74 75 = 3 · 5² 124 125 = 5³ 174 175 = 5² · 7 25 28 = 2² · 7 75 91 = 7 · 13 125 133 = 7 · 19 175 319 = 11 · 19 26 27 = 3³ 76 77 = 7 · 11 126 247 = 13 · 19 176 177 = 3 · 59 27 65 = 5 · 13 77 247 = 13 · 19 127 153 = 3² · 17 177 196 = 2² · 7² 28 45 = 3² · 5 78 341 = 11 · 31 128 129 = 3 · 43 178 247 = 13 · 19 29 35 = 5 · 7 79 91 = 7 · 13 129 217 = 7 · 31 179 185 = 5 · 37 30 49 = 7² 80 81 = 3⁴ 130 217 = 7 · 31 180 217 = 7 · 31 31 49 = 7² 81 85 = 5 · 17 131 143 = 11 · 13 181 195 = 3 · 5 · 13 32 33 = 3 · 11 82 91 = 7 · 13 132 133 = 7 · 19 182 183 = 3 · 61 33 85 = 5 · 17 83 105 = 3 · 5 · 7 133 145 = 5 · 29 183 221 = 13 · 17 34 35 = 5 · 7 84 85 = 5 · 17 134 135 = 3³ · 5 184 185 = 5 · 37 35 51 = 3 · 17 85 129 = 3 · 43 135 221 = 13 · 17 185 217 = 7 · 31 36 91 = 7 · 13 86 87 = 3 · 29 136 265 = 5 · 53 186 187 = 11 · 17 37 45 = 3² · 5 87 91 = 7 · 13 137 148 = 2² · 37 187 217 = 7 · 31 38 39 = 3 · 13 88 91 = 7 · 13 138 259 = 7 · 37 188 189 = 3³ · 7 39 95 = 5 · 19 89 99 = 3² · 11 139 161 = 7 · 23 189 235 = 5 · 47 40 91 = 7 · 13 90 91 = 7 · 13 140 141 = 3 · 47 190 231 = 3 · 7 · 11 41 105 = 3 · 5 · 7 91 115 = 5 · 23 141 355 = 5 · 71 191 217 = 7 · 31 42 205 = 5 · 41 92 93 = 3 · 31 142 143 = 11 · 13 192 217 = 7 · 31 43 77 = 7 · 11 93 301 = 7 · 43 143 213 = 3 · 71 193 276 = 2² · 3 · 23 44 45 = 3² · 5 94 95 = 5 · 19 144 145 = 5 · 29 194 195 = 3 · 5 · 13 45 76 = 2² · 19 95 141 = 3 · 47 145 153 = 3² · 17 195 259 = 7 · 37 46 133 = 7 · 19 96 133 = 7 · 19 146 147 = 3 · 7² 196 205 = 5 · 41 47 65 = 5 · 13 97 105 = 3 · 5 · 7 147 169 = 13² 197 231 = 3 · 7 · 11 48 49 = 7² 98 99 = 3² · 11 148 231 = 3 · 7 · 11 198 247 = 13 · 19 49 66 = 2 · 3 · 11 99 145 = 5 · 29 149 175 = 5² · 7 199 225 = 3² · 5² 50 51 = 3 · 17 100 153 = 3² · 17 150 169 = 13² 200 201 = 3 · 67
Числа Пуле Псевдопростые Ферма по основанию 2 называют числами Пуле, по имени бельгийского математика . Разложение на множители шестидесяти первых чисел Пуле, в том числе тринадцати чисел Кармайкла (выделены жирным шрифтом), ниже в таблице.
Числа ПулеПуле 1 - 15Пуле 16 - 30Пуле 31 - 45Пуле 46 - 6034111 · 31468131 · 1511570923 · 683331533 · 43 · 2575613 · 11 · 17546143 · 127158417 · 31 · 73349455 · 29 · 2416453 · 5 · 4366017 · 23 · 41167055 · 13 · 2573533389 · 39711055 · 13 · 17795773 · 109187053 · 5 · 29 · 43398655 · 7 · 17 · 67138719 · 73832153 · 1571872197 · 193410417 · 11 · 13 · 4117297 · 13 · 1984813 · 11 · 2571995171 · 281416655 · 13 · 64119053 · 5 · 12789117 · 19 · 67230013 · 11 · 17 · 4142799127 · 337204723 · 891026131 · 3312337797 · 2414665713 · 37 · 9724655 · 17 · 29105855 · 29 · 73257613 · 31 · 27749141157 · 313270137 · 73113055 · 7 · 17 · 192934113 · 37 · 6149981151 · 33128217 · 13 · 31128013 · 17 · 251301217 · 13 · 331526337 · 73 · 103327729 · 113137417 · 13 · 1513088917 · 23 · 79552453 · 5 · 29 · 127403337 · 1091374759 · 2333141789 · 353574217 · 13 · 631436917 · 2571398111 · 31 · 413160973 · 43360701101 · 60143713 · 31 · 471449143 · 33731621103 · 3076078789 · 683
Число Пуле, все делители d которого делят также число 2d − 2, называется суперчислом Пуле. Существует бесконечно много чисел Пуле, не являющихся суперчислами Пуле.
Первые псевдопростые числа Ферма (до 10000) по основанию a