Ֆերմայի թիվ

Վիքիպեդիայից՝ ազատ հանրագիտարանից

Ֆերմայի թվերը այս՝ F_n=2^{2^n}+1 տեսքի թվերն են, որտեղ n-ը ոչ բացասական ամբողջ թիվ է։ Ֆերմայի թվերի հաջորդականությունը սկսվում է այսպես.

3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, …

Պատմությունը[խմբագրել]

Այս տեսքի թվերի ուսումնասիրությունը սկսել է Ֆերման, և ըստ նրա առաջ քաշած հիպոթեզի դրանք բոլորը պարզ են։ Սակայն դա հերքել է Էյլերը 1732 թվին, վերլուծելով F_5-ը պարզ արտադրիչների՝

 F_5 = 4294967297 = 641 \cdot 6700417

Հատկությունները[խմբագրել]

և այդ պատճառով 2^n+1-ն չեն հանդիսանում պարզ:
  • Ֆերմայի թվերի պարզությունը կարելի է էֆֆեկտիվորեն պարզել Պեպինի թեստի միջոցով։
  • Այս պահի դրությամբ հայտնի է միայն 5 Ֆերմայի պարզ թիվ. 3, 5, 17, 257 և 65537:
  • Հայտնի է, որ F_n հանդիսանում են բաղադրյալ, եթե 5 \le n \le 32:

Պարզ արտադրիչների վերլուծություն[խմբագրել]

F_0=2^{2^0}+1=2^1+1 = 3
F_1=2^{2^1}+1=2^2+1 = 5
F_2=2^{2^2}+1=2^4+1 = 17
F_3=2^{2^3}+1=2^8+1 = 257
F_4=2^{2^4}+1=2^{16}+1 = 65537
F_5=2^{2^5}+1=2^{32}+1 = 4294967297 = (5 \cdot 2^{5+2}+1) \cdot (52347 \cdot 2^{5+2}+1) = 641 \cdot 6700417
F_6=2^{2^6}+1=2^{64}+1 =  18446744073709551617 = (1071 \cdot 2^{6+2}+1) \cdot (262'814'145'745 \cdot 2^{6+2}+1) = 274177 \cdot 67280421310721
\begin{array}{lll}F_7=2^{2^7}+1=2^{128}+1 & = & 340282366920938463463374607431768211457 =\\ & = & (116\,503\,103\,764\,643 \cdot 2^{7+2}+1) \cdot (11\,141\,971\,095\,088\,142\,685 \cdot 2^{7+2}+1) =\\ & = & 59\,649\,589\,127\,497\,217 \cdot 5\,704\,689\,200\,685\,129\,054\,721\end{array}
\begin{array}{lll}F_8=2^{2^8}+1=2^{256}+1 & = & 115792089237316195423570985008687907853269984665640564039457584007913129639937=\\ & = & (3853149761 \cdot 157 \cdot 2^{8+3}+1) \cdot \\ && <(1057372046781162536274034354686893329625329 \cdot 31618624099079 \cdot 13 \cdot 7 \cdot 5 \cdot 3 \cdot 2^{8+3}+1) =\\ & = & 1238926361552897 \cdot 93461639715357977769163558199606896584051237541638188580280321\end{array}

Հղումներ[խմբագրել]