Числата на Ферма — дефиниция, свойства и факторизация

Научете всичко за числата на Ферма: дефиниция, свойства, известни прости случаи, факторизации и примери — ясно, с исторически контекст и актуални резултати.

Числото на Ферма е специално положително число. Числата на Ферма са кръстени на Пиер дьо Ферма. Формулата, която ги генерира, е

F n = 2 2 n + 1 {\displaystyle F_{n}=2^{2^{\overset {n}{}}}+1}

където n е неотрицателно цяло число. Първите девет числа на Ферма са (последователност A000215 в OEIS):

F0 = ²¹ + 1 = 3

F1 = ²² + 1 = 5

F2 = ²⁴ + 1 = 17

F3 = ²⁸ + 1 = 257

F4 = ²¹⁶ + 1 = 65537

F5 = ²³² + 1 = 4294967297 = 641 × 6700417

F6 = ²⁶⁴ + 1 = 18446744073709551617 = 274177 × 67280421310721

F7 = ²¹²⁸ + 1 = 340282366920938463463374607431768211457 = 59649589127497217 × 5704689200685129054721

F8 = ²²⁵⁶ + 1 = 115792089237316195423570985008687907853269984665640564039457584007913129639937 = 1238926361552897 × 93461639715357977769163558199606896584051237541638188580280321

Към 2007 г. само първите 12 числа на Ферма са напълно разчетени. Тези факторизации могат да бъдат намерени на адрес Prime Factors of Fermat Numbers.

Ако 2n + 1 е просто число и n > 0, може да се докаже, че n трябва да е степен на две. Всяко просто число от вида 2n + 1 е число на Ферма и такива числа се наричат числа на Ферма. Единствените известни първични числа на Ферма са F0,...,F4.

Допълнителни пояснения и свойства

За по-голяма яснота запишем формулата с явни степени:

F_n = 2²ⁿ + 1, където n = 0, 1, 2, ...

• Идентичност за произведение: за всяко n ≥ 1 важи
  ∏_{k=0}^{n-1} F_k = F_n − 2. Това следва от общата алгебрична равност: ∏_{k=0}^{n-1} (1 + x^{2^k}) = (1 − x^{2^n})/(1 − x); при x = 2 получаваме ∏ (1 + 2^{2^k}) = 2^{2^n} − 1 = F_n − 2.
• Взаимна простота: от горната идентичност следва, че всяки два различни числа на Ферма са взаимно прости (тоест gcd(F_m, F_n) = 1 за m ≠ n). Действително, ако някои p дели F_m и F_n с m < n, то p дели и F_n − 2 = ∏_{k=0}^{n-1} F_k, но тогава p трябва да дели разликата (F_n − 2) − ∏_{k=0}^{n-1} F_k = 0, което води до противоречие освен в тривиалния случай; по-просто: всякакъв общ делител би трябвало да дели 2, но всички Fermat числа са нечетни, следователно общ делителът е 1.
• Условие за простите делители: ако p е прост делител на F_n (с n ≥ 1), то 2^{2^n} ≡ −1 (mod p). Следователно 2^{2^{n+1}} ≡ 1 (mod p) и редът на 2 по модул p е точно 2^{n+1}. Оттук p − 1 е делимо на 2^{n+1}, т.е. p ≡ 1 (mod 2^{n+1}).
• История — Ферма и Евлер: Пиер дьо Ферма предположил, че всички числа от вида F_n са прости. Това се оказало невярно: Леонард Ойлер (Euler) през 1732 г. показа, че F5 = 4294967297 е съставно и намери делителя 641; по-нататъшни изследвания откриха още фактори за много по-големи F_n.
• Известни първични числа на Ферма: единствените известни Fermat-прости числа са F0 = 3, F1 = 5, F2 = 17, F3 = 257 и F4 = 65537. За n ≥ 5 всички проверени случаи до момента са съставни; въпросът дали съществуват допълнителни Fermat-прими остава отворен.
• Факторизации и текущо състояние: за много по-големи н са намерени единични прости делители и частични факторизации; пълна факторизация на Fermat числа е трудна задача и се поддържат публични списъци (например страницата "Prime Factors of Fermat Numbers"). В оригиналната статия е посочено, че към 2007 г. първите 12 са били напълно факторизирани; оттогава напредъкът продължава, но стойностите растат бързо и пълните факторизации се намират на специализирани бази данни и проекти.
• Приложение — построимост на правилни многоъгълници: връзката с теоремата на Гаус: правилният n-ъгълник може да бъде конструиран с линийка и пергел точно когато n е от вида n = 2^k · p_1 · p_2 · ... · p_r, където p_i са различни Fermat-прости числа. Поради това откриването на нов Fermat-просто число води до нови построими правилни многоъгълници.

Кратки примери и бележки

Някои вече дадени факторизации (повторени тук за удобство):

• F5 = 2³² + 1 = 4294967297 = 641 × 6700417 (показано от Euler)
• F6 = 2⁶⁴ + 1 = 18446744073709551617 = 274177 × 67280421310721
• F7 и F8 имат посочените по-горе делители и т.н.

За по-нататъшно изучаване и пълни списъци на известните делители и факторизации е удобно да се консултирате със специализирани ресурси и бази данни (OEIS, сайтове за факторизация и проекти, посветени на числата на Ферма).

Въпроси и отговори

В: Какво е число на Ферма?

В: Колко са числата на Ферма?

В: Кои са първите девет числа на Ферма?

Въпрос: Какво може да се каже за простите числа от вида 2n + 1?

Въпрос: Къде могат да се намерят факторизациите на всички 12 известни фактории на числата на Ферма?

В: Кой е бил Пиер дьо Ферма?

Търсене по буква