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