कम अवशेष प्रणाली

गणित में, पूर्णांकों के एक उपसमुच्चय R को 'कम अवशेष प्रणाली मॉड्यूलो' n कहा जाता है यदि:

1. gcd(r, n) = 1 R में प्रत्येक r के लिए,
2. R में φ(n) तत्व शामिल हैं,
3. R के कोई भी दो अवयव मॉड्यूलर अंकगणित नहीं हैं#Congruence modulo n.

यहाँ φ यूलर के कुल कार्य को दर्शाता है।

एक पूर्ण अवशेष प्रणाली modulo m modulo n से सभी पूर्णांकों को हटाकर एक कम अवशेष प्रणाली modulo n बनाया जा सकता है जो n के लिए अपेक्षाकृत प्रमुख नहीं है। उदाहरण के लिए, एक पूर्ण अवशेष प्रणाली मॉड्यूल 12 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} है। तथाकथित कुल 1, 5, 7 और 11 इस सेट में एकमात्र पूर्णांक हैं जो अपेक्षाकृत 12 के लिए प्रमुख हैं, और इसलिए संबंधित कम अवशेष प्रणाली मॉड्यूलो 12 {1, 5, 7, 11} है। इस सेट की प्रमुखता की गणना टोटिएंट फंक्शन के साथ की जा सकती है: φ(12) = 4. कुछ अन्य कम अवशेष सिस्टम मॉड्यूल 12 हैं:

• {13,17,19,23}
• {−11,−7,−5,−1}
• {−7,−13,13,31}
• {35,43,53,61}

तथ्य

• यदि {आर₁, आर₂, ... , आर_φ(n)} n > 2 के साथ एक कम अवशेष प्रणाली मॉड्यूलो n है, फिर $\sum r_{i}\equiv 0\!\!\!\!\mod n$.
• एक कम अवशेष प्रणाली मॉड्यूलो एन में प्रत्येक संख्या एक चक्रीय समूह # परिभाषा और पूर्णांक मॉड्यूलो एन के योगात्मक समूह (गणित) के लिए संकेतन है।
• यदि {आर₁, आर₂, ... , आर_φ(n)} एक कम अवशेष प्रणाली सापेक्ष n है, और एक पूर्णांक है जैसे कि gcd (a, n) = 1, फिर {ar₁, साथ₂, ... , साथ_φ(n)} भी एक कम अवशेष प्रणाली मॉड्यूलो एन है।

यह भी देखें

• पूरा अवशेष प्रणाली मॉड्यूलो एम
• पूर्णांक मॉड्यूलो n का गुणक समूह
• सर्वांगसमता संबंध
• यूलर का कुल कार्य
• महत्तम सामान्य भाजक
• न्यूनतम अवशेष प्रणाली मॉड्यूलो एम
• मॉड्यूलर अंकगणित
• संख्या सिद्धांत
• अवशेष संख्या प्रणाली

संदर्भ

• Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77171950
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 71081766

बाहरी संबंध

• Residue systems at PlanetMath
• Reduced residue system at MathWorld