सर्वांगसमताएँ और मॉड्यूलर अंकगणित

मॉड्यूलर अंकगणित एक निश्चित मापांक द्वारा विभाज्यता तक पूर्णांकों का अध्ययन करता है, पूर्णांकों को परिमित वलय Z/nZ में बदल देता है और संख्या सिद्धांत को अपना सबसे लचीला संगणनात्मक उपकरण प्रदान करता है।

Definition

दो पूर्णांक n के मापांक सर्वांगसम होते हैं यदि उनका अंतर n से विभाज्य हो। मॉड्यूलर अंकगणित परिणामी अवशेष वर्गों का अंकगणित है, जो क्रमविनिमेय वलय Z/nZ बनाते हैं।

Scope

यह विषय सर्वांगसमता संबंध और अवशेष वर्गों, Z/nZ में अंकगणित, रैखिक और बहुपद सर्वांगसमताओं, चीनी शेषफल प्रमेय, फर्मेट के छोटे प्रमेय और यूलर के प्रमेय, इकाई समूह की संरचना, आदिम मूलों और तत्वों के क्रम को शामिल करता है। यह वह भाषा है जिसमें अधिकांश प्राथमिक और संगणनात्मक संख्या सिद्धांत व्यक्त किया जाता है।

Core questions

• एक रैखिक सर्वांगसमता ax सर्वांगसम b mod n के हल कब होते हैं, और कितने होते हैं?
• चीनी शेषफल प्रमेय Z/nZ को अभाज्य-घात मापांकों पर एक गुणनफल में कैसे विघटित करता है?
• फर्मेट का छोटा प्रमेय और यूलर का प्रमेय क्यों मान्य हैं, और वे इकाइयों के क्रम के बारे में क्या कहते हैं?
• किन मापांकों के लिए एक आदिम मूल मौजूद होता है, जिससे इकाई समूह चक्रीय बनता है?

Key theories

चीनी शेषफल प्रमेय

यदि मापांक युग्मशः सहअभाज्य हैं, तो एक साथ सर्वांगसमताओं की एक प्रणाली का गुणनफल के मापांक में एक अद्वितीय हल होता है; समतुल्य रूप से Z/nZ अपने अभाज्य-घात कारकों पर Z के गुणनफल के लिए समरूपी है।

फर्मेट का छोटा प्रमेय और यूलर का प्रमेय

n के सहअभाज्य a के लिए, n के टोटिएंट की घात a, n के मापांक एक के सर्वांगसम है; अभाज्य स्थिति (फर्मेट) अभाज्यता परीक्षणों का आधार है और सामान्य स्थिति RSA का आधार है।

आदिम मूल और समूह संरचना

n के मापांक इकाइयों का गुणात्मक समूह ठीक तभी चक्रीय होता है जब n एक, दो, चार, एक विषम अभाज्य घात, या उसका दोगुना हो; एक जनरेटर एक आदिम मूल होता है, जो एक असतत लघुगणक देता है।

Clinical relevance

मॉड्यूलर अंकगणित क्रिप्टोग्राफी (RSA, Diffie-Hellman, दीर्घवृत्तीय-वक्र योजनाएं), चेकसम और त्रुटि पहचान (ISBN, हैश फ़ंक्शन), और छद्म-यादृच्छिक संख्या जनन का संगणनात्मक इंजन है, जो इसे संख्या सिद्धांत का सबसे व्यापक रूप से तैनात हिस्सा बनाता है।

History

यद्यपि विशेष मामले प्राचीन चीनी और भारतीय गणित में दिखाई देते हैं (पूर्व के नाम पर शेषफल समस्या), सर्वांगसमताओं का व्यवस्थित सिद्धांत गॉस द्वारा डिसक्विजिशन अरिथमेटिका (1801) में प्रस्तुत किया गया था, जहाँ उन्होंने संकेतन स्थापित किया और केंद्रीय संरचनात्मक परिणामों को सिद्ध किया।

Key figures

• Carl Friedrich Gauss
• Pierre de Fermat
• Leonhard Euler

Seminal works

• irelandRosen1990

Frequently asked questions

संकेतन a सर्वांगसम b mod n का क्या अर्थ है?

इसका अर्थ है कि n, a माइनस b के अंतर को विभाजित करता है, समतुल्य रूप से a और b को n से विभाजित करने पर समान शेषफल प्राप्त होता है।

RSA यूलर के प्रमेय पर क्यों निर्भर करता है?

RSA एन्क्रिप्शन और डिक्रिप्शन मॉड्यूलर घातांक हैं जिनकी संरचना मूल संदेश को ठीक-ठीक वापस करती है क्योंकि यूलर का प्रमेय गारंटी देता है कि प्रासंगिक घातांक कुंजी के मापांक पहचान के रूप में कार्य करता है।