उच्च माध्यमिक गणित · Grades 10–12

29अंकगणित

अंकगणित पूर्णांकों का अध्ययन करता है: विभाज्यता, अभाज्य संख्याएँ, शेषफल। बहुत समय तक इसे शुद्धतम शुद्ध गणित माना जाता रहा, और आज वही हर ऑनलाइन भुगतान की रक्षा करता है: RSA गूढ़लेखन-पद्धति इसी अध्याय में सिद्ध होने वाली बेज़ू, गाउस और फ़र्मा की प्रमेयों पर टिकी है।

29.1 विभाज्यता और यूक्लिडीय भाग

परिभाषा 29.1 (विभाज्यता)

मान लीजिए $a, b \in \Z$ है। हम कहते हैं कि $b$ $a$ को विभाजित करता है, और $b \mid a$ लिखते हैं, यदि ऐसा $k \in \Z$ हो कि $a = kb$ हो। हम यह भी कहते हैं कि $a$ $b$ का गुणज है।

प्रतिज्ञप्ति 29.2

यदि $c \mid a$ और $c \mid b$ हों, तो $c$ हर पूर्णांक संयोजन $au + bv$ ( $u, v \in \Z$ ) को विभाजित करता है। यदि $a \mid b$ और $b \mid a$ हों, जहाँ $a,b \in \N$ , तो $a = b$ । यदि $a \mid b$ और $b \neq 0$ हों, तो $\abs a \leq \abs b$ ।

उपपत्ति. $a = kc$ , $b = lc$ लिखिए: तब $au + bv = (ku + lv)c$ । शेष बिंदु $b = ka \neq 0$ होने पर $\abs k \geq 1$ के साथ $\abs{a} = \abs{k}\,\abs{b}$ से निकलते हैं। ∎

प्रमेय 29.3 (यूक्लिडीय भाग)

मान लीजिए $a \in \Z$ और $b \in \N^*$ हैं। ऐसा अद्वितीय युग्म $(q, r) \in \Z \times \N$ है कि

a = bq + r \qquad\text{और}\qquad 0 \leq r < b .

$q$ भागफल है और $r$ शेषफल।

उपपत्ति. अस्तित्व: $a$ से अधिक न होने वाले $b$ के गुणजों के समुच्चय का एक सबसे बड़ा अवयव $bq$ है (वह अरिक्त और ऊपर परिबद्ध है); $r = a - bq$ रखिए। अधिकतमता से $b(q+1) > a$ , इसलिए $0 \leq r < b$ । अद्वितीयता: यदि $0 \leq r, r' < b$ के साथ $bq + r = bq' + r'$ हो, तो $b(q - q') = r' - r$ और $\abs{r' - r} < b$ : $b$ से कम निरपेक्ष मान वाला $b$ का गुणज $0$ ही हो सकता है, इसलिए $r = r'$ और $q = q'$ । ∎

29.2 सर्वांगसमताएँ

परिभाषा 29.4 (सर्वांगसमता)

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

प्रतिज्ञप्ति 29.5 (संक्रियाओं के साथ संगति)

यदि $a \equiv b \pmod n$ और $c \equiv d \pmod n$ हों, तो

a + c \equiv b + d, \qquad ac \equiv bd, \qquad a^k \equiv b^k \ (k \in \N) \pmod n .

उपपत्ति. $n$ $(a-b) + (c-d) = (a+c) - (b+d)$ को विभाजित करता है, और $ac - bd = a(c - d) + d(a - b)$ भी $n$ का गुणज है। घात वाला नियम गुणनफल वाले नियम से आगमन द्वारा निकलता है। ∎

विधि 29.6 ( $n$ के सापेक्ष घातें निकालना)

$a^k \bmod n$ निकालने के लिए आधार को $n$ के सापेक्ष घटाइए, फिर $\pm1$ के सर्वांगसम $a$ की कोई छोटी घात ढूँढ़िए और उससे घातांक को समेट दीजिए। जैसे $2^{100} \bmod 7$ : चूँकि $2^3 = 8 \equiv 1 \pmod 7$ और $100 = 3\times33 + 1$ , इसलिए

2^{100} = \left(2^{3}\right)^{33} \times 2 \equiv 1^{33}\times 2 = 2 \pmod 7 .

29.3 महत्तम समापवर्तक, बेज़ू और गाउस

परिभाषा 29.7 (महत्तम समापवर्तक)

मान लीजिए $a, b$ ऐसे पूर्णांक हैं जो दोनों शून्य नहीं हैं। महत्तम समापवर्तक $\gcd(a, b)$ वह सबसे बड़ा पूर्णांक है जो $a$ और $b$ दोनों को विभाजित करता है। जब $\gcd(a,b) = 1$ हो, तब $a$ और $b$ सह-अभाज्य कहलाते हैं।

प्रतिज्ञप्ति 29.8 (यूक्लिड की कलनविधि)

यदि $a = bq + r$ ( $b \neq 0$ ) हो, तो $\gcd(a, b) = \gcd(b, r)$ । इसलिए यूक्लिडीय भाग को बार-बार दोहराने से $\gcd(a,b)$ निकल आता है: महत्तम समापवर्तक अंतिम शून्येतर शेषफल है।

उपपत्ति. $a$ और $b$ का कोई भी उभयनिष्ठ भाजक $r = a - bq$ (प्रतिज्ञप्ति 29.2) को विभाजित करता है, अतः वह $b$ और $r$ का भी उभयनिष्ठ भाजक है; और इसके उलट भी, क्योंकि $a = bq + r$ । दोनों युग्मों के उभयनिष्ठ भाजक एक ही हैं, इसलिए महत्तम समापवर्तक भी। कलनविधि समाप्त हो जाती है क्योंकि शेषफल अऋणात्मक पूर्णांकों का निरंतर ह्रासमान अनुक्रम बनाते हैं। ∎

उदाहरण 29.9

$\gcd(252, 198)$ : $252 = 198 + 54$ ; $198 = 3\times54 + 36$ ; $54 = 36 + 18$ ; $36 = 2 \times 18 + 0$ । अतः $\gcd(252,198) = 18$ ।

प्रमेय 29.10 (बेज़ू सर्वसमिका)

मान लीजिए $a, b$ ऐसे पूर्णांक हैं जो दोनों शून्य नहीं हैं, और $d = \gcd(a,b)$ है। ऐसे $u, v \in \Z$ हैं कि

au + bv = d .

विशेष रूप से, $a$ और $b$ सह-अभाज्य हैं यदि और केवल यदि किन्हीं पूर्णांकों $u, v$ के लिए $au + bv = 1$ हो।

उपपत्ति. यूक्लिड की कलनविधि उल्टी चलाइए: हर शेषफल पिछले दोनों का पूर्णांक संयोजन है, और आरंभिक आँकड़े $a, b$ स्वयं अपने संयोजन हैं; नीचे से ऊपर प्रतिस्थापन करते जाने पर अंतिम शून्येतर शेषफल $d$ $a$ और $b$ का पूर्णांक संयोजन बन जाता है। (उदाहरण 29.9 में: $18 = 54 - 36 = 54 - (198 - 3\times54) = 4\times54 - 198 = 4(252 - 198) - 198 = 4\times252 - 5\times198$ ।)

तुल्यता के लिए: यदि $\gcd(a,b) = 1$ हो, तो बेज़ू $u, v$ दे देता है; इसके उलट, $a$ और $b$ का कोई भी उभयनिष्ठ भाजक $au + bv = 1$ को विभाजित करता है, जिससे $\gcd(a,b) = 1$ अनिवार्य हो जाता है। ∎

प्रमेय 29.11 (गाउस की प्रमेयिका)

मान लीजिए $a, b, c \in \Z$ है। यदि $a \mid bc$ और $\gcd(a, b) = 1$ हों, तो $a \mid c$ ।

उपपत्ति. बेज़ू $au + bv = 1$ देता है; $c$ से गुणा कीजिए: $acu + bcv = c$ । बाएँ पक्ष के दोनों पद $a$ के गुणज हैं (दूसरा इसलिए कि $a \mid bc$ ), अतः $c$ भी। ∎

उपप्रमेय 29.12

यदि $a \mid c$ , $b \mid c$ और $\gcd(a,b) = 1$ हों, तो $ab \mid c$ ।

उपपत्ति. $c = ak$ लिखिए। $b \mid ak$ और $\gcd(a,b)=1$ से गाउस $b \mid k$ देता है, मान लीजिए $k = bl$ ; तब $c = abl$ । ∎

29.4 अभाज्य संख्याएँ

परिभाषा 29.13 (अभाज्य)

पूर्णांक $p \geq 2$ अभाज्य है यदि उसके एकमात्र धनात्मक भाजक $1$ और $p$ हों।

प्रतिज्ञप्ति 29.14

हर पूर्णांक $n \geq 2$ का कोई अभाज्य भाजक होता है; और यदि $n$ अभाज्य न हो, तो उसका कोई अभाज्य भाजक $\leq \sqrt n$ होता है। यदि कोई अभाज्य $p$ किसी गुणनफल $ab$ को विभाजित करे, तो $p \mid a$ या $p \mid b$ (यूक्लिड की प्रमेयिका)।

उपपत्ति. $n$ का सबसे छोटा भाजक $d \geq 2$ अभाज्य है ( $d$ का कोई भी उचित भाजक $n$ का उससे छोटा भाजक होता)। यदि $n = de$ भाज्य हो और $2 \leq d \leq e$ हो, तो $d^2 \leq de = n$ , इसलिए $d \leq \sqrt n$ । यूक्लिड की प्रमेयिका के लिए: यदि $p \nmid a$ हो, तो $\gcd(p, a) = 1$ ( $p$ के एकमात्र भाजक $1$ और $p$ हैं), और गाउस की प्रमेयिका $p \mid b$ दे देती है। ∎

प्रमेय 29.15 (यूक्लिड)

अभाज्य संख्याएँ अनंत हैं।

उपपत्ति. अभाज्यों की कोई भी परिमित सूची $p_1, \dots, p_k$ दी होने पर $N = p_1 p_2 \cdots p_k + 1$ पर विचार कीजिए। कोई अभाज्य $p$ $N$ को विभाजित करता है; पर कोई भी $p_i$ $N$ को विभाजित नहीं करता (शेषफल $1$ है), इसलिए $p$ ऐसा अभाज्य है जो सूची में नहीं है। कोई भी परिमित सूची अभाज्यों को समाप्त नहीं कर सकती। ∎

प्रमेय 29.16 (अंकगणित की मूल प्रमेय)

हर पूर्णांक $n \geq 2$ अभाज्यों का गुणनफल है, और यह गुणनखंडन गुणनखंडों के क्रम तक अद्वितीय है:

n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r}, \qquad p_1 < p_2 < \dots < p_r \text{ अभाज्य},\ \alpha_i \geq 1 .

उपपत्ति. अस्तित्व, प्रबल आगमन से: अभाज्य $n$ स्वयं अपना गुणनखंडन है; अन्यथा $2 \leq d, e < n$ वाला $n = de$ , और आगमन-परिकल्पना से दोनों गुणनखंडित हो जाते हैं। अद्वितीयता: मान लीजिए $p_1\cdots p_s = q_1 \cdots q_t$ (अभाज्य, पुनरावृत्ति की छूट के साथ)। यूक्लिड की प्रमेयिका से $p_1$ किसी $q_j$ को विभाजित करता है, और अभाज्य होने के कारण $p_1 = q_j$ ; उसे काटकर यही दोहराइए। दोनों गुणनखंडन पद-दर-पद मेल खा जाते हैं। ∎

प्रमेय 29.17 (फ़र्मा की लघु प्रमेय)

मान लीजिए $p$ अभाज्य है और $p \nmid a$ वाला $a \in \Z$ है। तब

a^{p-1} \equiv 1 \pmod p .

हर $a \in \Z$ के लिए (कोई सह-अभाज्यता माने बिना) $a^p \equiv a \pmod p$ ।

उपपत्ति. $p$ के सापेक्ष $p - 1$ पूर्णांकों $a, 2a, 3a, \dots, (p-1)a$ पर विचार कीजिए। इनमें से कोई $\equiv 0$ नहीं है (यदि $1 \leq k \leq p-1$ के साथ $p \mid ka$ हो, तो यूक्लिड की प्रमेयिका $p \mid k$ अनिवार्य कर देती है, जो असंभव है), और वे $p$ के सापेक्ष जोड़े-जोड़े भिन्न हैं (यदि $ka \equiv la$ हो, तो $p \mid (k - l)a$ , इसलिए $p \mid k - l$ , अतः $k = l$ )। अतः $p$ के सापेक्ष वे किसी क्रम में संख्याएँ $1, 2, \dots, p-1$ ही हैं। सभी सर्वांगसमताओं का गुणा करने पर:

a^{p-1}\,(p-1)! \equiv (p-1)! \pmod p .

चूँकि $p$ $1, \dots, p-1$ में से किसी को विभाजित नहीं करता, इसलिए यूक्लिड की प्रमेयिका बार-बार लगाकर $(p-1)!$ काटा जा सकता है, जिससे $a^{p-1} \equiv 1$ बचता है। दूसरा रूप $a$ से गुणा करने पर मिलता है (और $p \mid a$ होने पर वह तुच्छ है)। ∎

उदाहरण 29.18 (गूढ़लेखन में अनुप्रयोग)

फ़र्मा की प्रमेय $n$ के सापेक्ष घातांकन को उलटने योग्य बना देती है, बशर्ते घातांक उपयुक्त ढंग से चुने जाएँ — और यही RSA गूढ़लेखन-पद्धति का हृदय है। बड़े अभाज्य $p, q$ और $n = pq$ के साथ $n$ तथा एक घातांक $e$ सार्वजनिक कर दिए जाते हैं; गूढ़लेखन $x \mapsto x^e \bmod n$ है। गूढ़वाचन के लिए ऐसा घातांक $d$ चाहिए जिसके लिए $ed \equiv 1 \pmod{(p-1)(q-1)}$ हो, और उसे केवल वही निकाल सकता है जो $p$ और $q$ जानता हो — और $n$ से $p, q$ वापस पाने का अर्थ है सैकड़ों अंकों वाली संख्या का गुणनखंडन, जो किसी भी ज्ञात कलनविधि से उचित समय में नहीं होता।

29.5 अभ्यास

अभ्यास 29.1 ★

$2026$ को $17$ से, और $-2026$ को $17$ से यूक्लिडीय भाग देने पर भागफल और शेषफल निकालिए।

हल

हल — अभ्यास 29.1.

$17 \times 119 = 2023$ , इसलिए $2026 = 17 \times 119 + 3$ : भागफल $119$ , शेषफल $3$ । $-2026$ के लिए: $-2026 = 17\times(-120) + 14$ (सचमुच $17 \times 120 = 2040$ और $2040 - 2026 = 14$ ): भागफल $-120$ , शेषफल $14$ (शेषफल $\intco{0}{17}$ में होना चाहिए, इसलिए वह $-3$ नहीं है)।

अभ्यास 29.2 ★

$10$ के सापेक्ष $7^{100}$ का शेषफल क्या है? ( $7^{100}$ का अंतिम अंक क्या है?)

हल

हल — अभ्यास 29.2.

$10$ के सापेक्ष: $7^2 = 49 \equiv 9 \equiv -1$ । अतः $7^{100} = \left(7^2\right)^{50} \equiv (-1)^{50} = 1 \pmod{10}$ : $7^{100}$ का अंतिम अंक $1$ है।

अभ्यास 29.3 ★

यूक्लिड की कलनविधि से $\gcd(1071, 462)$ निकालिए, और ऐसे पूर्णांक $u, v$ ज्ञात कीजिए कि $1071u + 462v = \gcd(1071, 462)$ हो।

हल

हल — अभ्यास 29.3.

यूक्लिड: $1071 = 2\times462 + 147$ ; $462 = 3\times147 + 21$ ; $147 = 7\times21 + 0$ । इसलिए $\gcd = 21$ ।

पीछे प्रतिस्थापन: $21 = 462 - 3\times147 = 462 - 3(1071 - 2\times462) = 7\times462 - 3\times1071$ । इस प्रकार $u = -3$ , $v = 7$ : $1071\times(-3) + 462\times7 = 21$ ।

अभ्यास 29.4 ★

दिखाइए कि हर $n \in \Z$ के लिए $n^2$ $4$ के सापेक्ष $0$ या $1$ के सर्वांगसम है। इससे निकालिए कि कोई पूर्णांक $\equiv 3 \pmod 4$ दो वर्गों का योग कभी नहीं होता।

हल

हल — अभ्यास 29.4.

हर पूर्णांक $\equiv 0, 1, 2$ या $3 \pmod 4$ है, और वर्ग करने पर: $0^2 \equiv 0$ , $1^2 \equiv 1$ , $2^2 = 4 \equiv 0$ , $3^2 = 9 \equiv 1$ । इसलिए $n^2 \equiv 0$ या $1 \pmod 4$ । तब दो वर्गों का योग $0 + 0$ , $0 + 1$ या $1 + 1$ के सर्वांगसम होता है, अर्थात् $0$ , $1$ या $2 \pmod 4$ के — कभी $3$ के नहीं।

अभ्यास 29.5 ★★

दिखाइए कि सभी $n \in \N$ के लिए $n(n+1)(2n+1)$ $6$ से विभाज्य है।

हल

हल — अभ्यास 29.5.

$2$ से विभाज्यता: $n$ और $n + 1$ में से एक सम है। $3$ से विभाज्यता: यदि $n \equiv 0$ हो तो $3 \mid n$ ; यदि $n \equiv 1 \pmod 3$ हो तो $2n + 1 \equiv 3 \equiv 0$ ; और यदि $n \equiv 2$ हो तो $n + 1 \equiv 0$ । हर स्थिति में $3$ गुणनफल को विभाजित करता है। चूँकि $\gcd(2,3) = 1$ है, इसलिए उपप्रमेय 29.12 $6 \mid n(n+1)(2n+1)$ दे देता है। (इससे यह भी फिर सिद्ध हो जाता है कि अभ्यास 20.1 के वर्गों का योग $\frac{n(n+1)(2n+1)}{6}$ पूर्णांक है।)

अभ्यास 29.6 ★★

$\Z$ में सर्वांगसमता $5x \equiv 3 \pmod{11}$ हल कीजिए। (संकेत: $11$ के सापेक्ष $5$ का प्रतिलोम ज्ञात कीजिए।)

हल

हल — अभ्यास 29.6.

हम $11$ के सापेक्ष $5$ का प्रतिलोम ढूँढ़ते हैं: आज़माने से (या बेज़ू से) $5 \times 9 = 45 = 44 + 1 \equiv 1 \pmod{11}$ । सर्वांगसमता को $9$ से गुणा करने पर:

x \equiv 9 \times 3 = 27 \equiv 5 \pmod{11}.

हल पूर्णांक $x = 5 + 11k$ , $k \in \Z$ हैं। (जाँच: $5\times5 = 25 \equiv 3 \pmod{11}$ ।)

अभ्यास 29.7 ★★

$\Z \times \Z$ में डायोफैंटीय समीकरण

17x - 40y = 1,

हल कीजिए, फिर $17x - 40y = 6$ के सभी हल बताइए।

हल

हल — अभ्यास 29.7.

$\gcd(17, 40) = 1$ , इसलिए हल मौजूद हैं। यूक्लिड: $40 = 2\times17 + 6$ ; $17 = 2\times6 + 5$ ; $6 = 5 + 1$ । पीछे प्रतिस्थापन करने पर: $1 = 6 - 5 = 6 - (17 - 2\times6) = 3\times6 - 17 = 3(40 - 2\times17) - 17 = 3\times40 - 7\times17$ । अतः $17\times(-7) - 40\times(-3) = 1$ : विशेष हल $(x_0, y_0) = (-7, -3)$ ।

$17x - 40y = 1$ का व्यापक हल: विशेष संबंध घटाने पर $17(x + 7) = 40(y + 3)$ ; और चूँकि $\gcd(17, 40) = 1$ है, गाउस $40 \mid x + 7$ देते हैं, इसलिए $x = -7 + 40k$ और फिर $y = -3 + 17k$ , $k \in \Z$ (और ये सब जाँच में खरे उतरते हैं)।

$17x - 40y = 6$ के लिए विशेष हल को $6$ से गुणा कीजिए: $(x_1, y_1) = (-42, -18)$ , और उसी तर्क से

x = -42 + 40k, \qquad y = -18 + 17k, \qquad k \in \Z .

(जैसे $k = 2$ : $x = 38$ , $y = 16$ ; और सचमुच $17\times38 - 40\times16 = 646 - 640 = 6$ ।)

अभ्यास 29.8 ★★

अभाज्य गुणनखंडन की अद्वितीयता का उपयोग करके दिखाइए कि $\sqrt2$ अपरिमेय है ( $a^2 = 2b^2$ के दोनों पक्षों पर $2$ के घातांक की तुलना कीजिए)।

हल

हल — अभ्यास 29.8.

मान लीजिए $a, b \in \N^*$ के साथ $\sqrt2 = \frac ab$ है; तब $a^2 = 2b^2$ । किसी वर्ग के अभाज्य गुणनखंडन में हर घातांक सम होता है; इसलिए $a^2$ में $2$ का घातांक सम है, जबकि $2b^2$ में वह विषम है (किसी सम संख्या से एक अधिक)। एक ही पूर्णांक के दो गुणनखंडनों में $2$ के घातांक भिन्न होना प्रमेय 29.16 की अद्वितीयता का खंडन है। अतः ऐसी कोई भिन्न है ही नहीं: $\sqrt2 \notin \Q$ ।

अभ्यास 29.9 ★★★

मान लीजिए $p$ कोई अभाज्य है।

दिखाइए कि $1 \leq k \leq p - 1$ के लिए $p$ $\dbinom{p}{k}$ को विभाजित करता है। (संकेत: $k\binom pk = p\binom{p-1}{k-1}$ , अभ्यास 27.7 और गाउस की प्रमेयिका का उपयोग कीजिए।)
$a \geq 0$ पर आगमन से फ़र्मा की लघु प्रमेय की एक और उपपत्ति $a^p \equiv a \pmod p$ के रूप में निकालिए।

हल

हल — अभ्यास 29.9.

1. $k\binom pk = p \binom{p-1}{k-1}$ से $p$ $k\binom pk$ को विभाजित करता है। $1 \leq k \leq p-1$ के लिए $p \nmid k$ और $p$ के अभाज्य होने से $\gcd(p, k) = 1$ मिलता है, इसलिए गाउस की प्रमेयिका $p \mid \binom pk$ दे देती है।

2. $a$ पर आगमन। $a = 0$ के लिए: $0^p \equiv 0$ । मान लीजिए $a^p \equiv a \pmod p$ है। द्विपद प्रमेय से

(a+1)^p = \sum_{k=0}^{p} \binom pk a^k \equiv a^p + 1 \pmod p,

जहाँ बिंदु 1 के अनुसार बीच के सारे पद $p$ के सापेक्ष लुप्त हो जाते हैं। आगमन-परिकल्पना से $(a+1)^p \equiv a + 1 \pmod p$ । इससे सभी $a \in \N$ के लिए $a^p \equiv a$ सिद्ध हो जाता है, और स्थिति $a < 0$ उपयुक्त धनात्मक प्रतिनिधि के रूप में $a \equiv a + kp$ लिखने से निकल आती है।

अभ्यास 29.10 ★★★

(चीनी शेषफल समस्या.) वे सभी पूर्णांक $n$ ज्ञात कीजिए जिनके लिए

n \equiv 2 \pmod 3, \qquad n \equiv 3 \pmod 5, \qquad n \equiv 2 \pmod 7 .

(संकेत: पहली दो शर्तें हल कीजिए, फिर तीसरी जोड़िए; बेज़ू गुणांक सहायक होंगे।)

हल

हल — अभ्यास 29.10.

$n \equiv 2 \pmod 3$ और $n \equiv 3 \pmod 5$ : $n = 2 + 3s$ लिखिए; तब $2 + 3s \equiv 3 \pmod 5$ , अर्थात् $3s \equiv 1 \pmod 5$ । $5$ के सापेक्ष $3$ का प्रतिलोम $2$ है ( $3\times2 = 6 \equiv 1$ ), इसलिए $s \equiv 2 \pmod 5$ , मान लीजिए $s = 2 + 5t$ , और $n = 8 + 15t$ : पहली दो शर्तों का अर्थ $n \equiv 8 \pmod{15}$ है।

$n \equiv 2 \pmod 7$ जोड़ने पर: $8 + 15t \equiv 2 \pmod 7$ , और $15 \equiv 1 \pmod 7$ , इसलिए $t \equiv -6 \equiv 1 \pmod 7$ , मान लीजिए $t = 1 + 7u$ । अतः $n = 23 + 105u$ :

n \equiv 23 \pmod{105}.

(जाँच: $23 = 3\times7 + 2 = 5\times4 + 3 = 7\times3 + 2$ ।)

29.6 समस्या: गुप्त कूट और जाँच-अंक

समस्या 29.1

सप्ताहांत समस्या — सर्वांगसमताएँ हर बारकोड और हर क्रेडिट कार्ड की पहरेदारी करती हैं, और फ़र्मा की लघु प्रमेय संसार के रहस्यों का ताला चलाती है

जी. एच. हार्डी ने 1940 में डींग हाँकी थी कि संख्या-सिद्धांत अनुप्रयोगों से “अछूता” है। अस्सी वर्ष बाद हर बारकोड की बीप, हर क्रेडिट-कार्ड भुगतान और हर गूढ़ संदेश उन्हें झुठला देता है — और वह भी ठीक इसी अध्याय के औज़ारों से: सर्वांगसमताएँ (प्रतिज्ञप्ति 29.5), बेज़ू प्रतिलोम (प्रमेय 29.10) और फ़र्मा की लघु प्रमेय (अभ्यास 29.9)। यह समस्या कूट जाँचती है, ताले का एक खिलौना रूप तोड़ती है, और यह सीखती है कि असली ताला टिकता क्यों है।

भाग I — सर्वांगसमता में प्रवाह।

$2026 \bmod 7$ निकालिए; फिर $7^{100}$ का अंतिम अंक ( $10$ के सापेक्ष $7$ की घातों का चक्र ढूँढ़िए)।
तेज़ घातांकन (विधि 29.6): $5^{117} \bmod 13$ निकालिए ( $5^2 \equiv -1$ से शुरू कीजिए)।
$3x \equiv 5 \pmod 7$ हल कीजिए।
$(97, 35)$ पर यूक्लिड की कलनविधि चलाइए, पीछे प्रतिस्थापन करके ऐसे पूर्णांक $u, v$ ज्ञात कीजिए कि $97u + 35v = 1$ हो, और $97$ के सापेक्ष $35$ का प्रतिलोम निकालिए।
ठीक-ठीक बताइए कि $a$ $n$ के सापेक्ष कब प्रतिलोमनीय है, और प्रतिलोम कौन-सी प्रमेय दे देती है।

भाग II — जाँच-अंक।

ISBN-10: किसी पुस्तक-कूट के दसों अंक $d_1 \dots d_{10}$ $10d_1 + 9d_2 + \dots + 2d_9 + 1d_{10} \equiv 0 \pmod{11}$ को संतुष्ट करने चाहिए। असली ISBN $0\,306\,40615\,2$ की जाँच कीजिए।
सिद्ध कीजिए कि ISBN की योजना हर एक-अंकीय त्रुटि पकड़ लेती है: यदि कोई एक अंक $d \not\equiv 0$ से बदल जाए, तो भारित योग $1 \leq w \leq 10$ वाले $w d$ से बदल जाता है — यह कभी $\equiv 0 \pmod{11}$ क्यों नहीं हो सकता (प्रमेय 29.11)?
सिद्ध कीजिए कि वह दो सटे हुए (भिन्न) अंकों की अदला-बदली भी पकड़ लेती है। फिर रचना का रहस्य समझाइए: $11$ के किस गुण ने दोनों उपपत्तियाँ चलाईं, और मापांक $10$ के साथ क्या गड़बड़ हो सकती थी?
EAN-13 बारकोड अंकों को $10$ के सापेक्ष $1, 3, 1, 3, \dots$ भार देते हैं। $978\,2940199\,05$ को पूरा करने वाला जाँच-अंक निकालिए। EAN किन सटी हुई अदला-बदलियों को पकड़ने में चूक जाता है? ( $2(a - b) \equiv 0 \pmod{10}$ कब होता है?)
क्रेडिट कार्ड लून की योजना काम में लाते हैं: दाईं ओर से हर दूसरे अंक को दुगुना कीजिए (दुगुना $9$ से अधिक हो तो $9$ घटा दीजिए), सब जोड़िए, और $10$ का गुणज माँगिए। जाँच-संख्या $4539\,1488\,0343\,6467$ की परीक्षा कीजिए।
एक वाक्य में: अभाज्य मापांक ने ISBN को क्या दे दिया जो $10$ से बँधे EAN और लून को कभी नहीं मिल सकता?

भाग III — फ़र्मा का ताला।

ख़ज़ाने से पहले एक जाल: $2^{10} \bmod 341$ निकालिए, $2^{340} \bmod 341$ निष्कर्ष निकालिए — और फिर $341$ का गुणनखंडन कीजिए। यह उदाहरण (एक फ़र्मा छद्म-अभाज्य) फ़र्मा की लघु प्रमेय को अभाज्यता की जाँच के रूप में काम में लाने के बारे में क्या कहता है?
लघुरूप में RSA: $p = 3$ , $q = 11$ लीजिए, इसलिए $n = 33$ और $(p-1)(q-1) = 20$ ; सार्वजनिक घातांक $e = 3$ है। ऐसा निजी घातांक $d$ ज्ञात कीजिए कि $3d \equiv 1 \pmod{20}$ हो (प्रश्न 4 की विधि)।
संदेश $m = 4$ गूढ़ कीजिए: $c = m^3 \bmod 33$ निकालिए।
गूढ़वाचन कीजिए: $c^d \bmod 33$ निकालिए ( $c \equiv -2 \pmod{33}$ का उपयोग कीजिए) और संदेश वापस पाइए।
गूढ़वाचन सदा काम क्यों करता है: दिखाइए कि $3$ के सापेक्ष और $11$ के सापेक्ष, दोनों जगह $m^{21} \equiv m$ (हर संसार में फ़र्मा की लघु प्रमेय), और $33$ के सापेक्ष निष्कर्ष निकालिए (प्रमेय 29.11 दोनों सर्वांगसमताओं को जोड़ देता है)। $21 = ed$ का विशेष रूप $1 + 20k$ कहाँ काम आया?
ताले की सुरक्षा: $n$ और $e$ सब जानते हैं; $d$ वापस पाने के लिए $(p-1)(q-1)$ चाहिए, अर्थात् $n$ के गुणनखंड। हमारा $33$ तो देखते ही गुणनखंडित हो जाता है — फिर वही योजना छह सौ अंकों वाले $n$ के साथ संसार के बैंकों की रक्षा कैसे करती है? (गुणा करने और गुणनखंडन करने की विषमता पर एक वाक्य।)

भाग IV — चिरपरिचित।

सैनिकों की पुरानी चीनी गिनती (अभ्यास 29.10 से तुलना कीजिए): सैनिकों की संख्या $3$ की पंक्तियों में लगाने पर शेषफल $2$ और $5$ की पंक्तियों में लगाने पर शेषफल $3$ छोड़ती है। सभी संभव संख्याएँ ज्ञात कीजिए, और समझाइए कि उत्तर $15$ के सापेक्ष अद्वितीय क्यों है।
अंततः एक-पंक्ति की उपपत्तियाँ: $10 \equiv 1 \pmod 9$ से सिद्ध कीजिए कि हर संख्या $9$ के सापेक्ष अपने अंकों के योग के सर्वांगसम होती है; और $10 \equiv -1 \pmod{11}$ से $11$ के लिए एकांतर-योग वाला नियम निकालिए। (माध्यमिक विद्यालय खंड ने इन्हें स्पष्ट बीजगणित से सिद्ध किया था — अब इस संक्षेप की सराहना कीजिए।)
समापन — बारकोड के सामने हार्डी: अध्याय का औज़ार-बक्सा दोहराइए (सर्वांगसमता का अंकगणित, बेज़ू प्रतिलोम, फ़र्मा की लघु प्रमेय, सह-अभाज्य मापांकों को जोड़ना) और बताइए कि इस समस्या में हर औज़ार कहाँ फ़िट बैठा; फिर “अछूता” पर आधुनिक फ़ैसला सुनाइए।

हल

हल — समस्या 29.1.

1. $2026 = 289 \times 7 + 3$ : $2026 \equiv 3 \pmod 7$ । $10$ के सापेक्ष $7$ की घातें: $7, 9, 3, 1$ , जिनका चक्र $4$ लंबा है; $100 \equiv 0 \pmod 4$ : $7^{100}$ का अंतिम अंक $1$ है।

2. $5^2 = 25 \equiv -1 \pmod{13}$ , इसलिए $5^{116} = \left(5^2\right)^{58} \equiv (-1)^{58} = 1$ और $5^{117} \equiv 5 \pmod{13}$ ।

3. $7$ के सापेक्ष $3$ का प्रतिलोम $5$ है ( $15 \equiv 1$ ): $x \equiv 5 \times 5 = 25 \equiv 4 \pmod 7$ ।

4. $97 = 2 \times 35 + 27$ ; $35 = 27 + 8$ ; $27 = 3 \times 8 + 3$ ; $8 = 2 \times 3 + 2$ ; $3 = 2 + 1$ । पीछे प्रतिस्थापन करने पर: $1 = 97 \times 13 + 35 \times (-36)$ । इसलिए $35 \times (-36) \equiv 1 \pmod{97}$ : $35$ का प्रतिलोम $-36 \equiv 61 \pmod{97}$ है।

5. $a$ $n$ के सापेक्ष ठीक तब प्रतिलोमनीय है जब $\gcd(a, n) = 1$ हो: बेज़ू $au + nv = 1$ दे देते हैं, अर्थात् $au \equiv 1$ ; और इसके उलट किसी प्रतिलोम के होने से महत्तम समापवर्तक को $1$ विभाजित करना ही पड़ता है।

6. $0{\cdot}10 + 3{\cdot}9 + 0{\cdot}8 + 6{\cdot}7 + 4{\cdot}6 + 0{\cdot}5 + 6{\cdot}4 + 1{\cdot}3 + 5{\cdot}2 + 2{\cdot}1 = 132 = 12 \times 11 \equiv 0 \pmod{11}$ : वैध।

7. योग $1 \leq w \leq 10$ और $1 \leq \abs d \leq 9$ वाले $wd$ से बदल जाता है: चूँकि $11$ अभाज्य है और किसी भी गुणनखंड को विभाजित नहीं करता, इसलिए वह गुणनफल को भी विभाजित नहीं कर सकता (प्रमेय 29.11 / प्रतिज्ञप्ति 29.14): बदला हुआ योग फिर कभी $\equiv 0$ नहीं होता: हर एक-अंकीय त्रुटि पर ख़तरे की घंटी बज जाती है।

8. सटे हुए अंकों $a, b$ (भार $w + 1, w$ ) की अदला-बदली योग को $a \neq b$ वाले $(w+1)b + wa - (w+1)a - wb = b - a \not\equiv 0$ से बदल देती है: पकड़ी गई। रहस्य $11$ की अभाज्यता है: $10$ के सापेक्ष $5 \times 2$ जैसे गुणनफल बिना किसी गुणनखंड के शून्य हुए लुप्त हो जाते हैं, इसलिए $\pm 2$ की भार- $5$ वाली त्रुटि (या कोई अभागी अदला-बदली) छिपकर निकल सकती थी।

9. बारहों अंकों का भारित योग: $119$ ; जाँच-अंक को उसे $10$ के गुणज तक पूरा करना है: $1$ (पूरा कूट $978\,2940199\,051$ )। EAN उन सटी हुई अदला-बदलियों में चूक जाता है जहाँ $2(a - b) \equiv 0 \pmod{10}$ , अर्थात् $\abs{a - b} = 5$ : मान लीजिए $2$ और $7$ की अदला-बदली बिना पकड़ में आए निकल जाती है — यही मिलनसार मापांक $10$ की क़ीमत है।

10. दाईं ओर से हर दूसरा अंक दुगुना करके और मोड़कर ( $16 \to 7$ इत्यादि) योग $80 \equiv 0 \pmod{10}$ बनता है: जाँच-कार्ड वैध निकलता है।

11. अभाज्य मापांक के साथ हर भार प्रतिलोमनीय होता है, इसलिए सारी एकल त्रुटियाँ और सारी सटी हुई अदला-बदलियाँ पकड़ में आ जाती हैं — यही ISBN की विलासिता है; $10$ वाले मापांक की योजनाएँ मनुष्य के मित्रवत अंक बनाए रखती हैं और बदले में एक छोटा-सा अंधा कोना स्वीकार कर लेती हैं।

12. $2^{10} = 1024 = 3 \times 341 + 1 \equiv 1 \pmod{341}$ , अतः $2^{340} = \left(2^{10}\right)^{34} \equiv 1$ । फिर भी $341 = 11 \times 31$ भाज्य है: वह आधार $2$ पर फ़र्मा की परीक्षा पास कर लेता है और फिर भी अभाज्य नहीं है। सीख: फ़र्मा की सर्वांगसमता आवश्यक है, पर्याप्त नहीं — अभाज्यता की जाँच को और पैने औज़ार चाहिए (और वे उसे स्नातक खंडों में मिलते भी हैं)।

13. $3d \equiv 1 \pmod{20}$ : $d = 7$ ( $21 = 20 + 1$ )।

14. $c = 4^3 = 64 \equiv 31 \pmod{33}$ ।

15. $31 \equiv -2$ : $(-2)^7 = -128$ , और $-128 + 4 \times 33 = 4$ : गूढ़ पाठ का गूढ़वाचन $m = 4$ देता है। ताला घूम जाता है।

16. $3$ के सापेक्ष: यदि $3 \nmid m$ हो, तो $m^2 \equiv 1$ (फ़र्मा), इसलिए $m^{21} = m \cdot \left(m^2\right)^{10} \equiv m$ ; और यदि $3 \mid m$ हो, तो दोनों पक्ष $\equiv 0$ हैं। $11$ के सापेक्ष: $m^{10} \equiv 1$ या $11 \mid m$ , और $m^{21} = m \cdot \left(m^{10}\right)^2 \equiv m$ । $3$ और $11$ दोनों $m^{21} - m$ को विभाजित करते हैं, और सह-अभाज्य होने के कारण उनका गुणनफल $33$ भी (गाउस): $m^{21} \equiv m \pmod{33}$ । घातांक $ed = 21 = 1 + 20k$ ऐसा गढ़ा गया था कि दोनों फ़र्मा-घातांक ( $2$ और $10$ , जो $20$ को विभाजित करते हैं) ग़ायब हो जाएँ।

17. $300$ अंकों के दो अभाज्यों को गुणा करने में माइक्रोसेकंड लगता है; पर उनके गुणनफल से उन्हें वापस पाना हर ज्ञात कलनविधि और संसार के सारे संगणकों को हरा देता है — ताला एकतरफ़ा गली है। (हमारा $n = 33$ वही गली खिलौने के पैमाने पर है, जो दोनों दिशाओं में चलने लायक़ है।)

18. शेषफल आज़माने से (या बेज़ू से बनाकर): $n \equiv 8 \pmod{15}$ : गिनतियाँ $8, 23, 38, 53, \dots$ । $15$ के सापेक्ष अद्वितीयता: दो हल $3$ के और $5$ के गुणज से भिन्न होते हैं, अतः $15$ के भी ( $3$ और $5$ सह-अभाज्य, गाउस)। $1000$ सैनिकों वाला सेनापति तीन झटपट क़तारों से “ $8$ ” घोषित कर देता है — यही प्राचीन सिर-गिनती की तरकीब है।

19. $10 \equiv 1 \pmod 9$ से $10^k \equiv 1$ मिलता है, इसलिए $\sum d_k 10^k \equiv \sum d_k$ : कोई संख्या और उसके अंकों का योग $9$ के सापेक्ष (और $3$ के सापेक्ष भी) सर्वांगसम होते हैं। और $10 \equiv -1 \pmod{11}$ से $\sum d_k 10^k \equiv \sum (-1)^k d_k$ मिलता है: यानी एकांतर वाला नियम। बचपन के दो नियम, एक-एक पंक्ति में।

20. सर्वांगसमताओं ने शेषफलों को एक अंकगणित बना दिया (भाग I); बेज़ू ने वे प्रतिलोम ढाले जो रैखिक सर्वांगसमताएँ और RSA का $d$ हल कर देते हैं (प्रश्न 4, 13); फ़र्मा की लघु प्रमेय ने ताला खोला और बंद किया (प्रश्न 15–16); और सह-अभाज्य मापांकों को जोड़ने ने सैनिक गिने तथा उपपत्ति पूरी की (प्रश्न 16, 18)। हार्डी पर फ़ैसला: उन्हें ज्ञात सबसे शुद्ध प्रमेय आज हर ख़रीद की पहरेदारी करती है — समय मिल जाए तो शुद्धता ही सबसे अधिक अनुप्रयोग योग्य वस्तु है।

इस अध्याय में परिभाषित शब्द

शब्दावली के सभी 395 शब्द देखें