फ़र्मेट संख्या

Fermat prime

Named after	Pierre de Fermat
No. of known terms	5
Conjectured no. of terms	5
Subsequence of	Fermat numbers
First terms	3, 5, 17, 257, 65537
Largest known term	65537
OEIS index	A019434

गणित में एक फ़र्मेट संख्या जिसका नाम पियरे डी फ़र्मेट के नाम पर रखा गया है जिन्होंने सबसे पहले उनका अध्ययन किया था इस रूप की एक प्राकृतिक संख्या है

$F_{n}=2^{2^{n}}+1,$

जहाँ n एक गैर-ऋणात्मक पूर्णांक है। पहले कुछ फ़र्मेट नंबर हैं:

3 (संख्या), 5 (संख्या), 17 (संख्या), 257 (संख्या), 65537 (संख्या), 4294967297, 18446744073709551617, ... (sequence A000215 in the OEIS).

यदि 2^k+1 अभाज्य संख्या है और k > 0, तो k 2 की घात होनी चाहिए, इसलिए 2^k + 1 एक फ़र्मेट संख्या है; ऐसे अभाज्यों को फर्मेट अभाज्य कहा जाता है। As of 2023, एकमात्र ज्ञात फ़र्मेट प्राइम हैं F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, और F₄ = 65537 (sequence A019434 in the OEIS); अनुमान बताते हैं कि अब और नहीं हैं।

मूलभूत गुण

फ़र्मेट संख्याएँ निम्नलिखित पुनरावृत्ति संबंध को संतुष्ट करती हैं:

$F_{n}=(F_{n-1}-1)^{2}+1$

$F_{n}=F_{0}\cdots F_{n-1}+2$

n ≥ 1 के लिए,

$F_{n}=F_{n-1}+2^{2^{n-1}}F_{0}\cdots F_{n-2}$

$F_{n}=F_{n-1}^{2}-2(F_{n-2}-1)^{2}$

n ≥ 2 के लिए इनमें से प्रत्येक संबंध को गणितीय प्रेरण द्वारा सिद्ध किया जा सकता है। दूसरे समीकरण से, हम गोल्डबैक के प्रमेय (क्रिश्चियन गोल्डबैक के नाम पर) का अनुमान लगा सकते हैं: कोई भी दो फ़र्मेट संख्याएं 1 से अधिक एक सामान्य पूर्णांक कारक साझा नहीं करती हैं। इसे देखने के लिए मान लें कि 0 ≤ i < j और F_i और F_j का एक सामान्य कारक a > 1 है फिर a दोनों को विभाजित करता है

$F_{0}\cdots F_{j-1}$

और F_j इसलिए a उनके अंतर को विभाजित करता है, 2. चूँकि a > 1, यह a = 2 को बल देता है। यह एक विरोधाभास है, क्योंकि प्रत्येक फ़र्मेट संख्या स्पष्ट रूप से विषम है। परिणाम के रूप में, हमें अभाज्य संख्याओं की अनंतता का एक और प्रमाण मिलता है: प्रत्येक F_n के लिए, एक अभाज्य गुणनखंड p_n चुनें; तो अनुक्रम {p_n} अलग-अलग अभाज्य संख्याओं का एक अनंत अनुक्रम है।

अतिरिक्त गुण

• किसी भी फ़र्मेट प्राइम को दो pth घातों के अंतर के रूप में व्यक्त नहीं किया जा सकता है, जहाँ p एक विषम प्राइम है।
• एफ को छोड़कर₀ और एफ₁, फ़र्मेट संख्या का अंतिम अंक 7 है।
• F₀ और F₁ के अपवाद के साथ, फ़र्मेट संख्या का अंतिम अंक 7 है।
• सभी फ़र्मेट संख्याओं के व्युत्क्रमों का योग (sequence A051158 in the OEIS) अपरिमेय संख्या है. (सोलोमन डब्ल्यू गोलोम्ब, 1963)

प्राचीनता

फ़र्मेट संख्याओं और फ़र्मेट प्राइम का अध्ययन सबसे पहले पियरे डी फ़र्मेट द्वारा किया गया था, जिन्होंने अनुमान लगाया था कि सभी फ़र्मेट संख्याएँ अभाज्य हैं। दरअसल, पहले पांच फ़र्मेट नंबर F₀, ..., F₄ को आसानी से अभाज्य दिखाया गया है। 1732 में लियोनहार्ड यूलर ने फ़र्मेट के अनुमान का खंडन किया जब उन्होंने दिखाया कि

$F_{5}=2^{2^{5}}+1=2^{32}+1=4294967297=641\times 6700417.$

यूलर ने सिद्ध किया कि n ≥ 2 के लिए F_n के प्रत्येक कारक का रूप k 2ⁿ⁺¹ + 1 होना चाहिए (बाद में लुकास द्वारा इसे k 2ⁿ⁺² + 1 में सुधार किया गया)।

यह कि 641, F₅ का एक गुणनखंड है, समानता 641 = 2⁷ × 5 + 1 और 641 = 2⁴ + 5⁴ से निकाला जा सकता है। यह पहली समानता से पता चलता है कि 2⁷ × 5 ≡ −1 (मॉड 641) और इसलिए (बढ़ाते हुए) चौथी शक्ति) वह 2²⁸ × 5⁴ ≡ 1 (मॉड 641)दूसरी ओर, दूसरी समानता का तात्पर्य है कि 5⁴ ≡ −2⁴ (मॉड 641)। इन सर्वांगसमताओं का अर्थ है कि 2³² ≡ −1 (मॉड 641)।

फ़र्मेट को संभवतः यूलर द्वारा बाद में सिद्ध किए गए कारकों के स्वरूप के बारे में पता था, इसलिए यह उत्सुक लगता है कि वह कारक को खोजने के लिए सीधी गणना का पालन करने में विफल रहा। एक सामान्य व्याख्या यह है कि फ़र्मेट ने एक कम्प्यूटेशनल गलती की है।

n > 4 के साथ कोई अन्य ज्ञात फ़र्मेट अभाज्य F_n नहीं है, किन्तु बड़े n के लिए फ़र्मेट संख्याओं के बारे में बहुत कम जानकारी है। वास्तव में, निम्नलिखित में से प्रत्येक एक खुली समस्या है:

• F_n सभी के लिए भाज्य संख्या n > 4? है
• क्या फ़र्मेट अभाज्य अनंत रूप से अनेक हैं? (गोटथोल्ड आइज़ेंस्टीन 1844)
• क्या मिश्रित फ़र्मेट संख्याएँ अपरिमित रूप से अनेक हैं?
• क्या कोई फ़र्मेट संख्या उपस्थित है जो वर्ग-मुक्त संख्या या वर्ग-मुक्त नहीं है?

2014 तक, यह ज्ञात है कि F_n 5 ≤ n ≤ 32 के लिए मिश्रित है, चूँकि इनमें से, F_n का पूर्ण गुणनखंडन केवल 0 ≤ n ≤ 11 के लिए जाना जाता है, और n = 20 और n = 24 के लिए कोई ज्ञात अभाज्य कारक नहीं हैं। समग्र के रूप में ज्ञात सबसे बड़ी फ़र्मेट संख्या F_18233954 है, और इसका अभाज्य कारक 7 × 2^18233956 + 1 अक्टूबर 2020 में खोजा गया था।

विवेकपूर्ण तर्क

अनुमान बताते हैं कि एफ₄ अंतिम फ़र्मेट प्राइम है।

अभाज्य संख्या प्रमेय का तात्पर्य है कि N के चारों ओर एक उपयुक्त अंतराल में एक यादृच्छिक पूर्णांक संभाव्यता 1 के साथ अभाज्य है / एलएन एन. यदि कोई अनुमान का उपयोग करता है कि एक फ़र्मेट संख्या उसके आकार के यादृच्छिक पूर्णांक के समान संभावना के साथ अभाज्य है, और वह एफ₅, ..., एफ₃₂ मिश्रित हैं, तो F से परे फ़र्मेट अभाज्यों की अपेक्षित संख्या₄ (या समकक्ष, एफ से परे₃₂) होना चाहिए

$\sum _{n\geq 33}{\frac {1}{\ln F_{n}}}<{\frac {1}{\ln 2}}\sum _{n\geq 33}{\frac {1}{\log _{2}(2^{2^{n}})}}={\frac {1}{\ln 2}}2^{-32}<3.36\times 10^{-10}.$

कोई इस संख्या की व्याख्या इस संभावना की ऊपरी सीमा के रूप में कर सकता है कि F से परे एक फ़र्मेट प्राइम है₄ मौजूद।

यह तर्क कोई कठोर प्रमाण नहीं है. एक बात के लिए, यह माना जाता है कि फ़र्मेट संख्याएँ यादृच्छिक रूप से व्यवहार करती हैं, किन्तु फ़र्मेट संख्याओं के कारकों में विशेष गुण होते हैं। बोकलान और जॉन एच. कॉनवे ने एक अधिक सटीक विश्लेषण प्रकाशित किया जिसमें बताया गया कि एक और फ़र्मेट प्राइम होने की संभावना एक अरब में एक से भी कम है।

समतुल्य स्थितियाँ

Main article: Pépin's test

होने देना $F_{n}=2^{2^{n}}+1$ nवाँ फ़र्मेट नंबर हो। पेपिन का परीक्षण बताता है कि n > 0,

$F_{n}$ प्रधान है यदि और केवल यदि $3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}.$

इजहार $3^{(F_{n}-1)/2}$ मॉड्यूलो का मूल्यांकन किया जा सकता है $F_{n}$ घातांक द्वारा, वर्ग करके। यह परीक्षण को एक तेज़ बहुपद-समय एल्गोरिथ्म बनाता है। किन्तु फ़र्मेट संख्याएँ इतनी तेज़ी से बढ़ती हैं कि उनमें से केवल मुट्ठी भर का ही उचित मात्रा और स्थान में परीक्षण किया जा सकता है।

फॉर्म के नंबरों के लिए कुछ परीक्षण होते हैं k 2^m + 1, जैसे कि फ़र्मेट संख्या के कारक, आदिमता के लिए।

प्रोथ का प्रमेय (1878)। होने देना N = k 2^m + 1 विषम के साथ k < 2^m. यदि कोई पूर्णांक ऐसा है

$a^{(N-1)/2}\equiv -1{\pmod {N}}$

तब $N$ प्रधान है. इसके विपरीत, यदि उपरोक्त अनुरूपता कायम नहीं है, और इसके अतिरिक्त

$\left({\frac {a}{N}}\right)=-1$ (जेकोबी प्रतीक देखें)

तब $N$ समग्र है.

अगर N = F_n > 3, तो उपरोक्त जैकोबी प्रतीक हमेशा −1 के बराबर होता है a = 3, और प्रोथ के प्रमेय के इस विशेष मामले को पेपिन परीक्षण के रूप में जाना जाता है। चूँकि पेपिन के परीक्षण और प्रोथ के प्रमेय को कुछ फ़र्मेट संख्याओं की समग्रता को साबित करने के लिए कंप्यूटर पर लागू किया गया है, किन्तु कोई भी परीक्षण एक विशिष्ट गैर-तुच्छ कारक नहीं देता है। वास्तव में, कोई विशिष्ट अभाज्य कारक ज्ञात नहीं हैं n = 20 और 24.

गुणनखंडीकरण

फ़र्मेट संख्याओं के आकार के कारण, गुणनखंड बनाना या यहां तक ​​कि प्रारंभिकता की जांच करना भी मुश्किल है। पेपिन का परीक्षण फ़र्मेट संख्याओं की प्रारंभिकता के लिए एक आवश्यक और पर्याप्त स्थिति देता है, और इसे आधुनिक कंप्यूटरों द्वारा कार्यान्वित किया जा सकता है। अण्डाकार वक्र विधि संख्याओं के छोटे अभाज्य विभाजक ज्ञात करने की एक तेज़ विधि है। वितरित कंप्यूटिंग परियोजना Fermatsearch ने Fermat संख्याओं के कुछ कारक ढूंढे हैं। यवेस गैलोट के proth.exe का उपयोग बड़े फ़र्मेट संख्याओं के गुणनखंडों को खोजने के लिए किया गया है। एडौर्ड लुकास ने यूलर के उपर्युक्त परिणाम में सुधार करते हुए 1878 में साबित किया कि फ़र्मेट संख्या का प्रत्येक कारक $F_{n}$, कम से कम 2 के साथ, फॉर्म का है $k\times 2^{n+2}+1$ (प्रोथ संख्या देखें), जहां k एक धनात्मक पूर्णांक है। अपने आप में, इससे ज्ञात फ़र्मेट अभाज्यों की आदिमता को सिद्ध करना आसान हो जाता है।

पहले बारह फ़र्मेट संख्याओं के गुणनखंडन इस प्रकार हैं:

F0	=	21	+	1	=	3 is prime
F1	=	22	+	1	=	5 is prime
F2	=	24	+	1	=	17 is prime
F3	=	28	+	1	=	257 is prime
F4	=	216	+	1	=	65,537 is the largest known Fermat prime
F5	=	232	+	1	=	4,294,967,297
					=	641 × 6,700,417 (fully factored 1732)
F6	=	264	+	1	=	18,446,744,073,709,551,617 (20 digits)
					=	274,177 × 67,280,421,310,721 (14 digits) (fully factored 1855)
F7	=	2128	+	1	=	340,282,366,920,938,463,463,374,607,431,768,211,457 (39 digits)
					=	59,649,589,127,497,217 (17 digits) × 5,704,689,200,685,129,054,721 (22 digits) (fully factored 1970)
F8	=	2256	+	1	=	115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129, 639,937 (78 digits)
					=	1,238,926,361,552,897 (16 digits) × 93,461,639,715,357,977,769,163,558,199,606,896,584,051,237,541,638,188,580,280,321 (62 digits) (fully factored 1980)
F9	=	2512	+	1	=	13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,592,393,377,723,561,443,721,764,0 30,073,546,976,801,874,298,166,903,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,6 49,006,084,097 (155 digits)
					=	2,424,833 × 7,455,602,825,647,884,208,337,395,736,200,454,918,783,366,342,657 (49 digits) × 741,640,062,627,530,801,524,787,141,901,937,474,059,940,781,097,519,023,905,821,316,144,415,759, 504,705,008,092,818,711,693,940,737 (99 digits) (fully factored 1990)
F10	=	21024	+	1	=	179,769,313,486,231,590,772,930...304,835,356,329,624,224,137,217 (309 digits)
					=	45,592,577 × 6,487,031,809 × 4,659,775,785,220,018,543,264,560,743,076,778,192,897 (40 digits) × 130,439,874,405,488,189,727,484...806,217,820,753,127,014,424,577 (252 digits) (fully factored 1995)
F11	=	22048	+	1	=	32,317,006,071,311,007,300,714,8...193,555,853,611,059,596,230,657 (617 digits)
					=	319,489 × 974,849 × 167,988,556,341,760,475,137 (21 digits) × 3,560,841,906,445,833,920,513 (22 digits) × 173,462,447,179,147,555,430,258...491,382,441,723,306,598,834,177 (564 digits) (fully factored 1988)

As of April 2023, केवल एफ₀ एफ को₁₁ पूरी तरह से पूर्णांक गुणनखंडन किया गया है।वितरित कंप्यूटिंग प्रोजेक्ट फ़र्मेट सर्च फ़र्मेट संख्याओं के नए कारकों की खोज कर रहा है। पूर्णांक अनुक्रमों के ऑन-लाइन विश्वकोश में सभी फ़र्मेट कारकों का सेट OEIS:A050922 (या, क्रमबद्ध, OEIS:A023394) है।

फ़र्मेट संख्या के निम्नलिखित कारक 1950 से पहले ज्ञात थे (तब से, डिजिटल कंप्यूटर ने अधिक कारकों को खोजने में मदद की है):

Year	Finder	Fermat number	Factor
1732	Euler	$F_{5}$	$5\cdot 2^{7}+1$
1732	Euler	$F_{5}$ (fully factored)	$52347\cdot 2^{7}+1$
1855	Clausen	$F_{6}$	$1071\cdot 2^{8}+1$
1855	Clausen	$F_{6}$ (fully factored)	$262814145745\cdot 2^{8}+1$
1877	Pervushin	$F_{12}$	$7\cdot 2^{14}+1$
1878	Pervushin	$F_{23}$	$5\cdot 2^{25}+1$
1886	Seelhoff	$F_{36}$	$5\cdot 2^{39}+1$
1899	Cunningham	$F_{11}$	$39\cdot 2^{13}+1$
1899	Cunningham	$F_{11}$	$119\cdot 2^{13}+1$
1903	Western	$F_{9}$	$37\cdot 2^{16}+1$
1903	Western	$F_{12}$	$397\cdot 2^{16}+1$
1903	Western	$F_{12}$	$973\cdot 2^{16}+1$
1903	Western	$F_{18}$	$13\cdot 2^{20}+1$
1903	Cullen	$F_{38}$	$3\cdot 2^{41}+1$
1906	Morehead	$F_{73}$	$5\cdot 2^{75}+1$
1925	Kraitchik	$F_{15}$	$579\cdot 2^{21}+1$

As of April 2023, फ़र्मेट संख्याओं के 362 अभाज्य गुणनखंड ज्ञात हैं, और 318 फ़र्मेट संख्याओं को मिश्रित माना जाता है। हर साल कई नए फ़र्मेट कारक पाए जाते हैं।

स्यूडोप्राइम्स और फ़र्मेट संख्याएँ

प्रपत्र 2 की भाज्य संख्याओं की तरह^पी - 1, प्रत्येक मिश्रित फ़र्मेट संख्या आधार 2 के लिए एक मजबूत छद्म अभाज्य है। ऐसा इसलिए है क्योंकि आधार 2 के लिए सभी मजबूत छद्म अभाज्य भी फ़र्मेट छद्म अभाज्य हैं - अर्थात,

$2^{F_{n}-1}\equiv 1{\pmod {F_{n}}}$

सभी फ़र्मेट नंबरों के लिए.

1904 में, सिपोला ने दिखाया कि कम से कम दो अलग-अलग अभाज्य या मिश्रित फ़र्मेट संख्याओं का गुणनफल $F_{a}F_{b}\dots F_{s},$ $a>b>\dots >s>1$ आधार 2 के लिए एक फ़र्मेट स्यूडोप्राइम होगा यदि और केवल यदि $2^{s}>a$.

फ़र्मेट संख्याओं के बारे में अन्य प्रमेय

Lemma. — If n is a positive integer,

$a^{n}-b^{n}=(a-b)\sum _{k=0}^{n-1}a^{k}b^{n-1-k}.$

Proof

${\begin{aligned}(a-b)\sum _{k=0}^{n-1}a^{k}b^{n-1-k}&=\sum _{k=0}^{n-1}a^{k+1}b^{n-1-k}-\sum _{k=0}^{n-1}a^{k}b^{n-k}\\&=a^{n}+\sum _{k=1}^{n-1}a^{k}b^{n-k}-\sum _{k=1}^{n-1}a^{k}b^{n-k}-b^{n}\\&=a^{n}-b^{n}\end{aligned}}$

Theorem —  If $2^{k}+1$ is an odd prime, then $k$ is a power of 2.

Proof

If $k$ is a positive integer but not a power of 2, it must have an odd prime factor $s>2$, and we may write $k=rs$ where $1\leq r<k$.

By the preceding lemma, for positive integer $m$,

$(a-b)\mid (a^{m}-b^{m})$

where $\mid$ means "evenly divides". Substituting $a=2^{r},b=-1$, and $m=s$ and using that $s$ is odd,

$(2^{r}+1)\mid (2^{rs}+1),$

and thus

$(2^{r}+1)\mid (2^{k}+1).$

Because $1<2^{r}+1<2^{k}+1$, it follows that $2^{k}+1$ is not prime. Therefore, by contraposition $k$ must be a power of 2.

Theorem —  A Fermat prime cannot be a Wieferich prime.

Proof

We show if $p=2^{m}+1$ is a Fermat prime (and hence by the above, m is a power of 2), then the congruence $2^{p-1}\equiv 1{\bmod {p^{2}}}$ does not hold.

Since $2m|p-1$ we may write $p-1=2m\lambda$. If the given congruence holds, then $p^{2}|2^{2m\lambda }-1$, and therefore

$0\equiv {\frac {2^{2m\lambda }-1}{2^{m}+1}}=(2^{m}-1)\left(1+2^{2m}+2^{4m}+\cdots +2^{2(\lambda -1)m}\right)\equiv -2\lambda {\pmod {2^{m}+1}}.$

Hence $2^{m}+1|2\lambda$, and therefore $2\lambda \geq 2^{m}+1$. This leads to $p-1\geq m(2^{m}+1)$, which is impossible since $m\geq 2$.

Theorem (Édouard Lucas) —  Any prime divisor p of $F_{n}=2^{2^{n}}+1$ is of the form $k2^{n+2}+1$ whenever n > 1.

Sketch of proof

Let G_p denote the group of non-zero integers modulo p under multiplication, which has order p − 1. Notice that 2 (strictly speaking, its image modulo p) has multiplicative order equal to $2^{n+1}$ in G_p (since $2^{2^{n+1}}$ is the square of $2^{2^{n}}$ which is −1 modulo F_n), so that, by Lagrange's theorem, p − 1 is divisible by $2^{n+1}$ and p has the form $k2^{n+1}+1$ for some integer k, as Euler knew. Édouard Lucas went further. Since n > 1, the prime p above is congruent to 1 modulo 8. Hence (as was known to Carl Friedrich Gauss), 2 is a quadratic residue modulo p, that is, there is integer a such that $p|a^{2}-2.$ Then the image of a has order $2^{n+2}$ in the group G_p and (using Lagrange's theorem again), p − 1 is divisible by $2^{n+2}$ and p has the form $s2^{n+2}+1$ for some integer s.

In fact, it can be seen directly that 2 is a quadratic residue modulo p, since

$\left(1+2^{2^{n-1}}\right)^{2}\equiv 2^{1+2^{n-1}}{\pmod {p}}.$

Since an odd power of 2 is a quadratic residue modulo p, so is 2 itself.

एक फ़र्मेट नंबर एक पूर्ण संख्या या सौहार्दपूर्ण संख्याओं की जोड़ी का हिस्सा नहीं हो सकता है। (Luca 2000)

फ़र्मेट संख्याओं के सभी अभाज्य विभाजकों के व्युत्क्रमों की श्रृंखला अभिसारी श्रृंखला है। (Křížek, Luca & Somer 2002)

अगर nⁿ + 1 अभाज्य है, ऐसा एक पूर्णांक m उपस्थित है n = 2^2m. समीकरण nⁿ + 1 = F_(2^m+m) उस मामले में रखता है. माना कि फ़र्मेट संख्या F का सबसे बड़ा अभाज्य गुणनखंड है_n पी(एफ) हो_n). तब,

$P(F_{n})\geq 2^{n+2}(4n+9)+1.$ (Grytczuk, Luca & Wójtowicz 2001)

रचनात्मक बहुभुजों से संबंध

1000 भुजाओं तक ज्ञात निर्माण योग्य बहुभुजों की भुजाओं की संख्या (बोल्ड) या विषम भुजाओं की संख्या (लाल)

Main article: Constructible polygon

कार्ल फ्रेडरिक गॉस ने अपने अंकगणितीय विवेचन में गॉसियन काल के सिद्धांत को विकसित किया और नियमित बहुभुजों की रचना के लिए पर्याप्त शर्त तैयार की। गॉस ने कहा कि यह शर्त भी आवश्यक शर्त थी, किन्तु कभी कोई प्रमाण प्रकाशित नहीं किया। पियरे वांटज़ेल ने 1837 में आवश्यकता का पूर्ण प्रमाण दिया। परिणाम को गॉस-वांटज़ेल प्रमेय के रूप में जाना जाता है:

एक एन-पक्षीय नियमित बहुभुज का निर्माण कम्पास और सीधा किनारा के साथ किया जा सकता है यदि और केवल यदि एन 2 की शक्ति और अलग-अलग फ़र्मेट प्राइम का उत्पाद है: दूसरे शब्दों में, यदि और केवल यदि n रूप का है n = 2^kp₁p₂...p_s, जहां k, s अऋणात्मक पूर्णांक हैं और p_i विशिष्ट फ़र्मेट अभाज्य हैं।

एक धनात्मक पूर्णांक n उपरोक्त रूप का है यदि और केवल यदि इसका यूलर का टोटिएंट फ़ंक्शन φ(n) 2 की शक्ति है।

फ़र्मेट संख्याओं का अनुप्रयोग

छद्म यादृच्छिक संख्या पीढ़ी

फ़र्मेट प्राइम्स विशेष रूप से 1, ..., एन की श्रेणी में संख्याओं के छद्म-यादृच्छिक अनुक्रम उत्पन्न करने में उपयोगी होते हैं, जहां एन 2 की शक्ति है। उपयोग की जाने वाली सबसे आम विधि 1 और के बीच किसी भी बीज मूल्य को लेना है P − 1, जहां P एक फ़र्मेट प्राइम है। अब इसे एक संख्या A से गुणा करें, जो P के वर्गमूल से अधिक है और एक आदिम मूल modulo n modulo P है (यानी, यह एक द्विघात अवशेष नहीं है)। फिर परिणाम मॉड्यूल पी लें। परिणाम आरएनजी के लिए नया मान है।

$V_{j+1}=(A\times V_{j}){\bmod {P}}$ (रैखिक सर्वांगसम जनरेटर, RANDU देखें)

यह कंप्यूटर विज्ञान में उपयोगी है, क्योंकि अधिकांश डेटा संरचनाओं में 2 सदस्य होते हैं^Xसंभावित मान. उदाहरण के लिए, एक बाइट में 256 (2) होता है⁸) संभावित मान (0-255)। इसलिए, किसी बाइट या बाइट्स को यादृच्छिक मानों से भरने के लिए, एक यादृच्छिक संख्या जनरेटर का उपयोग किया जा सकता है जो 1-256 मान उत्पन्न करता है, बाइट आउटपुट मान -1 लेता है। इस कारण से बहुत बड़े फ़र्मेट प्राइम डेटा एन्क्रिप्शन में विशेष रुचि रखते हैं। यह विधि केवल छद्म यादृच्छिक मान उत्पन्न करती है, जैसा कि बाद में हुआ P − 1 पुनरावृत्ति, अनुक्रम दोहराता है। खराब तरीके से चुने गए गुणक के परिणामस्वरूप अनुक्रम जल्दी दोहराया जा सकता है P − 1.

सामान्यीकृत फ़र्मेट संख्या

फॉर्म के नंबर $a^{2^{\overset {n}{}}}\!\!+b^{2^{\overset {n}{}}}$ ए, बी के साथ कोई सहअभाज्य पूर्णांक, a > b > 0, सामान्यीकृत फ़र्मेट संख्याएँ कहलाती हैं। एक विषम अभाज्य पी एक सामान्यीकृत फ़र्मेट संख्या है यदि और केवल तभी जब पी पायथागॉरियन अभाज्य|1 (मॉड 4) के सर्वांगसम हो। (यहां हम केवल मामले पर विचार करते हैं n > 0, इसलिए 3 = $2^{2^{0}}\!+1$ एक प्रतिउदाहरण नहीं है।)

इस फॉर्म के संभावित अभाज्य का एक उदाहरण 1215 है¹³¹⁰⁷²+242¹³¹⁰⁷² (केलेन शेंटन द्वारा पाया गया)। सामान्य फ़र्मेट संख्याओं के अनुरूप, प्रपत्र की सामान्यीकृत फ़र्मेट संख्याएँ लिखना आम बात है $a^{2^{\overset {n}{}}}\!\!+1$ एफ के रूप में_n(ए)। उदाहरण के लिए, इस नोटेशन में संख्या 100,000,001 को F के रूप में लिखा जाएगा₃(10). निम्नलिखित में हम स्वयं को इस रूप के अभाज्य संख्याओं तक ही सीमित रखेंगे, $a^{2^{\overset {n}{}}}\!\!+1$, ऐसे अभाज्यों को फ़र्मेट अभाज्य आधार a कहा जाता है। निःसंदेह, ये अभाज्य संख्याएँ केवल तभी उपस्थित होती हैं जब a समता (गणित) हो।

अगर हमें आवश्यकता है n > 0, फिर लैंडौ की समस्याएं|लैंडौ की चौथी समस्या पूछती है कि क्या अनंत रूप से कई सामान्यीकृत फ़र्मेट अभाज्य एफ हैं_n(ए)।

सामान्यीकृत फ़र्मेट अभाज्य

अपनी आदिमता को साबित करने में आसानी के कारण, सामान्यीकृत फ़र्मेट प्राइम हाल के वर्षों में संख्या सिद्धांत के क्षेत्र में शोध का विषय बन गए हैं। आज के सबसे बड़े ज्ञात अभाज्यों में से कई सामान्यीकृत फ़र्मेट अभाज्य हैं।

सामान्यीकृत फ़र्मेट संख्याएँ केवल सम के लिए अभाज्य हो सकती हैं a, क्योंकि अगर a विषम है तो प्रत्येक सामान्यीकृत फ़र्मेट संख्या 2 से विभाज्य होगी। सबसे छोटी अभाज्य संख्या $F_{n}(a)$ साथ $n>4$ है $F_{5}(30)$, या 30³² + 1. इसके अलावा, हम एक विषम आधार के लिए आधे सामान्यीकृत फ़र्मेट संख्याओं को परिभाषित कर सकते हैं, आधार a के लिए एक आधा सामान्यीकृत फ़र्मेट संख्या (विषम a के लिए) है ${\frac {a^{2^{n}}\!+1}{2}}$, और यह भी उम्मीद की जानी चाहिए कि प्रत्येक विषम आधार के लिए केवल सीमित रूप से कई आधे सामान्यीकृत फ़र्मेट अभाज्य होंगे।

(सूची में, सामान्यीकृत फ़र्मेट संख्याएँ ($F_{n}(a)$) एक सम तक a हैं $a^{2^{n}}\!+1$, विषम के लिए a, वे हैं ${\frac {a^{2^{n}}\!\!+1}{2}}$. अगर a एक विषम घातांक वाली एक पूर्ण शक्ति है (sequence A070265 in the OEIS), तो सभी सामान्यीकृत फ़र्मेट संख्या को बीजगणितीय गुणनखंडित किया जा सकता है, इसलिए वे अभाज्य नहीं हो सकते)

(सबसे छोटी संख्या के लिए $n$ ऐसा है कि $F_{n}(a)$ प्रधान है, देखिये OEIS: A253242)

$a$	numbers $n$ such that $F_{n}(a)$ is prime	$a$	numbers $n$ such that $F_{n}(a)$ is prime	$a$	numbers $n$ such that $F_{n}(a)$ is prime	$a$	numbers $n$ such that $F_{n}(a)$ is prime
2	0, 1, 2, 3, 4, ...	18	0, ...	34	2, ...	50	...
3	0, 1, 2, 4, 5, 6, ...	19	1, ...	35	1, 2, 6, ...	51	1, 3, 6, ...
4	0, 1, 2, 3, ...	20	1, 2, ...	36	0, 1, ...	52	0, ...
5	0, 1, 2, ...	21	0, 2, 5, ...	37	0, ...	53	3, ...
6	0, 1, 2, ...	22	0, ...	38	...	54	1, 2, 5, ...
7	2, ...	23	2, ...	39	1, 2, ...	55	...
8	(none)	24	1, 2, ...	40	0, 1, ...	56	1, 2, ...
9	0, 1, 3, 4, 5, ...	25	0, 1, ...	41	4, ...	57	0, 2, ...
10	0, 1, ...	26	1, ...	42	0, ...	58	0, ...
11	1, 2, ...	27	(none)	43	3, ...	59	1, ...
12	0, ...	28	0, 2, ...	44	4, ...	60	0, ...
13	0, 2, 3, ...	29	1, 2, 4, ...	45	0, 1, ...	61	0, 1, 2, ...
14	1, ...	30	0, 5, ...	46	0, 2, 9, ...	62	...
15	1, ...	31	...	47	3, ...	63	...
16	0, 1, 2, ...	32	(none)	48	2, ...	64	(none)
17	2, ...	33	0, 3, ...	49	1, ...	65	1, 2, 5, ...

b	known generalized (half) Fermat prime base b
2	3, 5, 17, 257, 65537
3	2, 5, 41, 21523361, 926510094425921, 1716841910146256242328924544641
4	5, 17, 257, 65537
5	3, 13, 313
6	7, 37, 1297
7	1201
8	(not possible)
9	5, 41, 21523361, 926510094425921, 1716841910146256242328924544641
10	11, 101
11	61, 7321
12	13
13	7, 14281, 407865361
14	197
15	113
16	17, 257, 65537
17	41761
18	19
19	181
20	401, 160001
21	11, 97241, 1023263388750334684164671319051311082339521
22	23
23	139921
24	577, 331777
25	13, 313
26	677
27	(not possible)
28	29, 614657
29	421, 353641, 125123236840173674393761
30	31, 185302018885184100000000000000000000000000000001
31
32	(not possible)
33	17, 703204309121
34	1336337
35	613, 750313, 330616742651687834074918381127337110499579842147487712949050636668246738736343104392290115356445313
36	37, 1297
37	19
38
39	761, 1156721
40	41, 1601
41	31879515457326527173216321
42	43
43	5844100138801
44	197352587024076973231046657
45	23, 1013
46	47, 4477457, 46512+1 (852 digits: 214787904487...289480994817)
47	11905643330881
48	5308417
49	1201
50

(देखना अधिक जानकारी के लिए (1000 तक के आधार भी), यह भी देखें विषम आधारों के लिए)

(प्रपत्र के सबसे छोटे अभाज्य के लिए $F_{n}(a,b)$ (विषम के लिए $a+b$), यह सभी देखें OEIS: A111635)

$a$	$b$	numbers $n$ such that ${\frac {a^{2^{n}}+b^{2^{n}}}{\gcd(a+b,2)}}(=F_{n}(a,b))$ is prime
2	1	0, 1, 2, 3, 4, ...
3	1	0, 1, 2, 4, 5, 6, ...
3	2	0, 1, 2, ...
4	1	0, 1, 2, 3, ...
4	3	0, 2, 4, ...
5	1	0, 1, 2, ...
5	2	0, 1, 2, ...
5	3	1, 2, 3, ...
5	4	1, 2, ...
6	1	0, 1, 2, ...
6	5	0, 1, 3, 4, ...
7	1	2, ...
7	2	1, 2, ...
7	3	0, 1, 8, ...
7	4	0, 2, ...
7	5	1, 4, ...
7	6	0, 2, 4, ...
8	1	(none)
8	3	0, 1, 2, ...
8	5	0, 1, 2, ...
8	7	1, 4, ...
9	1	0, 1, 3, 4, 5, ...
9	2	0, 2, ...
9	4	0, 1, ...
9	5	0, 1, 2, ...
9	7	2, ...
9	8	0, 2, 5, ...
10	1	0, 1, ...
10	3	0, 1, 3, ...
10	7	0, 1, 2, ...
10	9	0, 1, 2, ...
11	1	1, 2, ...
11	2	0, 2, ...
11	3	0, 3, ...
11	4	1, 2, ...
11	5	1, ...
11	6	0, 1, 2, ...
11	7	2, 4, 5, ...
11	8	0, 6, ...
11	9	1, 2, ...
11	10	5, ...
12	1	0, ...
12	5	0, 4, ...
12	7	0, 1, 3, ...
12	11	0, ...
13	1	0, 2, 3, ...
13	2	1, 3, 9, ...
13	3	1, 2, ...
13	4	0, 2, ...
13	5	1, 2, 4, ...
13	6	0, 6, ...
13	7	1, ...
13	8	1, 3, 4, ...
13	9	0, 3, ...
13	10	0, 1, 2, 4, ...
13	11	2, ...
13	12	1, 2, 5, ...
14	1	1, ...
14	3	0, 3, ...
14	5	0, 2, 4, 8, ...
14	9	0, 1, 8, ...
14	11	1, ...
14	13	2, ...
15	1	1, ...
15	2	0, 1, ...
15	4	0, 1, ...
15	7	0, 1, 2, ...
15	8	0, 2, 3, ...
15	11	0, 1, 2, ...
15	13	1, 4, ...
15	14	0, 1, 2, 4, ...
16	1	0, 1, 2, ...
16	3	0, 2, 8, ...
16	5	1, 2, ...
16	7	0, 6, ...
16	9	1, 3, ...
16	11	2, 4, ...
16	13	0, 3, ...
16	15	0, ...

(सबसे छोटे सम आधार के लिए a ऐसा है कि $F_{n}(a)$ प्रधान है, देखिये OEIS: A056993)

$n$	bases a such that $F_{n}(a)$ is prime (only consider even a)	OEIS sequence
0	2, 4, 6, 10, 12, 16, 18, 22, 28, 30, 36, 40, 42, 46, 52, 58, 60, 66, 70, 72, 78, 82, 88, 96, 100, 102, 106, 108, 112, 126, 130, 136, 138, 148, 150, ...	A006093
1	2, 4, 6, 10, 14, 16, 20, 24, 26, 36, 40, 54, 56, 66, 74, 84, 90, 94, 110, 116, 120, 124, 126, 130, 134, 146, 150, 156, 160, 170, 176, 180, 184, ...	A005574
2	2, 4, 6, 16, 20, 24, 28, 34, 46, 48, 54, 56, 74, 80, 82, 88, 90, 106, 118, 132, 140, 142, 154, 160, 164, 174, 180, 194, 198, 204, 210, 220, 228, ...	A000068
3	2, 4, 118, 132, 140, 152, 208, 240, 242, 288, 290, 306, 378, 392, 426, 434, 442, 508, 510, 540, 542, 562, 596, 610, 664, 680, 682, 732, 782, ...	A006314
4	2, 44, 74, 76, 94, 156, 158, 176, 188, 198, 248, 288, 306, 318, 330, 348, 370, 382, 396, 452, 456, 470, 474, 476, 478, 560, 568, 598, 642, ...	A006313
5	30, 54, 96, 112, 114, 132, 156, 332, 342, 360, 376, 428, 430, 432, 448, 562, 588, 726, 738, 804, 850, 884, 1068, 1142, 1198, 1306, 1540, 1568, ...	A006315
6	102, 162, 274, 300, 412, 562, 592, 728, 1084, 1094, 1108, 1120, 1200, 1558, 1566, 1630, 1804, 1876, 2094, 2162, 2164, 2238, 2336, 2388, ...	A006316
7	120, 190, 234, 506, 532, 548, 960, 1738, 1786, 2884, 3000, 3420, 3476, 3658, 4258, 5788, 6080, 6562, 6750, 7692, 8296, 9108, 9356, 9582, ...	A056994
8	278, 614, 892, 898, 1348, 1494, 1574, 1938, 2116, 2122, 2278, 2762, 3434, 4094, 4204, 4728, 5712, 5744, 6066, 6508, 6930, 7022, 7332, ...	A056995
9	46, 1036, 1318, 1342, 2472, 2926, 3154, 3878, 4386, 4464, 4474, 4482, 4616, 4688, 5374, 5698, 5716, 5770, 6268, 6386, 6682, 7388, 7992, ...	A057465
10	824, 1476, 1632, 2462, 2484, 2520, 3064, 3402, 3820, 4026, 6640, 7026, 7158, 9070, 12202, 12548, 12994, 13042, 15358, 17646, 17670, ...	A057002
11	150, 2558, 4650, 4772, 11272, 13236, 15048, 23302, 26946, 29504, 31614, 33308, 35054, 36702, 37062, 39020, 39056, 43738, 44174, 45654, ...	A088361
12	1534, 7316, 17582, 18224, 28234, 34954, 41336, 48824, 51558, 51914, 57394, 61686, 62060, 89762, 96632, 98242, 100540, 101578, 109696, ...	A088362
13	30406, 71852, 85654, 111850, 126308, 134492, 144642, 147942, 150152, 165894, 176206, 180924, 201170, 212724, 222764, 225174, 241600, ...	A226528
14	67234, 101830, 114024, 133858, 162192, 165306, 210714, 216968, 229310, 232798, 422666, 426690, 449732, 462470, 468144, 498904, 506664, ...	A226529
15	70906, 167176, 204462, 249830, 321164, 330716, 332554, 429370, 499310, 524552, 553602, 743788, 825324, 831648, 855124, 999236, 1041870, ...	A226530
16	48594, 108368, 141146, 189590, 255694, 291726, 292550, 357868, 440846, 544118, 549868, 671600, 843832, 857678, 1024390, 1057476, 1087540, ...	A251597
17	62722, 130816, 228188, 386892, 572186, 689186, 909548, 1063730, 1176694, 1361244, 1372930, 1560730, 1660830, 1717162, 1722230, 1766192, ...	A253854
18	24518, 40734, 145310, 361658, 525094, 676754, 773620, 1415198, 1488256, 1615588, 1828858, 2042774, 2514168, 2611294, 2676404, 3060772, ...	A244150
19	75898, 341112, 356926, 475856, 1880370, 2061748, 2312092, 2733014, 2788032, 2877652, 2985036, 3214654, 3638450, 4896418, 5897794, ...	A243959
20	919444, 1059094, 1951734, 1963736, ...	A321323

सबसे छोटा आधार b इस प्रकार है कि b²ⁿ + 1 अभाज्य हैं

2, 2, 2, 2, 2, 30, 102, 120, 278, 46, 824, 150, 1534, 30406, 67234, 70906, 48594, 62722, 24518, 75898, 919444, ... (sequence A056993 in the OEIS)

सबसे छोटा k ऐसा है कि (2n)^k+1 अभाज्य हैं

1, 1, 1, 0, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 0, 4, 1, ... (अगला पद अज्ञात है) (sequence A079706 in the OEIS) (यह भी देखें OEIS: A228101 और OEIS: A084712)

जिसके लिए आधारों की संख्या की भविष्यवाणी करने के लिए एक अधिक विस्तृत सिद्धांत का उपयोग किया जा सकता है $F_{n}(a)$ तय के लिए प्रमुख होगा $n$. सामान्यीकृत फ़र्मेट प्राइम की संख्या मोटे तौर पर आधी होने की उम्मीद की जा सकती है $n$ 1 से बढ़ गया है.

सबसे बड़ा ज्ञात सामान्यीकृत फ़र्मेट अभाज्य

निम्नलिखित 5 सबसे बड़े ज्ञात सामान्यीकृत फ़र्मेट अभाज्यों की सूची है। संपूर्ण शीर्ष-5 की खोज प्राइमग्रिड परियोजना में प्रतिभागियों द्वारा की गई है।

Rank	Prime number	Generalized Fermat notation	Number of digits	Discovery date	ref.
1	19637361048576 + 1	F20(1963736)	6,598,776	Sep 2022
2	19517341048576 + 1	F20(1951734)	6,595,985	Aug 2022
3	10590941048576 + 1	F20(1059094)	6,317,602	Nov 2018
4	9194441048576 + 1	F20(919444)	6,253,210	Sep 2017
5	81 × 220498148 + 1	F2(3 × 25124537)	6,170,560	Jun 2023

प्राइम पेजों पर कोई भी वर्तमान शीर्ष 100 सामान्यीकृत फ़र्मेट प्राइम पा सकता है।

यह भी देखें

• निर्माण योग्य बहुभुज: कौन सा नियमित बहुभुज रचनात्मक है, यह आंशिक रूप से फ़र्मेट अभाज्य पर निर्भर करता है।
• दोहरा घातीय कार्य
• लुकास का प्रमेय
• मेर्सन प्रीमियम
• पियरपोंट प्राइम
• प्राथमिकता परीक्षण
• प्रोथ का प्रमेय
• स्यूडोप्राइम
• सिएरपिंस्की नंबर
• सिल्वेस्टर का क्रम

संदर्भ

• Golomb, S. W. (January 1, 1963), "On the sum of the reciprocals of the Fermat numbers and related irrationalities", Canadian Journal of Mathematics, 15: 475–478, doi:10.4153/CJM-1963-051-0, S2CID 123138118
• Grytczuk, A.; Luca, F. & Wójtowicz, M. (2001), "Another note on the greatest prime factors of Fermat numbers", Southeast Asian Bulletin of Mathematics, 25 (1): 111–115, doi:10.1007/s10012-001-0111-4, S2CID 122332537
• Guy, Richard K. (2004), Unsolved Problems in Number Theory, Problem Books in Mathematics, vol. 1 (3rd ed.), New York: Springer Verlag, pp. A3, A12, B21, ISBN 978-0-387-20860-2
• Křížek, Michal; Luca, Florian & Somer, Lawrence (2001), 17 Lectures on Fermat Numbers: From Number Theory to Geometry, CMS books in mathematics, vol. 10, New York: Springer, ISBN 978-0-387-95332-8 - This book contains an extensive list of references.
• Křížek, Michal; Luca, Florian & Somer, Lawrence (2002), "On the convergence of series of reciprocals of primes related to the Fermat numbers", Journal of Number Theory, 97 (1): 95–112, doi:10.1006/jnth.2002.2782
• Luca, Florian (2000), "The anti-social Fermat number", American Mathematical Monthly, 107 (2): 171–173, doi:10.2307/2589441, JSTOR 2589441
• Ribenboim, Paulo (1996), The New Book of Prime Number Records (3rd ed.), New York: Springer, ISBN 978-0-387-94457-9
• Robinson, Raphael M. (1954), "Mersenne and Fermat Numbers", Proceedings of the American Mathematical Society, 5 (5): 842–846, doi:10.2307/2031878, JSTOR 2031878
• Yabuta, M. (2001), "A simple proof of Carmichael's theorem on primitive divisors" (PDF), Fibonacci Quarterly, 39: 439–443, archived (PDF) from the original on 2022-10-09

बाहरी संबंध

• Chris Caldwell, The Prime Glossary: Fermat number at The Prime Pages.
• Luigi Morelli, History of Fermat Numbers
• John Cosgrave, Unification of Mersenne and Fermat Numbers
• Wilfrid Keller, Prime Factors of Fermat Numbers
• Weisstein, Eric W. "Fermat Number". MathWorld.
• Weisstein, Eric W. "Fermat Prime". MathWorld.
• Weisstein, Eric W. "Generalized Fermat Number". MathWorld.
• Yves Gallot, Generalized Fermat Prime Search
• Mark S. Manasse, Complete factorization of the ninth Fermat number (original announcement)
• Peyton Hayslette, Largest Known Generalized Fermat Prime Announcement