एक अज्ञात के साथ पहली डिग्री की तुलना का रूप है:

एफ(एक्स) 0 (मोड एम); एफ(एक्स) = ओह + एक. (1)

तुलना हल करेंइसका मतलब है कि x के सभी मानों को खोजना जो इसे संतुष्ट करते हैं। दो तुलनाएँ जो x के समान मानों को संतुष्ट करती हैं, कहलाती हैं बराबर.

अगर तुलना (1) कुछ को संतुष्ट करती है एक्स = एक्स 1, तब (49 के अनुसार) सभी संख्याओं की तुलना एक्स 1, मोडुलो एम: एक्स एक्स 1 (मोड एम) संख्याओं का यह पूरा वर्ग इस प्रकार गिना जाता है एक हल. इस समझौते के साथ, निम्नलिखित निष्कर्ष निकाला जा सकता है।

66.एस संरेखण (1) के पास उतने ही समाधान होंगे जितने पूरे सिस्टम के अवशेष हैं जो इसे संतुष्ट करते हैं.

उदाहरण। तुलना

6एक्स- 4 0 (मॉड 8)

अवशेषों की पूरी प्रणाली के 0, 1,2, 3, 4, 5, 6, 7 की संख्या के बीच मॉड्यूलो 8, दो संख्याएँ संतुष्ट करती हैं: एक्स= 2 और एक्स= 6. इसलिए, इस तुलना के दो हल हैं:

एक्स 2 (मॉड 8), एक्स 6 (मॉड 8)।

फ्री टर्म (विपरीत चिह्न के साथ) को दाईं ओर स्थानांतरित करके पहली डिग्री की तुलना को फॉर्म में घटाया जा सकता है

कुल्हाड़ी बी(मोड एम). (2)

एक तुलना पर विचार करें जो शर्त को पूरा करती है ( एक, एम) = 1.

66 के अनुसार हमारी तुलना में उतने ही समाधान हैं जितने पूरे सिस्टम के अवशेष हैं जो इसे संतुष्ट करते हैं। लेकिन जब एक्सअवशेष मॉड्यूलो की पूरी प्रणाली के माध्यम से चलता है टी,फिर ओहकटौती की पूरी प्रणाली (60 में से) के माध्यम से चलता है। इसलिए, एक और केवल एक मान के लिए एक्स,पूरी प्रणाली से लिया गया, ओहके साथ तुलनीय होगा बी।इसलिए,

67. (ए, एम) = 1 तुलना कुल्हाड़ी के लिए बी(मोड एम)एक समाधान है।

चलो अब ( एक, एम) = डी> 1. फिर, तुलना के लिए (2) समाधान होने के लिए, यह आवश्यक है (55 में से) कि बीमें बांटें डी,अन्यथा तुलना (2) किसी भी पूर्णांक x . के लिए असंभव है . इसलिए मान लेना बीविभिन्न डी,चलो रखो एक = एक 1 डी, बी = बी 1 डी, एम = एम 1 डी।तब तुलना (2) इसके बराबर होगी (इससे घटाई गई डी): एक 1 एक्स बी 1 (मोड एम), जिसमें पहले से ही ( एक 1 , एम 1) = 1, और इसलिए इसका एक समाधान मॉड्यूल होगा एमएक । होने देना एक्स 1 इस समाधान का सबसे छोटा गैर-ऋणात्मक अवशेष है मॉड्यूल एम 1 , फिर सभी नंबर x , इस समाधान को बनाने के रूप में पाया जा सकता है

एक्स एक्स 1 (मोड एम 1). (3)

मोडुलो, संख्याएँ (3) एक समाधान नहीं बनाती हैं, लेकिन अधिक, ठीक उतने ही समाधान हैं जितने संख्याएँ हैं (3) श्रृंखला में 0, 1, 2, ..., एम 1 कम से कम गैर-नकारात्मक अवशेष मोडुलो एम।लेकिन निम्नलिखित संख्याएँ यहाँ गिरेंगी (3):

एक्स 1 , एक्स 1 + एम 1 , एक्स 1 + 2एम 1 , ..., एक्स 1 + (डी – 1) एम 1 ,

वे। कुल डीसंख्या (3); इसलिए तुलना (2) है डीसमाधान।

हमें प्रमेय मिलता है:

68. माना (ए, एम) = डी। तुलना कुल्हाड़ी बी (आधुनिक m) असंभव है यदि b, d से विभाज्य नहीं है। जब b, d का गुणज हो, तो तुलना में d समाधान होते हैं।

69. निरंतर भिन्नों के सिद्धांत के आधार पर पहली डिग्री की तुलना को हल करने की विधि:

एक निरंतर अंश में विस्तार अनुपात एम:ए,

और पिछले दो अभिसरणों पर विचार करते हुए:

निरंतर भिन्नों के गुणों के अनुसार (के अनुसार 30 ) अपने पास

तो तुलना का एक समाधान है

खोज के लिए, जो गणना करने के लिए पर्याप्त है पी न- 1 30 में निर्दिष्ट विधि के अनुसार।

उदाहरण। आइए तुलना को हल करें

111एक्स= 75 (मॉड 321)। (चार)

यहाँ (111, 321) = 3, और 75, 3 का गुणज है। इसलिए, तुलना के तीन हल हैं।

तुलना के दोनों भागों और मापांक को 3 से विभाजित करने पर, हमें तुलना प्राप्त होती है

37एक्स= 25 (मॉड 107), (5)

जो हमें पहले तय करने की जरूरत है। हमारे पास है

क्यू
पी 3

तो, इस मामले में एन = 4, पी एन - 1 = 26, बी= 25, और हमारे पास तुलना (5) के रूप में हल है

एक्स-26 25 99 (मॉड 107)।

इसलिए, तुलना (4) के समाधान निम्नानुसार प्रस्तुत किए गए हैं:

एक्स 99; 99 + 107; 99 + 2 107 (मॉड 321),

एक्स 99; 206; 313 (मॉड 321)।

व्युत्क्रम तत्व की गणना एक दिए गए मॉड्यूलो

70.यदि पूर्णांक एकतथा एन coprime, तो एक संख्या है एक', तुलना को संतुष्ट करना एक एक 1(मोड एन) संख्या एक'बुलाया एक मॉड्यूलो n . का गुणन प्रतिलोमऔर इसके लिए संकेतन का उपयोग किया जाता है एक- 1 (मोड एन).

पारस्परिक मोडुलो की गणना कुछ अज्ञात के साथ प्रथम-डिग्री तुलना समाधान द्वारा की जा सकती है, जिसमें एक्सस्वीकृत संख्या एक'.

तुलना समाधान खोजने के लिए

एक एक्स≡ 1 (मोड एम),

कहाँ पे ( पूर्वाह्न)= 1,

कोई यूक्लिड एल्गोरिथम (69) या फ़र्मेट-यूलर प्रमेय का उपयोग कर सकता है, जिसमें कहा गया है कि यदि ( पूर्वाह्न) = 1, तो

एक φ( एम) 1 (मोड एम).

एक्स ≡ एक φ( एम)-1 (मोड एम).

समूह और उनके गुण

समूह सामान्य विशेषताओं वाले गणितीय संरचनाओं के वर्गीकरण में उपयोग किए जाने वाले वर्गीकरण वर्गों में से एक हैं। समूहों में दो घटक होते हैं: बहुत सारे (जी) तथा संचालन() इस सेट पर परिभाषित।

समुच्चय, तत्व और सदस्यता की अवधारणाएँ आधुनिक गणित की मूल अपरिभाषित अवधारणाएँ हैं। किसी भी समुच्चय को उसमें शामिल तत्वों द्वारा परिभाषित किया जाता है (जो बदले में समुच्चय भी हो सकते हैं)। इस प्रकार, हम कहते हैं कि एक सेट परिभाषित या दिया गया है यदि किसी तत्व के लिए हम कह सकते हैं कि यह इस सेट से संबंधित है या नहीं।

दो सेट के लिए ए, बीअभिलेख बी ए, बी ए, बी∩ ए, बी ए, बी \ ए, ए × बीमतलब, क्रमशः, कि बीसेट का एक सबसेट है ए(अर्थात से कोई तत्व बीमें भी निहित है ए, उदाहरण के लिए, प्राकृत संख्याओं का समुच्चय वास्तविक संख्याओं के समुच्चय में समाहित है; इसके अलावा, हमेशा ए ए), बीसमुच्चय का उचित उपसमुच्चय है ए(वे। बी एतथा बी ≠ ए), कई . का चौराहा बीतथा ए(अर्थात् ऐसे सभी तत्व जो एक साथ और में स्थित हों) ए, और में बी, उदाहरण के लिए, पूर्णांकों और धनात्मक वास्तविक संख्याओं का प्रतिच्छेदन प्राकृत संख्याओं का समुच्चय है), समुच्चयों का संघ बीतथा ए(अर्थात तत्वों से मिलकर बना एक समुच्चय जो या तो में स्थित है) ए, में या तो बी), अंतर सेट करें बीतथा ए(अर्थात तत्वों का समुच्चय जो में स्थित है) बी, लेकिन झूठ मत बोलो ए), सेट का कार्टेशियन उत्पाद एतथा बी(यानी, फॉर्म के जोड़े का एक सेट ( एक, बी), कहाँ पे एक ए, बी बी) के माध्यम से | ए| सेट की कार्डिनैलिटी हमेशा निरूपित की जाती है ए, अर्थात। सेट में तत्वों की संख्या ए.

संक्रिया वह नियम है जिसके अनुसार समुच्चय के किन्हीं दो अवयव जी(एकतथा बी) G से तीसरे तत्व से जुड़ा है: एक ख.

बहुत सारे तत्व जीनामक एक ऑपरेशन के साथ समूहयदि निम्नलिखित शर्तें पूरी होती हैं।

n पर वे वही शेषफल देते हैं।

समतुल्य सूत्र: ए और बी तुलनीय मोडुलो n यदि उनका अंतर एक - बी n से विभाज्य है, या यदि a को के रूप में दर्शाया जा सकता है एक = बी + कएन , कहाँ पे ककुछ पूर्णांक है। उदाहरण के लिए: 32 और -10 सर्वांगसम मॉड्यूल 7 हैं क्योंकि

कथन "ए और बी सर्वांगसम मोडुलो एन हैं" इस प्रकार लिखा गया है:

मोडुलो समानता गुण

मॉड्यूलो तुलना संबंध में गुण होते हैं

कोई दो पूर्णांक एकतथा बीतुलनीय मोडुलो 1 हैं।

संख्याओं के क्रम में एकतथा बीतुलनीय मोडुलो . थे एन, यह आवश्यक और पर्याप्त है कि उनका अंतर विभाज्य है एन.

यदि संख्याएं और जोड़ीवार तुलनीय मॉड्यूल हैं एन, फिर उनकी रकम और , साथ ही साथ उत्पाद और तुलनीय मॉड्यूल भी हैं एन.

अगर संख्या एकतथा बीतुलनीय मोडुलो एन, फिर उनकी डिग्री एक कतथा बी कतुलनीय मोडुलो . भी हैं एनकिसी भी प्राकृतिक के लिए क.

अगर संख्या एकतथा बीतुलनीय मोडुलो एन, तथा एनद्वारा विभाजित एम, फिर एकतथा बीतुलनीय मोडुलो एम.

संख्याओं के क्रम में एकतथा बीतुलनीय मोडुलो . थे एन, प्रमुख कारकों में इसके विहित अपघटन के रूप में दर्शाया गया है पी मैं

के लिए आवश्यक और पर्याप्त

तुलना संबंध एक तुल्यता संबंध है और इसमें सामान्य समानता के कई गुण हैं। उदाहरण के लिए, उन्हें जोड़ा और गुणा किया जा सकता है: if

हालाँकि, आम तौर पर तुलना को एक दूसरे या अन्य संख्याओं से विभाजित नहीं किया जा सकता है। उदाहरण: हालांकि, 2 से कम करने पर, हमें एक गलत तुलना मिलती है: . तुलना के लिए कमी नियम इस प्रकार हैं।

यदि उनके मॉड्यूल मेल नहीं खाते हैं तो आप तुलनाओं पर भी संचालन नहीं कर सकते हैं।

अन्य गुण:

संबंधित परिभाषाएं

कटौती वर्ग

तुलनीय सभी संख्याओं का समुच्चय एकसापेक्ष एनबुलाया कटौती वर्ग एकसापेक्ष एन , और आमतौर पर [द्वारा निरूपित किया जाता है] एक] एनया । इस प्रकार, तुलना अवशेष वर्गों की समानता के बराबर है [एक] एन = [बी] एन .

क्योंकि मोडुलो तुलना एनपूर्णांकों के समुच्चय पर एक तुल्यता संबंध है, तो अवशेष वर्ग modulo एनतुल्यता वर्ग हैं; उनकी संख्या है एन. सभी अवशेष वर्गों का सेट modulo एनया द्वारा निरूपित।

जोड़ और गुणा के संचालन सेट पर संबंधित संचालन को प्रेरित करते हैं:

[एक] एन + [बी] एन = [एक + बी] एन

इन संक्रियाओं के संबंध में, समुच्चय एक परिमित वलय है, और यदि एनसरल - अंतिम क्षेत्र।

कटौती प्रणाली

अवशेष प्रणाली आपको संख्याओं के एक सीमित सेट पर बिना इससे आगे बढ़े अंकगणितीय संचालन करने की अनुमति देती है। कटौती की पूरी प्रणाली modulo n n पूर्णांकों का कोई भी सेट है जो अतुलनीय modulo n है। आमतौर पर, अवशेष मॉड्यूल n की एक पूरी प्रणाली के रूप में, कोई सबसे छोटा गैर-नकारात्मक अवशेष लेता है

0,1,...,एन − 1

या संख्याओं से युक्त बिल्कुल छोटे अवशेष

,

विषम के मामले में एनऔर संख्या

सम के मामले में एन .

तुलना निर्णय

पहली डिग्री की तुलना

संख्या सिद्धांत, क्रिप्टोग्राफी और विज्ञान के अन्य क्षेत्रों में, समस्या अक्सर फॉर्म की पहली डिग्री की तुलना के लिए समाधान खोजने की होती है:

ऐसी तुलना का समाधान gcd . की गणना से शुरू होता है (ए, एम) = डी. इस मामले में, 2 मामले संभव हैं:

• यदि एक बीएक बहु नहीं डी, तो तुलना का कोई समाधान नहीं है।
• यदि एक बीविभिन्न डी, तो तुलना का एक अनूठा समाधान मॉड्यूल है एम / डी, या, जो एक ही है, डीमॉड्यूलो समाधान एम. इस मामले में, मूल तुलना को कम करने के परिणामस्वरूप डीतुलना परिणाम:

कहाँ पे एक 1 = एक / डी , बी 1 = बी / डी तथा एम 1 = एम / डी पूर्णांक हैं, और एक 1 और एम 1 कोप्राइम हैं। इसलिए संख्या एक 1 उलटा मोडुलो हो सकता है एम 1 , यानी ऐसी कोई संख्या ज्ञात करें सीवह (दूसरे शब्दों में,)। अब परिणामी तुलना को से गुणा करके हल निकाला जाता है सी:

व्यावहारिक मूल्य गणना सीविभिन्न तरीकों से किया जा सकता है: यूलर के प्रमेय, यूक्लिड के एल्गोरिदम, निरंतर अंशों का सिद्धांत (एल्गोरिदम देखें), आदि का उपयोग करना। विशेष रूप से, यूलर का प्रमेय आपको मूल्य लिखने की अनुमति देता है सीजैसा:

उदाहरण

तुलना के लिए, हमारे पास है डी= 2, इसलिए मॉड्यूल 22 तुलना के दो समाधान हैं। आइए 26 को 4 से बदलें, जो तुलनीय मॉड्यूल 22 है, और फिर सभी 3 नंबरों को 2 से रद्द करें:

चूँकि 2 मॉड्यूलो 11 का सहअभाज्य है, हम बाएँ और दाएँ पक्षों को 2 से कम कर सकते हैं। परिणामस्वरूप, हमें एक समाधान मॉड्यूल 11: मिलता है, जो दो समाधान मॉड्यूलो 22: के बराबर है।

दूसरी डिग्री की तुलना

दूसरी डिग्री की तुलना को हल करना यह पता लगाने के लिए कम हो जाता है कि क्या दी गई संख्या एक द्विघात अवशेष है (पारस्परिकता के द्विघात नियम का उपयोग करके) और फिर वर्गमूल मॉड्यूलो की गणना करना।

कहानी

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

विषय।

परिचय

§एक। मोडुलो तुलना

2. तुलना गुण

1. मॉड्यूल-स्वतंत्र तुलना गुण
2. मॉड्यूल-विशिष्ट तुलना गुण

3. कटौती प्रणाली

1. कटौती की पूरी प्रणाली
2. कटौती की कम प्रणाली

§चार। यूलर का प्रमेय और फ़र्माटा

1. यूलर फंक्शन
2. यूलर की प्रमेय और फ़र्माटा

अध्याय 2। एक चर के साथ तुलना का सिद्धांत

§एक। तुलना के निर्णय से संबंधित बुनियादी अवधारणाएं

1. तुलना की जड़ें
2. तुलना की समानता
3. विल्सन का प्रमेय

2. पहली डिग्री और उनके समाधान की तुलना

1. चयन विधि
2. यूलर तरीके
3. यूक्लिड की एल्गोरिथम विधि
4. निरंतर भिन्न विधि

3. एक अज्ञात के साथ पहली डिग्री की तुलना की प्रणाली

§चार। उच्च शक्तियों की तुलना का विभाजन

5. आदिम मूल और सूचकांक

1. कटौती वर्ग आदेश
2. आदिम जड़ें मोडुलो प्राइम
3. इंडेक्स मोडुलो प्राइम

अध्याय 3 तुलना के सिद्धांत का अनुप्रयोग

§एक। विभाज्यता के लक्षण

2. अंकगणितीय संक्रियाओं के परिणामों की जाँच करना

3. साधारण भिन्न को परिमित में बदलना

दशमलव अंश

निष्कर्ष

साहित्य

परिचय

अपने जीवन में हमें अक्सर पूर्णांकों और उनसे जुड़े कार्यों से निपटना पड़ता है। इस थीसिस में, मैं पूर्णांकों की तुलना के सिद्धांत पर विचार करता हूं।

दो पूर्णांक जिनका अंतर किसी दी गई प्राकृतिक संख्या का गुणज हैएम तुलनीय मोडुलो . कहा जाता हैएम।

शब्द "मॉड्यूल" लैटिन मॉड्यूलस से आया है, जिसका रूसी में अर्थ है "माप", "मूल्य"।

कथन "a, b modulo m के सर्वांगसम है" को आमतौर पर a . के रूप में लिखा जाता हैबी (मॉड एम) और इसे तुलना कहा जाता है।

तुलना की परिभाषा के। गॉस "अरिथमेटिक रिसर्च" द्वारा पुस्तक में तैयार की गई थी। लैटिन में लिखा गया यह काम 1797 में छपना शुरू हुआ, लेकिन यह किताब 1801 में ही प्रकाशित हुई थी क्योंकि उस समय छपाई की प्रक्रिया बेहद श्रमसाध्य और लंबी थी। गॉस की पुस्तक के पहले खंड को "ऑन द कम्पेरिजन ऑफ नंबर्स इन जनरल" कहा जाता है।

तुलना उन मामलों में उपयोग करने के लिए बहुत सुविधाजनक है जब किसी भी शोध में एक निश्चित संख्या के गुणकों तक संख्याओं को जानना पर्याप्त होता है।

उदाहरण के लिए, यदि हम इस बात में रुचि रखते हैं कि किसी पूर्णांक का घन किस अंक पर समाप्त होता है, तो हमारे लिए केवल 10 के गुणकों तक ही जानना पर्याप्त है और हम तुलना मॉड्यूलो 10 का उपयोग कर सकते हैं।

इस काम का उद्देश्य तुलना के सिद्धांत पर विचार करना और अज्ञात के साथ तुलना को हल करने के मुख्य तरीकों का अध्ययन करना है, साथ ही स्कूली गणित की तुलना के सिद्धांत के आवेदन का अध्ययन करना है।

थीसिस में तीन अध्याय होते हैं, प्रत्येक अध्याय पैराग्राफ में विभाजित होता है, और पैराग्राफ पैराग्राफ में।

पहला अध्याय तुलना के सिद्धांत के सामान्य प्रश्नों से संबंधित है। यहां हम मॉड्यूलो तुलना की अवधारणा, तुलना के गुण, अवशेषों की पूर्ण और कम प्रणाली, यूलर फ़ंक्शन, यूलर और फ़र्मेट प्रमेय पर विचार करते हैं।

दूसरा अध्याय अज्ञात के साथ तुलना के सिद्धांत को समर्पित है। यह तुलना के समाधान से संबंधित बुनियादी अवधारणाओं को रेखांकित करता है, पहली डिग्री की तुलना को हल करने के तरीकों पर विचार करता है (चयन विधि, यूलर की विधि, यूक्लिड की एल्गोरिथम विधि, निरंतर अंशों की विधि, सूचकांकों का उपयोग करके), पहली डिग्री की तुलना की प्रणाली के साथ एक अज्ञात, उच्च डिग्री की तुलना, आदि।

तीसरे अध्याय में स्कूली गणित के लिए संख्या सिद्धांत के कुछ अनुप्रयोग शामिल हैं। विभाज्यता के संकेत, क्रियाओं के परिणामों का सत्यापन, साधारण अंशों का व्यवस्थित दशमलव अंशों में परिवर्तन पर विचार किया जाता है।

सैद्धांतिक सामग्री की प्रस्तुति बड़ी संख्या में उदाहरणों के साथ होती है जो प्रस्तुत अवधारणाओं और परिभाषाओं के सार को प्रकट करते हैं।

अध्याय 1। तुलना के सिद्धांत के सामान्य प्रश्न

§एक। मोडुलो तुलना

मान लें कि पूर्णांकों का z-रिंग, m-निश्चित पूर्णांक और m से विभाज्य सभी पूर्णांकों का m z-सेट।

परिभाषा 1. दो पूर्णांक a और b को सर्वांगसम मॉड्यूल m कहा जाता है यदि m, a-b को विभाजित करता है।

यदि संख्याएँ a और b तुलनीय मोडुलो m हैं, तो a लिखिएबी (मॉड एम)।

शर्त ए b (mod m) का अर्थ है कि a-b, m से विभाज्य है।

ए बी (मॉड एम)↔(ए-बी) एम

हम परिभाषित करते हैं कि तुलनीयता मोडुलो एम का संबंध तुलनीयता मोडुलो (-एम) के संबंध के साथ मेल खाता है (एम द्वारा विभाज्यता -एम द्वारा विभाज्यता के बराबर है)। इसलिए, व्यापकता के नुकसान के बिना, हम मान सकते हैं कि m>0।

उदाहरण।

प्रमेय। (स्पिरिट नंबर मोडुलो एम की तुलनीयता का संकेत): दो पूर्णांक ए और बी तुलनीय मॉड्यूल एम हैं यदि और केवल तभी जब ए और बी में एम द्वारा विभाजित होने पर समान शेष हो।

सबूत।

मान लीजिए कि a और b को m से भाग देने पर शेषफल बराबर है, अर्थात् a=mq₁+r,(1)

बी=एमक्यू₂+आर, (2)

जहां 0≤r≥m.

(2) घटाना (1) से, हमें a-b= m(q₁- q₂), अर्थात् a-b प्राप्त होता है।एम या ए बी (मॉड एम)।

इसके विपरीत, चलो a बी (मॉड एम)। इसका मतलब है a-bएम या ए-बी = एमटी, टी जेड (3)

बी को एम से विभाजित करें; हमें b=mq+r इन (3) प्राप्त होता है, हमारे पास a=m(q+t)+r होगा, अर्थात a को m से भाग देने पर b को m से भाग देने पर वही शेषफल प्राप्त होता है।

उदाहरण।

5=4 (-2)+3

23=4 5+3

24=3 8+0

10=3 3+1

परिभाषा 2. दो या दो से अधिक संख्याएँ जो m से विभाजित करने पर समान शेषफल देती हैं, समदूरस्थ या तुलनीय मॉड्यूल m कहलाती हैं।

उदाहरण।

हमारे पास है: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m², और (- m²) m => से विभाज्य है => हमारी तुलना सही है।

1. सिद्ध कीजिए कि निम्नलिखित तुलनाएँ असत्य हैं:

यदि संख्याएँ तुलनीय modulo m हैं, तो उनके पास इसके साथ समान gcd है।

हमारे पास है: 4=2 2, 10=2 5, 25=5 5

gcd(4,10) = 2, gcd(25,10) = 5, इसलिए हमारी तुलना गलत है।

2. तुलना गुण

1. मॉड्यूल-स्वतंत्र तुलना गुण।

तुलना के कई गुण समानता के समान हैं।

ए) रिफ्लेक्सिविटी: एए (मॉड एम) (कोई भी पूर्णांकएक मॉड्यूलो एम के लिए तुलनीय है);

सी) समरूपता: यदि एबी (मॉड एम), फिर बी ए (मॉड एम);

सी) ट्रांजिटिविटी: यदि एबी (मॉड एम), और बी (मॉड एम), फिर ए (मॉड एम) के साथ।

सबूत।

शर्त के अनुसार एम/(ए-बी) और एम/ (सी-डी)। इसलिए, m/(a-b)+(c-d), m/(a+c)-(b+d) => a+cबी + डी (मॉड एम)।

उदाहरण।

विभाजित करते समय शेषफल ज्ञात करें 13 बजे

समाधान: -1 (मॉड 13) और 1 (मॉड 13), फिर (-1) +1 0 (मॉड 13), यानी शेष भाग 13 से 0 है।

एसी बी-डी (मॉड एम)।

सबूत।

शर्त के अनुसार एम/(ए-बी) और एम/(सी-डी)। इसलिए, एम/(ए-बी)-(सी-डी), एम/(ए-सी)-(बी-डी) => (ए-सी)बी-डी (मॉड एम)।

1. (गुण 1, 2, 3 का परिणाम)। आप तुलना के दोनों भागों में एक ही पूर्णांक जोड़ सकते हैं।

सबूत।

चलो एक b (mod m) और k कोई पूर्णांक है। रिफ्लेक्सिविटी के गुण से

k=k (mod m), और गुण 2 और 3 के अनुसार हमारे पास a+k . हैबी + के (मॉड एम)।

एसी डी (मॉड एम)।

सबूत।

शर्त के अनुसार, a-b mz, c-d є mz. इसलिए a c-b d = (a c - b c)+(b c- b d)=(a-b) c+b (c-d) mz, यानी a cडी (मॉड एम)।

परिणाम। तुलना के दोनों हिस्सों को एक ही पूर्णांक गैर-ऋणात्मक शक्ति तक बढ़ाया जा सकता है: यदि ab (mod m) और s एक गैर-ऋणात्मक पूर्णांक है, तो aएस बी एस (मॉड एम)।

उदाहरण।

समाधान: स्पष्ट रूप से 13 1 (मॉड 3)

2-1 (मॉड 3)

5 -1 (मॉड 3), फिर

- 1-1 0 (मॉड 13)

उत्तर: वांछित शेषफल शून्य है, और A, 3 से विभाज्य है।

समाधान:

आइए हम सिद्ध करें कि 1+ 0(mod13) या 1+ 0(mod 13)

1+ =1+ 1+ =

चूंकि 27 1 (मॉड 13) है, यह इस प्रकार है कि 1+ 1+1 3+1 9 (मॉड 13)।

एच.टी.डी.

3. किसी संख्या के शेष से भाग देने पर शेषफल ज्ञात कीजिए 24 बजे।

हमारे पास है: 1 (मॉड 24), इसलिए

1 (मॉड 24)

तुलना के दोनों भागों में 55 जोड़ने पर, हम प्राप्त करते हैं:

(मोड 24)।

हमारे पास है: (मॉड 24), तो

(मॉड 24) किसी भी k N के लिए।

फलस्वरूप (मोड 24)। चूंकि (-8)16 (मॉड 24), वांछित शेष 16 है।

1. तुलना के दोनों भागों को एक ही पूर्णांक से गुणा किया जा सकता है।

2. मॉड्यूल के आधार पर तुलना के गुण।

सबूत।

चूँकि a b (mod t), तब (a - b) t. और चूँकि t n , तो विभाज्यता संबंध की ट्रांजिटिविटी के कारण(ए - बी एन), यानी, ए बी (मॉड एन)।

उदाहरण।

196 को 7 से भाग देने पर शेषफल ज्ञात कीजिए।

समाधान:

यह जानते हुए कि 196= , हम लिख सकते हैं 196(मोड 14)। आइए पिछली संपत्ति का उपयोग करें, 14 7, हमें 196 (मॉड 7) मिलता है, यानी 196 7.

1. तुलना और मापांक के दोनों भागों को एक ही धनात्मक पूर्णांक से गुणा किया जा सकता है।

सबूत।

चलो ए बी (मॉड एम ) और c एक धनात्मक पूर्णांक है। तब a-b = mt और ac-bc=mtc, या acबीसी (मॉड एमसी)।

उदाहरण।

जाँच करें कि क्या व्यंजक का मान हैपूरा नंबर।

समाधान:

आइए तुलना के रूप में भिन्नों का प्रतिनिधित्व करते हैं: 4(मॉड 3)

1 (मॉड 9)

31 (मॉड 27)

हम इन तुलनाओं को पद (संपत्ति 2) से जोड़ते हैं, हमें 124 . मिलता है(mod 27) हम देखते हैं कि 124 एक पूर्णांक 27 से विभाज्य नहीं है, इसलिए व्यंजक का मानपूर्णांक भी नहीं है।

1. तुलना के दोनों भागों को उनके सामान्य कारक द्वारा विभाजित किया जा सकता है यदि यह मापांक के लिए अपेक्षाकृत प्रमुख है।

सबूत।

अगर ca सीबी (मॉड एम), यानी एम / सी (ए-बी) और संख्यासाथ सहअभाज्य से m, (c,m)=1, फिर m, a-b को विभाजित करता है। फलस्वरूप,ए बी (मॉड टी)।

उदाहरण।

60 9 (मॉड 17), तुलना के दोनों हिस्सों को 3 से विभाजित करने के बाद हम प्राप्त करते हैं:

20 (मॉड 17)।

सामान्यतया, तुलना के दोनों भागों को उस संख्या से विभाजित करना असंभव है जो मापांक के साथ सहअभाज्य नहीं है, क्योंकि विभाजन के बाद, ऐसी संख्याएँ प्राप्त की जा सकती हैं जो इस मापांक में अतुलनीय हैं।

उदाहरण।

8 (मॉड 4) लेकिन 2 (मॉड 4)।

1. तुलना और मापांक के दोनों हिस्सों को उनके सामान्य भाजक द्वारा विभाजित किया जा सकता है।

सबूत।

अगर ka kb (mod km), फिर k (a-b) km से विभाज्य है। अत: a-b, m से विभाज्य है, अर्थात्ए बी (मॉड टी)।

सबूत।

मान लीजिए P (x) = c 0 x n + c 1 x n-1 + ... + c n-1 x+ c n । शर्त के अनुसार a b (mod t), तब

एक के बी के (मॉड एम) के = 0, 1, 2, …, एन के लिए। परिणामी n + 1 तुलनाओं में से प्रत्येक के दोनों भागों को c . से गुणा करनाएन-के, हमें मिलता है:

सी एन-के एक के सी एन-के बी के (मॉड एम), जहां के = 0, 1, 2, …, एन।

पिछली तुलनाओं को जोड़ने पर, हम प्राप्त करते हैं: P (a)पी (बी) (मॉड एम)। यदि a (mod m) और c i d i (mod m), 0 i ≤ n, तो

(मॉड एम)। इस प्रकार, सर्वांगसमता मोडुलो एम में, अलग-अलग पदों और कारकों को संख्या सर्वांगसम मोडुलो एम द्वारा प्रतिस्थापित किया जा सकता है।

उसी समय, इस तथ्य पर ध्यान दिया जाना चाहिए कि तुलना में सामने आने वाले घातांक को इस तरह से बदला नहीं जा सकता है: से

ए एन सी (मॉड एम) और एन k(mod m) का अर्थ यह नहीं है कि aके साथ (मॉड एम)।

संपत्ति 11 में कई महत्वपूर्ण अनुप्रयोग हैं। विशेष रूप से, इसका उपयोग विभाज्यता के संकेतों की सैद्धांतिक पुष्टि देने के लिए किया जा सकता है। उदाहरण के लिए, उदाहरण के तौर पर, हम 3 से विभाज्यता के परीक्षण की व्युत्पत्ति देंगे।

उदाहरण।

किसी भी प्राकृतिक संख्या N को एक व्यवस्थित संख्या के रूप में दर्शाया जा सकता है: N = a 0 10 एन + ए 1 10 एन -1 + ... + ए एन -1 10 + ए एन।

बहुपद f (x) = a . पर विचार करें 0 x n + a 1 x n-1 + ... + a n-1 x+a n । इसलिये

10 1 (मॉड 3), फिर संपत्ति से 10 एफ (10)च(1) (मॉड 3) या

एन = ए 0 10 एन + ए 1 10 एन -1 + ... + ए एन -1 10 + ए एन ए 1 + ए 2 +… + ए एन -1 + ए एन (मोड 3) अर्थात N के 3 से विभाज्य होने के लिए, यह आवश्यक और पर्याप्त है कि इस संख्या के अंकों का योग 3 से विभाज्य हो।

3. कटौती प्रणाली

1. पूर्ण बिलिंग प्रणाली।

समतुल्य संख्याएँ, या, जो समान है, तुलनीय मोडुलो m, संख्याओं का एक वर्ग बनाती है modulo m।

इस परिभाषा से यह निष्कर्ष निकलता है कि वही शेष r वर्ग की सभी संख्याओं से मेल खाता है, और यदि हम q को सभी पूर्णांकों के माध्यम से mq + r के रूप में चलाने के लिए बाध्य करते हैं, तो हमें वर्ग की सभी संख्याएँ प्राप्त होती हैं।

तदनुसार, r के विभिन्न मानों के साथ, हमारे पास संख्याओं के m वर्ग हैं जो modulo m हैं।

किसी वर्ग की किसी भी संख्या को एक ही वर्ग की सभी संख्याओं के संबंध में अवशेष मापांक कहा जाता है। q=0 पर प्राप्त अवशेष, शेष r के बराबर, सबसे छोटा गैर-ऋणात्मक अवशेष कहलाता है।

अवशेष ρ, निरपेक्ष मान में सबसे छोटा, सबसे छोटा अवशेष कहलाता है।

जाहिर है, r के लिए हमारे पास ρ=r है; जब आर> हमारे पास ρ=r-m है; अंत में, यदि m सम है और r=, तो के लिए कोई भी दो संख्याओं में से कोई भी ले सकता हैऔर -एम = -।

हम अवशेषों के प्रत्येक वर्ग से चुनते हैं moduloटी एक नंबर से। प्राप्तमी पूर्णांक: x 1 ,…, x m । सेट (x 1, ..., x t) को कहा जाता है अवशेषों की पूरी प्रणाली मोडुलो एम.

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

उदाहरण।

अवशेष मॉड्यूलो की कई पूर्ण प्रणालियों की रचना करेंटी = 5. हमारे पास वर्ग हैं: 0, 1, 2, 3, 4।

0 = {... -10, -5,0, 5, 10,…}

1= {... -9, -4, 1, 6, 11,…}

आइए प्रत्येक वर्ग से एक कटौती लेते हुए, कटौतियों की कई संपूर्ण प्रणालियाँ बनाएँ:

0, 1, 2, 3, 4

5, 6, 2, 8, 9

10, -9, -8, -7, -6

5, -4, -3, -2, -1

आदि।

सबसे अधिक इस्तेमाल किया गता:

1. कम से कम गैर-नकारात्मक अवशेषों की पूरी प्रणाली: 0, 1, टी -1 ऊपर के उदाहरण में: 0, 1, 2, 3, 4। अवशेषों की ऐसी प्रणाली सरल है: आपको m से विभाजन के परिणामस्वरूप सभी गैर-ऋणात्मक शेषफलों को लिखना होगा।
2. कम से कम सकारात्मक अवशेषों की पूरी प्रणाली(प्रत्येक वर्ग से सबसे छोटी सकारात्मक कटौती ली जाती है):

1, 2, ..., एम। हमारे उदाहरण में: 1, 2, 3, 4, 5।

1. बिल्कुल कम से कम अवशेषों की एक पूरी प्रणाली।विषम m के मामले में, सबसे छोटे अवशेष साथ-साथ दिखाई देते हैं।

- ,…, -1, 0, 1,…, ,

और सम मी के मामले में, दो पंक्तियों में से एक

1, …, -1, 0, 1,…, ,

, …, -1, 0, 1, …, .

दिए गए उदाहरण में: -2, -1, 0, 1, 2।

आइए अब हम अवशेषों की पूरी प्रणाली के मुख्य गुणों पर विचार करें।

प्रमेय 1 . एम पूर्णांकों का कोई भी सेट:

एक्स एल, एक्स 2,…,х एम (1)

जोड़ीदार अतुलनीय मोडुलो एम, अवशेष मोडुलो एम की एक पूरी प्रणाली बनाता है।

सबूत।

1. समुच्चय (1) की प्रत्येक संख्या किसी न किसी वर्ग की है।
2. कोई भी दो संख्याएँ x i और x j से (1) एक दूसरे के साथ अतुलनीय हैं, अर्थात, वे विभिन्न वर्गों से संबंधित हैं।
3. कुल मिलाकर, (1) में m संख्याएँ हैं, यानी, जितने वर्ग modulo हैंटी।

एक्स 1, एक्स 2,…, एक्स टी अवशेष मोडुलो एम की एक पूरी प्रणाली है।

प्रमेय 2। माना (ए, एम) = 1, बी - मनमाना पूर्णांक; तो अगरएक्स 1, एक्स 2,…, एक्स टी -अवशेषों की पूरी प्रणाली मोडुलो एम, फिर संख्याओं का सेट कुल्हाड़ी 1 + बी, कुल्हाड़ी 2 + ख,…, कुल्हाड़ी एम + बी भी अवशेष मोडुलो एम की एक पूरी प्रणाली है।

सबूत।

विचार करना

कुल्हाड़ी 1 + ख, कुल्हाड़ी 2 + ख, ..., कुल्हाड़ी एम + ख (2)

1. समुच्चय (2) की प्रत्येक संख्या किसी न किसी वर्ग की है।
2. कोई भी दो संख्याएँ ax i +b और ax j + b से (2) एक दूसरे के साथ अतुलनीय हैं, अर्थात वे विभिन्न वर्गों से संबंधित हैं।

वास्तव में, यदि (2) में दो संख्याएँ ऐसी हों कि

कुल्हाड़ी मैं + ख कुल्हाड़ी जे + बी (मोड एम), (आई = जे), तो हम प्राप्त करेंगेकुल्हाड़ी और कुल्हाड़ी जे (मॉड एम)। चूंकि (ए, टी) = 1, तो तुलना का गुण तुलना के दोनों भागों को कम कर सकता हैएक । हमें x i x j (mod m) प्राप्त होता है।

शर्त के अनुसार, x i x j (mod m) (i = j) के लिए, क्योंकि x 1, एक्स 2, ..., एक्स एम - कटौती की पूरी प्रणाली।

1. संख्याओं के समुच्चय (2) में शामिल हैंटी संख्याएँ, अर्थात्, जितने वर्ग modulo m हैं।

तो, कुल्हाड़ी 1 + बी, कुल्हाड़ी 2 + बी, ..., कुल्हाड़ी एम + बी अवशेष मोडुलो एम की पूरी प्रणाली है।

उदाहरण।

मान लीजिए एम = 10, ए = 3, बी = 4।

आइए अवशेष मॉड्यूलो 10 की कुछ पूरी प्रणाली लें, उदाहरण के लिए: 0, 1, 2, ..., 9। आइए फॉर्म की संख्याएँ बनाते हैंकुल्हाड़ी + बी। हम प्राप्त करते हैं: 4, 7, 10, 13, 16, 19, 22, 25, 28, 31। संख्याओं का परिणामी सेट अवशेष मॉड्यूलो 10 की एक पूरी प्रणाली है।

1. कटौती की दी गई प्रणाली।

आइए हम निम्नलिखित प्रमेय को सिद्ध करें।

प्रमेय 1.

समान अवशेष वर्ग modulo m की संख्या में m के साथ समान सबसे बड़ा सामान्य भाजक होता है: ifएक बी (मॉड एम), फिर (ए, एम) = (बी, एम)।

सबूत।

चलो ए बी (मॉड एम)। फिर ए = बी + एमटी, जहां टी जेड। इस समानता से यह इस प्रकार है कि (ए,एम) = (बी, एम)।

वास्तव में, मान लीजिए कि a और m का -सामान्य भाजक है, फिर a, एम . चूँकि a = b + mt, तब b=a-mt, इसलिए b. इसलिए, a और m का कोई भी उभयनिष्ठ भाजक m और b का उभयनिष्ठ भाजक होता है।

इसके विपरीत, यदि m और b , तो a = b + mt से विभाज्य है, और इसलिए m और b का कोई भी उभयनिष्ठ भाजक a और m का उभयनिष्ठ भाजक है। प्रमेय सिद्ध हो चुका है।

परिभाषा 1. मापांक का सबसे बड़ा सामान्य भाजक t और कोई भी संख्या a कटौतियों के इस वर्ग सेटी सबसे बड़ा सामान्य भाजक कहा जाता हैटी और अवशेषों का यह वर्ग।

परिभाषा 2. अवशेष वर्ग एक मॉड्यूल एम मॉड्यूलो के साथ कोप्राइम कहा जाता हैएम अगर सबसे बड़ा आम भाजकए और टी बराबर 1 (अर्थात, यदि m और a में से कोई भी संख्या सहअभाज्य है)।

उदाहरण।

चलो = 6. अवशेष वर्ग 2 में संख्याएँ (..., -10, -4, 2, 8, 14, ...) हैं। इनमें से किसी भी संख्या और मॉड्यूल 6 का सबसे बड़ा सामान्य भाजक 2 है। इसलिए, (2, 6) = 2. कक्षा 5 और मॉड्यूल 6 से किसी भी संख्या का सबसे बड़ा सामान्य भाजक 1 है। इसलिए, कक्षा 5 मॉड्यूल के लिए अपेक्षाकृत अभाज्य है। 6.

आइए हम अवशेषों के प्रत्येक वर्ग में से चुनें कोप्राइम मॉडुलो एम एक संख्या के साथ। हम कटौती की एक प्रणाली प्राप्त करते हैं, जो कटौती की पूरी प्रणाली का हिस्सा है। वे उसे बुलाते हैंअवशेषों की कम प्रणाली मोडुलो एम.

परिभाषा 3. अवशेष मोडुलो एम का सेट, प्रत्येक कोप्राइम से एक समय में एक लिया जाता हैटी अवशेष मोडुलो का वर्ग इस मॉड्यूल को कम अवशेष प्रणाली कहा जाता है।

परिभाषा 3 का तात्पर्य अवशेषों की कम प्रणाली प्राप्त करने के लिए एक विधि हैटी: अवशेषों की कुछ पूरी प्रणाली को लिखना और उसमें से उन सभी अवशेषों को हटाना आवश्यक है जो एम के साथ कोप्राइम नहीं हैं। कटौती का शेष सेट कटौती की कम प्रणाली है। जाहिर तौर पर अवशिष्ट मॉडुलो एम के कम सिस्टम की एक अनंत संख्या है।

यदि हम कम से कम गैर-नकारात्मक या बिल्कुल कम अवशेषों की पूरी प्रणाली को प्रारंभिक के रूप में लेते हैं, तो संकेतित तरीके से हम कम से कम गैर-नकारात्मक या बिल्कुल कम से कम अवशेष मोडुलो एम की क्रमशः कम प्रणाली प्राप्त करते हैं।

उदाहरण।

अगर टी = 8, फिर 1, 3, 5, 7 - कम से कम गैर-ऋणात्मक अवशेषों की कम प्रणाली, 1, 3, -3, -1- बिल्कुल कम से कम अवशेषों की कम प्रणाली।

प्रमेय 2।

होने देना m से अपेक्षाकृत अभाज्य वर्गों की संख्या k के बराबर है।तब k पूर्णांकों का कोई संग्रह

जोड़ीदार अतुलनीय मोडुलो एम और अपेक्षाकृत प्राइम टू मी, अवशेष मोडुलो एम की एक कम प्रणाली है।

सबूत

ए) सेट (1) में प्रत्येक संख्या किसी न किसी वर्ग से संबंधित है।

1. (1) से सभी संख्याएं जोड़ीवार अतुलनीय मोडुलो हैंटी, यानी वे अलग-अलग वर्ग के हैं modulo m.
2. (1) में से प्रत्येक संख्या के साथ सहभाज्य हैटी, अर्थात्, ये सभी संख्याएँ मापांक m के साथ सहअभाज्य वर्गों से संबंधित हैं।
3. कुल मिलाकर, (1) हैक संख्याएँ, अर्थात्, अवशेषों की कम प्रणाली के रूप में कई मॉडुलो एम में होना चाहिए।

इसलिए, संख्याओं का समुच्चय(1) - अवशेषों की कम प्रणाली moduloटी।

§चार। यूलर फंक्शन।

यूलर और फ़र्मेट के प्रमेय।

1. यूलर फंक्शन।

. द्वारा निरूपित करें(टी) अवशेषों के वर्गों की संख्या मोडुलो एम कोप्राइम एम के साथ, यानी अवशेषों की कम प्रणाली के तत्वों की संख्या मॉड्यूलोटी. समारोह (टी) सांख्यिक है। वे उसे बुलाते हैंयूलर फंक्शन।

हम अवशेष वर्गों के प्रतिनिधि के रूप में चुनते हैं moduloटी नंबर 1, ..., टी - 1, टी। फिर φ (टी) ऐसी संख्याओं की संख्या है जिसका सहअभाज्य हैटी। दूसरे शब्दों में, (टी) - धनात्मक संख्याओं की संख्या m से अधिक नहीं है और अपेक्षाकृत अभाज्य से m है।

उदाहरण।

1. चलो = 9. अवशेष मॉड्यूल 9 की पूरी प्रणाली में संख्याएं 1, 2, 3, 4, 5, 6, 7, 8, 9 शामिल हैं। इनमें से, संख्याएं 1,2,4, 5, 7, 8 सहअभाज्य हैं। 9 से। अतः चूँकि इन संख्याओं की संख्या 6 है, तो (9) = 6।
2. चलो टी = 12. अवशेषों की पूरी प्रणाली में संख्याएं 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 शामिल हैं। इनमें से संख्या 1, 5, 7, 11 से सहअभाज्य हैं। 12. इसलिए,

(12) = 4.

टी पर = 1, अवशेषों की पूरी प्रणाली में एक वर्ग होता है। संख्या 1 और 1 का सामान्य प्राकृतिक भाजक 1, (1, 1) = 1 है। इस आधार पर, हम φ(1) = 1 रखते हैं।

आइए यूलर फ़ंक्शन की गणना के लिए आगे बढ़ें।

1) यदि एम = पी एक अभाज्य संख्या है, तो(पी) = पी-1।

सबूत।

अवशेष 1, 2, ..., पी- 1 और केवल वे अभाज्य संख्या के साथ सहअभाज्य हैंआर। इसलिए (पी) = पी -1।

2) यदि एम = पी के - एक अभाज्य संख्या की शक्तिपी, फिर

(टी) = (पी -1) । (एक)

सबूत।

अवशेषों की पूरी प्रणाली moduloटी = पी के संख्या 1 के होते हैं,...,पी के - 1, पी के प्राकृतिक विभाजकटी डिग्री हैंआर। इसलिए संख्या एक1 . के अलावा m के साथ एक सामान्य भाजक हो सकता है, केवल जबएकद्वारा विभाजितआर।लेकिन नंबर 1 . के बीच, ... , पीक -1 परआरकेवल संख्याओं को विभाजित करनापी, 2पी, ..., पी2 , ... आरप्रति, जिसकी संख्या हैआरप्रति: पी = पीके-1. इसलिए के साथ कोप्राइमटी = पीप्रतिविश्रामआरप्रति- आरके-1=पीकेएलई(पी-1)संख्याएं। इस प्रकार यह सिद्ध होता है कि

φ (आरप्रति) = पीके-1(आर -1)।

प्रमेय1.

यूलर फलन गुणनात्मक है, अर्थात् सह अभाज्य संख्याओं m और n के लिए हमारे पास φ (mn) = (m) (n) है।

सबूत।

गुणक फलन की परिभाषा में पहली आवश्यकता एक तुच्छ तरीके से पूरी होती है: यूलर फ़ंक्शन को सभी प्राकृतिक संख्याओं के लिए परिभाषित किया जाता है, और (1) = 1. हमें केवल यह दिखाना है कि यदिके प्रकारअपेक्षाकृत अभाज्य संख्याएँ, तब

φ (टीपी)= φ (टी) φ (पी)।(2)

अवशेषों की पूरी प्रणाली को व्यवस्थित करें moduloटीपीजैसापीएक्सटी -मैट्रिक्स

1 2 टी

टी+1 टी+2 2t

………………………………

(पी -1) टी+1 (पी -1) एम +2 शुक्र

क्यों किटीतथापीकोप्राइम, फिर संख्याएक्सके साथ परस्पर सरलटीपीअगर और केवल अगरएक्सके साथ परस्पर सरलटीतथाएक्सके साथ परस्पर सरलपी. लेकिन संख्याकिमी + टीके साथ परस्पर सरलटीअगर और केवल अगरटीके साथ परस्पर सरलटी।इसलिए, एम से अपेक्षाकृत अभाज्य संख्याएं उन स्तंभों में स्थित होती हैं जिनके लिएटीअवशेष मॉड्यूलो की कम प्रणाली के माध्यम से चलता हैटी।ऐसे स्तंभों की संख्या . है(टी)।प्रत्येक कॉलम अवशेष मॉड्यूलो की पूरी प्रणाली प्रस्तुत करता हैपी।इन अवशेषों से(पी)के साथ सह-प्रमुखपी।इसलिए, संख्याओं की कुल संख्या सहअभाज्य और साथटीऔर n के साथ, . के बराबर है(टी)(एन)

(φ (टी)कॉलम, जिनमें से प्रत्येक φ . लेता है(पी)नंबर)। ये संख्याएं, और केवल वे, सहअभाज्य हैंआदि।इस प्रकार यह सिद्ध होता है कि

φ (टीपी)= φ (टी) φ (पी)।

उदाहरण।

№1 . निम्नलिखित समानताएं सिद्ध करें

(4एन) =

सबूत।

№2 . प्रश्न हल करें

समाधान:इसलिये(एम) =, फिर= , वह है=600, =75, =3, तो x-1=1, x=2,

वाई-1=2, वाई=3

उत्तर: x=2, y=3

हम यूलर फ़ंक्शन के मान की गणना कर सकते हैं(एम), संख्या एम के विहित प्रतिनिधित्व को जानना:

एम =.

गुणक के कारण(एम) हमारे पास है:

(एम) =.

लेकिन सूत्र (1) के अनुसार हम पाते हैं कि

-1), और इसलिए

(3)

समानता (3) को इस प्रकार लिखा जा सकता है:

क्यों कि= एम, फिर(4)

सूत्र (3) या, जो समान है, (4) वांछित है।

उदाहरण।

№1 . राशि क्या है

समाधान:,

, =18 (1- ) (1- =18 , फिर= 1+1+2+2+6+6=18.

№2 . यूलर संख्या फलन के गुणों के आधार पर सिद्ध कीजिए कि प्राकृत संख्याओं के अनुक्रम में अभाज्य संख्याओं का अनंत समुच्चय है।

समाधान:एक परिमित समुच्चय द्वारा अभाज्य संख्याओं की संख्या को समतल करना, मान लीजिए किसबसे बड़ी अभाज्य संख्या है और मान लीजिए a=यूलर संख्या फ़ंक्शन के गुणों में से एक के आधार पर सभी अभाज्य संख्याओं का गुणनफल है

चूंकि, तो a एक भाज्य संख्या है, लेकिन चूंकि इसके विहित निरूपण में सभी अभाज्य संख्याएँ हैं, तो= 1। हमारे पास है:

=1 ,

जो असंभव है, और इस प्रकार यह सिद्ध हो जाता है कि अभाज्य संख्याओं का समुच्चय अनंत है।

№3 ।प्रश्न हल करें, जहां एक्स =तथा=2.

समाधान:हम यूलर संख्यात्मक फ़ंक्शन की संपत्ति का उपयोग करते हैं,

,

और शर्त के अनुसार=2.

एक्सप्रेस से=2 , हम पाते हैं, चलो प्रतिस्थापित करें

:

(1+ -1=120, =11 =>

फिर एक्स =, एक्स=11 13=143.

उत्तर:एक्स = 143

2. यूलर का प्रमेय और फ़र्मेट।

तुलना के सिद्धांत में, यूलर का प्रमेय एक महत्वपूर्ण भूमिका निभाता है।

यूलर का प्रमेय।

यदि एक पूर्णांक a, m से अपेक्षाकृत अभाज्य है, तो

(1)

सबूत।होने देना

(2)

अवशेष मोडुलो एम की एक कम प्रणाली है।

यदि एकएकएक पूर्णांक है जो m से अपेक्षाकृत अभाज्य है, तो

(3)

परिभाषा 1. यदि दो अंक 1) एकतथा बीद्वारा विभाजित करते समय पीवही शेष दो आर, तो ऐसी संख्याएँ समदूरस्थ कहलाती हैं या मॉड्यूलो में तुलनीय पी.

कथन 1. होने देना पीकुछ सकारात्मक संख्या। फिर कोई संख्या एकहमेशा और, इसके अलावा, एक अनोखे तरीके से रूप में प्रदर्शित किया जा सकता है

लेकिन इन नंबरों को पूछकर प्राप्त किया जा सकता है आर 0, 1, 2,..., के बराबर पी-1. फलस्वरूप एसपी+आर=एसभी संभावित पूर्णांक मान लेता है।

आइए हम दिखाते हैं कि यह प्रतिनिधित्व अद्वितीय है। चलो दिखावा करते हैं कि पीदो तरह से दर्शाया जा सकता है ए = एसपी + आरतथा ए = एस 1 पी+आरएक । फिर

(2)

इसलिये आर 1 संख्याओं में से एक लेता है 0,1, ..., पी-1, फिर निरपेक्ष मान आर 1 −आरकम पी. लेकिन (2) से यह इस प्रकार है आर 1 −आरविभिन्न पी. फलस्वरूप आर 1 =आरतथा एस 1 =एस.

संख्या आरबुलाया ऋणनंबर एकसापेक्ष पी(दूसरे शब्दों में, संख्या आरकिसी संख्या के भाग के शेष भाग को कहते हैं एकपर पी).

कथन 2. यदि दो अंक एकतथा बीतुलनीय मोडुलो पी, फिर एक-बीद्वारा विभाजित पी.

सचमुच। यदि दो अंक एकतथा बीतुलनीय मोडुलो पी, फिर जब से विभाजित किया जाता है पीएक ही शेष है पी. फिर

द्वारा विभाजित पी, इसलिये समीकरण (3) का दाहिना भाग से विभाजित होता है पी.

कथन 3. यदि दो संख्याओं का अंतर से विभाज्य है पी, तो ये संख्याएँ तुलनीय modulo . हैं पी.

सबूत। द्वारा निरूपित करें आरतथा आरभाग से 1 शेष एकतथा बीपर पी. फिर

उदाहरण 25≡39 (मॉड 7), -18≡14 (मॉड 4)।

यह पहले उदाहरण से इस प्रकार है कि 25 को 7 से विभाजित करने पर वही शेषफल मिलता है जो 39 है। वास्तव में, 25=3 7+4 (शेष 4)। 39=3 7+4 (शेष 4)। दूसरे उदाहरण पर विचार करते समय, ध्यान रखें कि शेष एक गैर-ऋणात्मक संख्या होनी चाहिए जो मापांक (यानी 4) से कम हो। तब हम लिख सकते हैं: −18=−5 4+2 (शेष 2), 14=3 4+2 (शेष 2)। इसलिए, −18 को 4 से विभाजित करने पर 2 शेष बचता है, और 14 को 4 से विभाजित करने पर 2 शेष बचता है।

मोडुलो तुलना के गुण

संपत्ति 1. किसी के लिए भी एकतथा पीहमेशा

तुलना हमेशा जरूरी नहीं होती

कहाँ पे λ संख्याओं का सबसे बड़ा सामान्य भाजक है एमतथा पी.

सबूत। होने देना λ संख्याओं का सबसे बड़ा सामान्य भाजक एमतथा पी. फिर

इसलिये एम (ए-बी)द्वारा विभाजित क, फिर

फलस्वरूप

तथा एमसंख्या के भाजक में से एक है पी, फिर

कहाँ पे एच = पीक्यू।

ध्यान दें कि हम नकारात्मक मॉड्यूल में तुलना की अनुमति दे सकते हैं, अर्थात तुलना आबीमॉड ( पी) का अर्थ है इस मामले में अंतर एक-बीद्वारा विभाजित पी. तुलना के सभी गुण नकारात्मक मॉड्यूल के लिए मान्य रहते हैं।

फॉर्म की तुलना पर विचार करें एक्स 2 ≡एक(मोड पीα), जहां पीएक साधारण विषम संख्या है। जैसा कि धारा 4 4 में दिखाया गया है, इस सर्वांगसमता का हल सर्वांगसमता को हल करके पाया जा सकता है एक्स 2 ≡एक(मोड पी) और तुलना एक्स 2 ≡एक(मोड पीα) के दो हल होंगे यदि एकएक द्विघात अवशेष मोडुलो है पी.

उदाहरण:

द्विघात तुलना हल करें एक्स 2 86 (मॉड 125)।

125 = 5 3, 5 एक अभाज्य संख्या है। आइए देखें कि क्या 86 एक वर्ग मॉड्यूल 5 है।

मूल तुलना के 2 समाधान हैं।

आइए एक तुलना समाधान खोजें एक्स 2 86 (मॉड 5)।

एक्स 2 1 (मॉड 5)।

इस तुलना को पिछले पैराग्राफ में बताए गए तरीके से हल किया जा सकता है, लेकिन हम इस तथ्य का उपयोग करेंगे कि 1 मोडुलो का वर्गमूल ±1 है, और तुलना के ठीक दो समाधान हैं। इस प्रकार, सर्वांगसमता मॉड्यूल 5 का हल है

एक्स±1(मॉड 5) या, अन्यथा, एक्स=±(1+5 टी 1).

परिणामी समाधान को तुलना मॉड्यूल 5 2 =25 में रखें:

एक्स 2 86 (मॉड 25)

एक्स 2 11 (मॉड 25)

(1+5टी 1) 2 11 (मॉड 25)

1+10टी 1 +25टी 1 2 11 (मॉड 25)

10टी 1 10 (मॉड 25)

2टी 1 2 (मॉड 5)

टी 1 1 (मॉड 5), या समकक्ष, टी 1 =1+5टी 2 .

तब सर्वांगसमता मॉड्यूलो 25 का हल है एक्स=±(1+5(1+5 .) टी 2))=±(6+25 टी 2))। परिणामी समाधान को तुलना मॉड्यूल 5 3 =125 में रखें:

एक्स 2 86 (मॉड 125)

(6+25टी 2) 2 86 (मॉड 125)

36+12 25 टी 2 +625टी 2 2 86 (मॉड 125)

12 25 टी 2 50 (मॉड 125)

12टी 2 2 (मॉड 5)

2टी 2 2 (मॉड 5)

टी 2 1 (मॉड 5), या टी 2 =1+5टी 3 .

तब तुलना मॉड्यूल 125 का हल है एक्स=±(6+25(1+5 .) टी 3))=±(31+125 टी 3).

उत्तर: एक्स± 31 (मॉड 125)।

अब फॉर्म की तुलना पर विचार करें एक्स 2 ≡एक(mod2α)। इस तरह की तुलना के हमेशा दो समाधान नहीं होते हैं। ऐसे मॉड्यूल के लिए, निम्नलिखित मामले संभव हैं:

1) α = 1। तब तुलना का समाधान तभी होता है जब एक 1 (मॉड 2), और समाधान है एक्स 1 (मॉड 2) (एक समाधान)।

2) α=2। तुलना का समाधान तभी होता है जब एक 1 (मॉड 4), और समाधान है एक्स±1(मॉड 4) (दो समाधान)।

3) α≥3। तुलना का समाधान तभी होता है जब एक 1 (मॉड 8), और ऐसे चार समाधान होंगे। तुलना एक्स 2 ≡एक(mod 2 α) α≥3 के लिए उसी तरह हल किया जाता है जैसे फॉर्म की तुलना एक्स 2 ≡एक(मोड पीα), केवल समाधान मॉड्यूलो 8 प्रारंभिक समाधान के रूप में कार्य करता है: एक्स±1(मॉड 8) और एक्स± 3 (मॉड 8)। उनकी तुलना मॉड्यूलो 16, फिर मॉड्यूलो 32, और इसी तरह मॉड्यूलो 2 α तक की जानी चाहिए।

उदाहरण:

तुलना हल करें एक्स 2 33 (मॉड 64)

64=26. आइए देखें कि मूल तुलना का कोई समाधान है या नहीं। 33≡1 (मॉड 8), इसलिए तुलना के 4 समाधान हैं।

मॉड्यूलो 8 ये समाधान होंगे: एक्स±1(मॉड 8) और एक्स±3 (मॉड 8), जिसे के रूप में दर्शाया जा सकता है एक्स=±(1+4 टीएक)। इस व्यंजक को तुलनात्मक मॉड्यूल 16 . में प्रतिस्थापित करें

एक्स 2 33 (मॉड 16)

(1+4टी 1) 2 1 (मॉड 16)

1+8टी 1 +16टी 1 2 1 (मॉड 16)

8टी 1 0 (मॉड 16)

टी 1 0 (मॉड 2)

तब समाधान रूप लेगा एक्स=±(1+4 टी 1)=±(1+4(0+2 .) टी 2))=±(1+8 टी 2))। परिणामी विलयन को सर्वांगसमता मॉड्यूल 32 में रखें:

एक्स 2 33 (मॉड 32)

(1+8टी 2) 2 1 (मॉड 32)

1+16टी 2 +64टी 2 2 1 (मॉड 32)

16टी 2 0 (मॉड 32)

टी 2 0 (मॉड 2)

तब समाधान रूप लेगा एक्स=±(1+8 टी 2) =±(1+8(0+2t 3)) =±(1+16 टी 3))। परिणामी समाधान को तुलना मॉड्यूल 64 में बदलें:

एक्स 2 33 (मॉड 64)

(1+16टी 3) 2 33 (मॉड 64)

1+32टी 3 +256टी 3 2 33 (मॉड 64)

32टी 3 32 (मॉड 64)

टी 3 1 (मॉड 2)

तब समाधान रूप लेगा एक्स=±(1+16 टी 3) =±(1+16(1+2t 4)) =±(17+32 टीचार)। तो, मॉड्यूल 64, मूल तुलना के चार समाधान हैं: एक्स±17(मॉड 64)और एक्स± 49 (मॉड 64)।

अब एक सामान्य तुलना पर विचार करें: एक्स 2 ≡एक(मोड एम), (एक,एम)=1, - मॉड्यूल का विहित अपघटन एम. 4 के मद 4 से प्रमेय के अनुसार, यह तुलना प्रणाली के बराबर है

यदि इस प्रणाली की हर तुलना निर्णायक है, तो पूरी प्रणाली निर्णायक है। इस प्रणाली की प्रत्येक तुलना का समाधान खोजने के बाद, हम पहली डिग्री की तुलना की एक प्रणाली प्राप्त करते हैं, जिसे हल करते हुए, चीनी शेष प्रमेय का उपयोग करके, हम मूल तुलना का समाधान प्राप्त करते हैं। इसके अलावा, मूल तुलना के विभिन्न समाधानों की संख्या (यदि यह हल करने योग्य है) 2 क, अगर α = 1, 2 क+1 अगर α=2, 2 क+2 अगर α≥3।

उदाहरण:

तुलना हल करें एक्स 2 4 (मॉड 21)।