फ़र्मेट की छोटी प्रमेय प्राथमिक संख्या सिद्धांत में एक मौलिक प्रमेय है, जो पूर्णांक मोडुलो अभाज्य संख्याओं की गणना शक्तियाँ प्रदान करता है। यह यूलर के प्रमेय का एक विशिष्ट मामला है, और प्राथमिक संख्या सिद्धांत के अनुप्रयोगों में आवश्यक है, जैसे कि प्रारंभिक परीक्षण और सार्वजनिक-कुंजी क्रिप्टोग्राफी। इसे फ़र्मेट का छोटा प्रमेय कहा जाता है।
फ़र्मेट के प्रमेय को फ़र्मेट का छोटा प्रमेय भी कहा जाता है जो परिभाषित करता है कि P अभाज्य है और 'a' एक धनात्मक पूर्णांक है जो P से विभाज्य नहीं है -
a P−1 ≡ 1 मॉड पी
दूसरी शर्त यह कहती है कि यदि P एक अभाज्य है और a एक पूर्णांक है तो a P ≡ 1 मॉड पी.
सबूत - जेड<उप>पी पूर्णांक {0, 1…P-1} का समुच्चय है, जब एक मॉड्यूलो P से गुणा किया जाता है, तो परिणाम में Zp के सभी अवयव शामिल होते हैं। कुछ क्रम में, कुल्हाड़ी 0 0 mod P के अलावा, इस प्रकार, (P-1) संख्याएँ {a mod P, 2a mod P,…((P-1) a mod P)} केवल संख्या हैं {1, 2 ,…(P-1)} किसी क्रम में।
दोनों चरणों में संख्याओं को गुणा करने और परिणाम प्राप्त करने पर mod P देता है
एक एक्स 2ए एक्स …. x ((P-1)a)=[(a mod P) x (2a mod P) x…। x ((P-1) एक मॉड P)] मॉड P
=[1 x 2 x…x (पी-1)] मॉड पी
=(पी -1)! मॉड पी
लेकिन
a x 2a x…x ((P-1)a) =(P-1)!a P−1
(पी-1)! a P−1 (𝑃 - 1)! मॉड पी
a P−1 ≡ 1 मॉड पी
p:{1, 2... p1} से कम धनात्मक पूर्णांकों के समुच्चय पर विचार करें और समुच्चय X ={a mod p, 2a mod p प्राप्त करने के लिए प्रत्येक अवयव को a, modulo p से गुणा करें। . . (पी 1) एक मॉड पी}। X का कोई भी अवयव शून्य के समान नहीं है क्योंकि p, a को विभाजित नहीं करता है।
इसके अलावा X में कोई भी दो पूर्णांक समान नहीं हैं। इसे देखने के लिए, उस (ja p) पर विचार करें जहां 1 p1. क्योंकि p, यह समीकरण के दोनों पक्षों से a को हटा सकता है, जिसके परिणामस्वरूप - j≡ p)।
j और k दोनों ही p से कम धनात्मक पूर्णांक हैं, क्योंकि यह अंतिम समानता अप्राप्य है। इसलिए, यह समझा जाता है कि X के (p1) अवयव सभी धनात्मक पूर्णांक हैं, जिनमें कोई भी दो अवयव समान नहीं हैं।
संख्यात्मक - फ़र्मेट की प्रमेय में कहा गया है कि यदि p अभाज्य है और a एक धनात्मक पूर्णांक है जो P से विभाज्य नहीं है, तो a P−1 ≡ 1(मॉड पी).
इसलिए, 3 10 1 (मोड 11) ।
इसलिए, 3 201 =(3 10 ) 20 x 3 3 (मॉड 11).
Fermats थोड़ा प्रमेय कभी-कभी कुछ घातांक के समाधान को जल्दी से खोजने के लिए फायदेमंद होता है। निम्नलिखित उदाहरण अवधारणा को दर्शाते हैं।
उदाहरण1 − 6 10 . का परिणाम खोजें मॉड 11.
समाधान
यहां, हमारे पास 6 10 . है mod 11 =1. यह Fermat के छोटे प्रमेय का पहला संस्करण है जहाँ p =11.
उदाहरण2 − 3 12 . का परिणाम खोजें मॉड 11.
समाधान
इसलिए घातांक (12) और मापांक (11) बराबर नहीं हैं। प्रतिस्थापन के साथ इसे फ़र्मेट के छोटे प्रमेय का उपयोग करके परिभाषित किया जा सकता है।
3 12 mod11 =(3 11 x3)mod11 =(3 11 mod11)(3 मॉड 11) =(3x3)mod11 =9