सर्वांगसमता क्या है? — गणित

परिभाषा 29.4 उच्च माध्यमिक गणित · अध्याय 29 — अंकगणित

मान लीजिए $n \in \N^*$ है। दो पूर्णांक $a, b$ $n$ के सापेक्ष सर्वांगसम हैं, और इसे $a \equiv b \pmod n$ लिखते हैं, यदि $n \mid (a - b)$ हो — अर्थात् यदि $a$ और $b$ को $n$ से यूक्लिडीय भाग देने पर एक ही शेषफल बचे।

अध्याय में पढ़ें →

परिभाषा 6.18 विश्वविद्यालय गणित — स्नातक वर्ष 1 · अध्याय 6 — पूर्णांक अंकगणित

$n \in \N^*$ के लिए: $a \equiv b \pmod n$ जब $n \mid a - b$ । यह ऐसा तुल्यता संबंध है जो योग और गुणन के अनुकूल है: यदि $a \equiv b$ और $a' \equiv b'$ ( $n$ के सापेक्ष), तो $a + a' \equiv b + b'$ , $aa' \equiv bb'$ , और $k \in \N$ के लिए $a^k \equiv b^k$ ।

उदाहरण

उदाहरण 6.19 (नवशेष परीक्षण)

$+$ और $\times$ के साथ अनुकूलता उतनी ही पुरानी जाँच-युक्ति है जितना व्यापार। चूँकि $10 \equiv 1 \pmod 9$ , प्रत्येक पूर्णांक $9$ के सापेक्ष अपने अंकों के योग के सर्वांगसम है (उपपत्ति अभ्यास 6.2 में)। दावा $1234 \times 567 = 699\,678$ जाँचने के लिए: अंकों के योग $1234 \equiv 1$ और $567 \equiv 18 \equiv 0 \pmod 9$ देते हैं, अतः गुणनफल $\equiv 1 \times 0 = 0$ होना चाहिए; और सचमुच $6 + 9 + 9 + 6 + 7 + 8 = 45 \equiv 0$ । जाँच पास हो जाती है (और गुणनफल वस्तुतः सही है)। यदि किसी ने $699\,478$ बताया होता, तो अंकों का योग $43 \equiv 7 \not\equiv 0$ उसे तुरंत पकड़ लेता। यह परीक्षण एकपक्षीय है — वह भूल तभी पकड़ता है जब भूल स्वयं $9$ का गुणज न हो — और यह छोटे पैमाने पर ठीक उदाहरण 6.24 वाला छद्म-अभाज्य पाठ है: सर्वांगसमता की जाँच खंडन करती है, प्रमाणित नहीं करती।

उदाहरण 6.21 ( $26$ के सापेक्ष $7$ का प्रतिलोम)

चूँकि $\gcd(7, 26) = 1$ , $7$ का वर्ग $26$ के सापेक्ष व्युत्क्रमणीय है। विस्तारित यूक्लिड:

26 = 3 \times 7 + 5, \qquad 7 = 1 \times 5 + 2, \qquad 5 = 2 \times 2 + 1 ,

फिर उलटी दिशा में:

1 = 5 - 2 \times 2 = 5 - 2(7 - 5) = 3 \times 5 - 2 \times 7 = 3(26 - 3 \times 7) - 2 \times 7 = 3 \times 26 - 11 \times 7 .

अतः $7 \times (-11) \equiv 1 \pmod{26}$ , अर्थात् $7^{-1} \equiv -11 \equiv 15 \pmod{26}$ ; जाँच: $7 \times 15 = 105 = 4 \times 26 + 1$ । प्रतिलोम हाथ में होने पर कोई भी सर्वांगसमता $7x \equiv c \pmod{26}$ एक ही गुणा में हल हो जाती है: $x \equiv 15c$ । यही यांत्रिक प्रतिलोमन मापांकी अंकगणित का परिश्रमी घोड़ा है — और टिप्पणी 6.27 में उल्लिखित सार्वजनिक-कुंजी प्रोटोकॉलों का भी, जहाँ मापांक सैकड़ों अंकों के होते हैं पर कलनविधि ठीक यही है।

उदाहरण 6.22 (जब गुणांक व्युत्क्रमणीय न हो)

$12x \equiv 8 \pmod{20}$ हल कीजिए। यहाँ $\gcd(12, 20) = 4$ , अतः $12$ $20$ के सापेक्ष व्युत्क्रमणीय नहीं है — फिर भी समीकरण साधा जा सकता है। सर्वांगसमता कहती है $20 \mid 12x - 8$ ; पूरे संबंध को $4$ (तीनों सामग्रियों का भाजक) से भाग देने पर वह $5 \mid 3x - 2$ के तुल्य है, अर्थात्

3x \equiv 2 \pmod 5 .

अब $\gcd(3, 5) = 1$ और $3^{-1} \equiv 2 \pmod 5$ ( $3 \times 2 = 6 \equiv 1$ ), अतः $x \equiv 4 \pmod 5$ : हल $x \equiv 4, 9, 14, 19 \pmod{20}$ हैं — अर्थात् $20$ के सापेक्ष चार वर्ग, जो महत्तम समापवर्तक से मेल खाते हैं। (यदि दायाँ पक्ष $4$ से विभाज्य न होता, मान लीजिए $12x \equiv 6 \pmod{20}$ , तो कोई हल होता ही नहीं: बायाँ पक्ष सदा $\equiv 0 \pmod 4$ रहता है।) व्यापक आकार: $ax \equiv b \pmod n$ तभी हल हो सकता है जब $\gcd(a, n) \mid b$ , और तब उसके ठीक $\gcd(a, n)$ हल-वर्ग होते हैं — सब कुछ महत्तम समापवर्तक से भाग दीजिए और प्रतिलोम लीजिए।

अध्याय में पढ़ें →

उदाहरण

संबंधित पद