विश्वविद्यालय गणित — स्नातक वर्ष 1 · Bachelor Year 1

6पूर्णांक अंकगणित

अंकगणित — $\Z$ में विभाज्यता का अध्ययन — उच्चतर माध्यमिक खंड में आरंभ हुआ था। यह अध्याय उसे यूक्लिडीय भाग से पूरी उपपत्तियों के साथ नए सिरे से खड़ा करता है: महत्तम समापवर्तक और यूक्लिडीय कलनविधि, बेज़ू सर्वसमिका और गाउस की प्रमेयिका, अभाज्य गुणनखंडन, तथा फर्मा की लघु प्रमेय तक सर्वांगसमताओं का कलन। अपने आकर्षण से आगे, यह सामग्री वह आदर्श है जिसका अनुकरण अध्याय 8 बहुपदों के लिए करता है।

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

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

$a, b \in \Z$ के लिए, $b$ $a$ को विभाजित करता है (लिखा जाता है $b \mid a$ ) जब किसी $q \in \Z$ के लिए $a = bq$ हो। मूल परिणाम: यदि $b \mid a$ और $b \mid a'$ , तो सभी $u, v \in \Z$ के लिए $b \mid (ua + va')$ ; यदि $b \mid a$ और $a \neq 0$ , तो $\abs b \leq \abs a$ ; और $a \mid b$ तथा $b \mid a$ साथ मिलकर $b = \pm a$ पर बाध्य कर देते हैं।

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

सभी $a \in \Z$ और $b \in \N^*$ के लिए ठीक एक युग्म $(q, r) \in \Z \times \N$ ऐसा है कि

a = bq + r, \qquad 0 \leq r < b .

उपपत्ति. अस्तित्व। समुच्चय $A = \{a - bk : k \in \Z\} \cap \N$ $\N$ का अरिक्त उपसमुच्चय है ( $k = -\abs a$ लीजिए: $a + b\abs a \geq a + \abs a \geq 0$ )। मान लीजिए $r = a - bq$ उसका न्यूनतम अवयव है। यदि $r \geq b$ , तो $r - b = a - 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$ का गुणज $0$ होना ही चाहिए, अतः $q = q'$ और $r = r'$ । ∎

उदाहरण 6.3 (बार-बार भाग देकर स्थानीय मान पद्धति)

$2026$ को आधार $7$ में लिखिए। $7$ से बार-बार भाग दीजिए और शेषफल रखते जाइए:

2026 = 7 \times 289 + 3, \quad 289 = 7 \times 41 + 2, \quad 41 = 7 \times 5 + 6, \quad 5 = 7 \times 0 + 5 .

शेषफलों को अंतिम से पहले तक पढ़िए: $2026 = (5\,6\,2\,3)_7$ । जाँच: $5 \times 343 + 6 \times 49 + 2 \times 7 + 3 = 1715 + 294 + 14 + 3 = 2026$ । यूक्लिडीय भाग की अद्वितीयता ही हर अंक को अनिवार्य बनाती है: हर पद पर शेषफल $\intint06$ का एकमात्र ऐसा पूर्णांक है जो वर्तमान मान के $7$ के सापेक्ष सर्वांगसम हो, अतः आधार- $7$ लेखन अद्वितीय है — यही तथ्य चुपचाप तब प्रयुक्त होता है जब सप्ताहांत समस्या “आधार $p$ में $n$ के अंकों” को साधती है।

6.2 महत्तम समापवर्तक

प्रमेय 6.4 ( $\Z$ के उपसमूह; महत्तम समापवर्तक का अस्तित्व)

$(\Z, +)$ का प्रत्येक उपसमूह किसी अद्वितीय $n \in \N$ के लिए $n\Z = \{nk : k \in \Z\}$ रूप का है।
जो $a, b \in \Z$ दोनों शून्य न हों, उनके लिए समुच्चय $a\Z + b\Z = \{au + bv : u, v \in \Z\}$ $\Z$ का उपसमूह है, अतः किसी अद्वितीय $d \in \N^*$ के लिए $d\,\Z$ के बराबर है। यही $d$ महत्तम समापवर्तक $\gcd(a, b)$ है: वह $a$ और $b$ को विभाजित करता है, और $a$ तथा $b$ का प्रत्येक उभयनिष्ठ भाजक $d$ को विभाजित करता है।

उपपत्ति. (1) मान लीजिए $H \subseteq \Z$ उपसमूह है (अरिक्त, घटाव के अंतर्गत स्थायी; औपचारिक परिभाषा अध्याय 7 में है, और केवल यही दो गुणधर्म प्रयुक्त होते हैं)। यदि $H = \{0\}$ , तो $n = 0$ लीजिए। अन्यथा $H$ में कोई अशून्य अवयव और उसका विपरीत भी है, अतः उसमें एक लघुतम पूर्णतः धनात्मक अवयव $n$ है। तब $n\Z \subseteq H$ । $x \in H$ के लिए $0 \leq r < n$ (प्रमेय 6.2) के साथ $x = nq + r$ लिखिए; $r = x - nq \in H$ , और $n$ की लघुतमता $r = 0$ पर बाध्य कर देती है: $x \in n\Z$ । अद्वितीयता: $n$ $n\Z$ का न्यूनतम धनात्मक अवयव है।

(2) $a\Z + b\Z$ में $0$ है और वह घटाव के अंतर्गत स्थायी है, अतः वह $d \geq 1$ के साथ $d\Z$ है (उसमें $a$ या $b$ अशून्य है)। चूँकि $a, b \in d\Z$ , $d$ दोनों को विभाजित करता है। और यदि $c$ $a$ तथा $b$ को विभाजित करता है, तो $c$ प्रत्येक $au + bv$ को विभाजित करता है — विशेष रूप से $c \mid d$ को, क्योंकि $d \in a\Z + b\Z$ । यही घोषित गुणधर्म है (और इससे $\abs c \leq d$ निकलता है, अतः $d$ महत्तम समापवर्तक कहलाने का अधिकारी है)। ∎

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

जो $a, b$ दोनों शून्य न हों, उनके लिए ऐसे $u, v \in \Z$ विद्यमान हैं कि

au + bv = \gcd(a, b) .

विशेष रूप से ( $\gcd(a,b) = 1$ , अर्थात् सहअभाज्य स्थिति): $a$ और $b$ सहअभाज्य हैं यदि और केवल यदि $au + bv = 1$ का कोई हल हो।

उपपत्ति. $\gcd(a,b) = d \in d\Z = a\Z + b\Z$ । तुल्यता के लिए: यदि $\gcd(a,b) = 1$ , तो बेज़ू हल दे देता है; विलोमतः $au + bv = 1$ $a, b$ के प्रत्येक उभयनिष्ठ भाजक को $1$ विभाजित करने पर बाध्य कर देता है। ∎

विधि 6.6 (यूक्लिडीय कलनविधि, विस्तारित)

$\gcd(a, b)$ ( $a > b > 0$ ) संगणित करने के लिए: $a = bq + r$ का भाग दीजिए; फिर $\gcd(a, b) = \gcd(b, r)$ ( $(a,b)$ और $(b,r)$ के उभयनिष्ठ भाजक एक ही हैं, क्योंकि $r = a - bq$ ); शेषफल $0$ होने तक दोहराइए; अंतिम अशून्य शेषफल ही महत्तम समापवर्तक है। भागों को उलटी दिशा में चलाने से (या नीचे उतरते समय गुणांक बनाए रखने से) एक बेज़ू युग्म $(u, v)$ मिल जाता है।

उदाहरण 6.7

$\gcd(120, 23)$ : $120 = 5 \times 23 + 5$ ; $23 = 4 \times 5 + 3$ ; $5 = 1\times 3 + 2$ ; $3 = 1 \times 2 + 1$ ; $2 = 2 \times 1 + 0$ । अतः $\gcd = 1$ । उलटी दिशा में:

\begin{align*} 1 &= 3 - 2 = 3 - (5 - 3) = 2\times 3 - 5 = 2(23 - 4\times 5) - 5 \\ &= 2 \times 23 - 9 \times 5 = 2\times 23 - 9(120 - 5\times 23) = 47 \times 23 - 9 \times 120 . \end{align*}

जाँच: $47 \times 23 = 1081$ , $9 \times 120 = 1080$ ।

प्रमेय 6.8 (गाउस की प्रमेयिका और उसके परिणाम)

मान लीजिए $a, b, c \in \Z$ ।

(गाउस की प्रमेयिका) यदि $a \mid bc$ और $\gcd(a, b) = 1$ , तो $a \mid c$ ।
यदि $a \mid c$ , $b \mid c$ और $\gcd(a,b) = 1$ , तो $ab \mid c$ ।
यदि $\gcd(a, b) = \gcd(a, c) = 1$ , तो $\gcd(a, bc) = 1$ ।

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

(2) $c = aq$ लिखिए; $b \mid aq$ और $\gcd(a, b) = 1$ से, बिंदु (1) $b \mid q$ देता है, अतः $ab \mid aq = c$ ।

(3) $au + bv = 1$ और $au' + cv' = 1$ । दोनों संबंधों को गुणा कीजिए:

1 = (au + bv)(au' + cv') = a\,\bigl(auu' + ucv' + u'bv\bigr) + bc\,(vv') ,

जो $a$ और $bc$ के बीच एक बेज़ू संबंध है: उपप्रमेय 6.5 से $\gcd(a, bc) = 1$ । ∎

उदाहरण 6.9 (एक रैखिक डायोफैंटीय समीकरण हल करना)

$6x + 10y = 4$ वाले सभी $(x, y) \in \Z^2$ खोजिए। पहले अस्तित्व की जाँच: $\gcd(6, 10) = 2$ $4$ को विभाजित करता है, अतः हल विद्यमान हैं (यदि महत्तम समापवर्तक दाएँ पक्ष को विभाजित न करता, तो बायाँ पक्ष सदा उसका गुणज होता और कोई हल न होता)। पूरे समीकरण को भाग दीजिए: $3x + 5y = 2$ । एक विशिष्ट हल दिखाई देता है: $(x_0, y_0) = (-1, 1)$ । व्यापक हल के लिए घटाइए: $3(x + 1) = -5(y - 1)$ , अतः $3 \mid 5(y-1)$ , और गाउस की प्रमेयिका ( $\gcd(3,5) = 1$ ) $3 \mid y - 1$ देती है: $y = 1 - 3k$ , फिर $x = -1 + 5k$ । विलोमतः ऐसा हर युग्म काम करता है:

(x, y) = (-1 + 5k,\ 1 - 3k), \qquad k \in \Z .

यह प्रतिरूप सामान्य है: एक विशिष्ट हल, और उसके साथ $\bigl(\frac b{\gcd}, -\frac a{\gcd}\bigr)$ के पूर्णांक गुणज — वही “विशिष्ट और समांगी” संरचना जो अध्याय 5 में है, जहाँ अद्वितीयता की भूमिका गाउस की प्रमेयिका निभाती है।

परिभाषा 6.10 (लघुत्तम समापवर्त्य)

$\operatorname{lcm}(a, b)$ उपसमूह $a\Z \cap b\Z$ का $\N$ में जनक है: वह $a$ और $b$ का ऐसा उभयनिष्ठ गुणज है जो प्रत्येक उभयनिष्ठ गुणज को विभाजित करता है, और $a, b \in \N^*$ के लिए

\gcd(a,b) \times \operatorname{lcm}(a,b) = ab \qquad (\text{उपपत्ति } \text{अभ्यास 6.5}).

उदाहरण 6.11 (संरेखण की समस्याएँ लघुत्तम समापवर्त्य की समस्याएँ हैं)

दो जुड़े हुए दंतचक्रों के $84$ और $36$ दाँते हैं। कितने दाँतों की उभयनिष्ठ गति के बाद वे साथ-साथ अपनी आरंभिक स्थिति में लौटते हैं? विन्यास तब दोहराता है जब बीते हुए दाँतों की संख्या $84$ और $36$ का उभयनिष्ठ गुणज हो; पहली बार यह

\operatorname{lcm}(84, 36) = \frac{84 \times 36}{\gcd(84, 36)} = \frac{3024}{12} = 252

दाँतों पर होता है — अर्थात् बड़े दंतचक्र के $3$ और छोटे के $7$ चक्कर ( $252/84$ और $252/36$ )। व्यावहारिक मार्ग पर ध्यान दीजिए: पहले महत्तम समापवर्तक संगणित कीजिए (यूक्लिड: $84 = 2\times36 + 12$ , $36 = 3\times12$ ), फिर भाग दीजिए — गुणजों की सूची बनाकर लघुत्तम समापवर्त्य कभी मत बनाइए। आवर्ती संपात का हर प्रश्न (दंतचक्र, ग्रहों का संरेखण, आवर्ती दशमलवों का मिलना) इसी एक संगणना पर सिमट जाता है।

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

परिभाषा 6.12

पूर्णांक $p \geq 2$ अभाज्य तब कहलाता है जब उसके एकमात्र धनात्मक भाजक $1$ और $p$ हों। अभाज्य $p$ और $a \in \Z$ के लिए: या तो $p \mid a$ , या $\gcd(p, a) = 1$ । फलस्वरूप (प्रमेय 6.8) यूक्लिड की प्रमेयिका सत्य है: यदि $p \mid ab$ , तो $p \mid a$ या $p \mid b$ ।

टिप्पणी 6.13 (भाग देकर अभाज्यता की जाँच)

यदि $2 \leq a \leq b$ के साथ $n = ab$ , तो $a^2 \leq ab = n$ , अतः $a \leq \sqrt n$ : किसी भाज्य $n$ का सदा कोई अभाज्य भाजक $\leq \sqrt n$ होता है। अतः यह जाँचने के लिए कि $n$ अभाज्य है या नहीं, $\sqrt n$ तक के अभाज्य आज़मा लेना पर्याप्त है। $n = 271$ के लिए: $\sqrt{271} < 17$ , और $271$ $2, 3, 5, 7, 11, 13$ में से किसी से विभाज्य नहीं है (विषम, अंकों का योग $10$ , अंत में $0$ या $5$ नहीं, $271 = 7\cdot38 + 5 = 11\cdot24 + 7 = 13\cdot20 + 11$ ): अतः अभाज्य, और वह भी दो सौ के बदले छह भागों में। $\sqrt n$ की बाधा एक सच्ची देहली है: सौ अंकों वाली संख्याओं के लिए उसे कुशलता से पार करने के लिए वे आधुनिक अभाज्यता-परीक्षण चाहिए जो प्रमेय 6.23 से उपजे हैं।

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

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

उपपत्ति. प्रत्येक पूर्णांक $n \geq 2$ का कोई अभाज्य भाजक है: उसका लघुतम भाजक $\geq 2$ अभाज्य है (उसका उचित गुणनखंडन $n$ का उससे छोटा भाजक दे देता)। अब मान लीजिए $p_1, \dots, p_k$ ही सारे अभाज्य हैं, और $N = p_1 p_2 \cdots p_k + 1 \geq 2$ रखिए। कोई अभाज्य $p_i$ $N$ को विभाजित करता है; पर $p_i$ $N - 1 = p_1\cdots p_k$ को भी विभाजित करता है, अतः $p_i \mid 1$ — असंगत। ∎

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

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

n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k} \qquad (p_1 < p_2 < \dots < p_k \text{ अभाज्य},\ \alpha_i \in \N^*)

अद्वितीय है।

उपपत्ति. अस्तित्व प्रबल आगमन (प्रमेय 1.12) से: $n = 2$ अभाज्य है; $n > 2$ के लिए या तो $n$ अभाज्य है, या $2 \leq a, b < n$ के साथ $n = ab$ , और आगमन परिकल्पना $a$ तथा $b$ का गुणनखंडन कर देती है।

अद्वितीयता। मान लीजिए $p_1 \cdots p_r = q_1 \cdots q_s$ (अभाज्य पुनरावृत्ति सहित सूचीबद्ध, मान लीजिए $r \leq s$ ), और $r$ पर आगमन कीजिए। यदि $r = 0$ , तो बायाँ पक्ष $1$ है, जो $s = 0$ पर बाध्य कर देता है (अभाज्यों का अरिक्त गुणनफल $1$ से बड़ा होता है)। $r \geq 1$ के लिए: अभाज्य $p_1$ $q_1(q_2\cdots q_s)$ को विभाजित करता है, अतः यूक्लिड की प्रमेयिका से या तो $p_1 \mid q_1$ या $p_1 \mid q_2\cdots q_s$ ; दोहराने पर $p_1$ किसी $q_j$ को विभाजित करता है। पर $q_j$ अभाज्य है और $p_1 \geq 2$ : अनिवार्यतः $p_1 = q_j$ । इस उभयनिष्ठ गुणनखंड को काट दीजिए (यह वैध है: $\Z$ पूर्णांकीय प्रांत है), जिससे मिलता है

p_2 \cdots p_r = q_1 \cdots \widehat{q_j} \cdots q_s

(टोपी का चिह्न लोप दर्शाता है), जो छोटे गुणनफलों की समता है; आगमन परिकल्पना कहती है कि दोनों सूचियाँ $p_2, \dots, p_r$ और $q_1, \dots, \widehat{q_j}, \dots, q_s$ क्रम तक मेल खाती हैं, अतः मूल सूचियाँ भी मेल खाती थीं। घातांक वाला रूप समान अभाज्यों को समूहबद्ध कर देता है। ∎

प्रतिज्ञप्ति 6.16 (मूल्यांकन)

अभाज्य $p$ और $n \in \N^*$ के लिए $n$ के गुणनखंडन में $p$ के घातांक को $v_p(n)$ लिखिए (जहाँ $p \nmid n$ होने पर $v_p(n) = 0$ )। तब

v_p(mn) = v_p(m) + v_p(n), \qquad m \mid n \iff \forall p,\ v_p(m) \leq v_p(n),

v_p\bigl(\gcd(m,n)\bigr) = \min\bigl(v_p(m), v_p(n)\bigr), \qquad v_p\bigl(\operatorname{lcm}(m,n)\bigr) = \max\bigl(v_p(m), v_p(n)\bigr).

उपपत्ति. पहली सर्वसमिका इसलिए सत्य है कि गुणनखंडन गुणित होते हैं और $mn$ का गुणनखंडन अद्वितीय है। यदि $m \mid n$ , तो $n = mq$ लिखिए और इसे लगाइए। विलोमतः, यदि सभी $v_p(m) \leq v_p(n)$ , तो पूर्णांक $q = \prod_p p^{\,v_p(n) - v_p(m)}$ $mq = n$ को संतुष्ट करता है। महत्तम समापवर्तक का सूत्र: कसौटी से पूर्णांक $d = \prod p^{\min}$ दोनों को विभाजित करता है, और प्रत्येक उभयनिष्ठ भाजक $c$ के लिए सभी $p$ पर $v_p(c) \leq \min$ , अतः $c \mid d$ ; लघुत्तम समापवर्त्य के लिए $\max$ के साथ वही तर्क। ∎

उदाहरण 6.17 (मूल्यांकनों से वर्ग और घन)

पूर्णांक $n \geq 1$ पूर्ण वर्ग है यदि और केवल यदि प्रत्येक $v_p(n)$ सम हो (यदि $n = m^2$ , तो $v_p(n) = 2v_p(m)$ ; विलोमतः प्रत्येक घातांक को आधा कीजिए)। घनों के लिए भी वही, $3$ के गुणजों के साथ। अतः $21168 = 2^4 \times 3^3 \times 7^2$ न वर्ग है ( $v_3 = 3$ विषम है) और न घन ( $v_2 = 4$ ); ऐसा लघुतम धनात्मक पूर्णांक $m$ कि $21168\,m$ घन हो, प्रत्येक घातांक को $3$ के अगले गुणज तक भरकर मिलता है:

m = 2^{6-4} \times 3^{3-3} \times 7^{3-2} = 2^2 \times 7 = 28, \qquad 21168 \times 28 = 2^6\,3^3\,7^3 = (2^2 \times 3 \times 7)^3 = 84^3 .

सार: गुणात्मक प्रश्न (वर्ग, घन, भाजक, महत्तम समापवर्तक, लघुत्तम समापवर्त्य) घातांक सदिशों $(v_2, v_3, v_5, \dots)$ पर निर्देशांक-दर-निर्देशांक प्रश्न बन जाते हैं — और अद्वितीय गुणनखंडन ठीक यही कथन है कि ये निर्देशांक विद्यमान और सुपरिभाषित हैं।

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

परिभाषा 6.18

$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.20 ( $n$ के सापेक्ष व्युत्क्रमणीयता)

$a$ $n$ के सापेक्ष व्युत्क्रमणीय है (अर्थात् किसी $b$ के लिए $ab \equiv 1 \pmod n$ ) यदि और केवल यदि $\gcd(a, n) = 1$ । तब प्रतिलोम $n$ के सापेक्ष अद्वितीय होता है और विस्तारित यूक्लिडीय कलनविधि से संगणित होता है।

उपपत्ति. $ab \equiv 1 \pmod n$ का अर्थ है कि किसी $k$ के लिए $ab + nk = 1$ : यह एक बेज़ू संबंध है, जो तभी विद्यमान है जब $\gcd(a,n) = 1$ (उपप्रमेय 6.5)। अद्वितीयता: यदि $ab \equiv ab' \equiv 1$ , तो $b \equiv b(ab') = (ab)b' \equiv b' \pmod n$ । ∎

उदाहरण 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)$ हल-वर्ग होते हैं — सब कुछ महत्तम समापवर्तक से भाग दीजिए और प्रतिलोम लीजिए।

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

मान लीजिए $p$ अभाज्य है। प्रत्येक $a \in \Z$ के लिए:

a^p \equiv a \pmod p,

और यदि $p \nmid a$ , तो $a^{p-1} \equiv 1 \pmod p$ ।

उपपत्ति. पहले, $1 \leq k \leq p - 1$ के लिए द्विपद गुणांक $\binom pk = \frac{p!}{k!(p-k)!}$ $p$ से विभाज्य है: वस्तुतः $k!\,(p-k)!\, \binom pk = p!$ और $p$ $p!$ को विभाजित करता है पर $k!(p-k)!$ से सहअभाज्य है (सभी गुणनखंड $< p$ हैं), अतः गाउस की प्रमेयिका $p \mid \binom pk$ देती है।

अब $a \in \N$ के लिए $a^p \equiv a$ आगमन से सिद्ध कीजिए। $a = 0$ के लिए सत्य। यदि $a^p \equiv a$ , तो द्विपद प्रमेय से

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

जहाँ बीच के सभी पद $p$ के सापेक्ष लुप्त हो जाते हैं। $a < 0$ के लिए परिणाम को $-a$ पर लगाइए और $p = 2$ (जहाँ $x \equiv -x$ ) को विषम $p$ (जहाँ $(-a)^p = -a^p$ ) से अलग कीजिए। अंत में, यदि $p \nmid a$ , तो $a^p \equiv a$ को $p$ के सापेक्ष $a$ के प्रतिलोम से गुणा कीजिए (प्रतिज्ञप्ति 6.20)। ∎

उदाहरण 6.24 (फर्मा का विलोम विफल है: $341$ )

फर्मा की लघु प्रमेय एक सस्ता भाज्यता परीक्षण देती है: यदि $n$ से सहअभाज्य किसी $a$ के लिए $a^{n-1} \not\equiv 1 \pmod n$ , तो $n$ अभाज्य नहीं है। क्या यह परीक्षण अभाज्यता प्रमाणित भी कर सकता है? नहीं: $n = 341 = 11 \times 31$ , जो भाज्य है, और $a = 2$ लीजिए। चूँकि $2^{10} = 1024 = 3 \times 341 + 1$ ,

2^{10} \equiv 1 \pmod{341} \qquad\Longrightarrow\qquad 2^{340} = \bigl(2^{10}\bigr)^{34} \equiv 1 \pmod{341} :

भाज्य $341$ आधार $2$ के लिए फर्मा-परीक्षण पास कर जाता है (वह लघुतम ऐसा छद्म-अभाज्य है)। आधार $3$ उसका मुखौटा उतार देता है ( $3^{340} \not\equiv 1$ ), और इसीलिए व्यावहारिक अभाज्यता-परीक्षण अनेक आधारों पर परीक्षण चलाते हैं, कुछ परिष्करणों के साथ — इसी विचार के औद्योगिक रूप ही टिप्पणी 6.27 के बड़े अभाज्यों को प्रमाणित करते हैं। उपदेश: निहितार्थ और उसका विलोम अलग-अलग जीवन जीते हैं (टिप्पणी 1.10), प्रमेयों के लिए भी।

उदाहरण 6.25 (व्यावहारिक सर्वांगसमता संगणनाएँ)

$11$ के सापेक्ष $7^{2026}$ का शेषफल क्या है? फर्मा से $7^{10} \equiv 1 \pmod{11}$ । चूँकि $2026 = 10 \times 202 + 6$ :

7^{2026} \equiv 7^6 = (7^2)^3 = 49^3 \equiv 5^3 = 125 \equiv 4 \pmod{11}.

शेषफल $4$ है। रणनीति: फर्मा से मिली कोटि के सापेक्ष घातांक घटाइए, फिर हर पद पर बीच की घातें भी घटाते जाइए।

टिप्पणी 6.26 (अंकगणित की सामान्य भूलें)

सर्वांगसमता में भाग देना। $ac \equiv bc \pmod n$ से $a \equiv b$ तब तक नहीं निकाला जा सकता जब तक $\gcd(c, n) = 1$ न हो: $6 \equiv 2 \pmod 4$ , पर $3 \not\equiv 1 \pmod 4$ । सही व्यापक नियम मापांक को भी भाग देता है: $ac \equiv bc \pmod n \iff a \equiv b \pmod{n/\gcd(c,n)}$ ।
यूक्लिड की प्रमेयिका का दुरुपयोग। $a \mid bc$ से $a \mid b$ या $a \mid c$ केवल तभी निकलता है जब $a$ अभाज्य हो (या किसी एक गुणनखंड से सहअभाज्य): $6 \mid 4 \times 9$ , फिर भी $6$ किसी भी गुणनखंड को विभाजित नहीं करता।
सहअभाज्य होना संबंध है, गुणधर्म नहीं। “ $8$ और $9$ सहअभाज्य हैं” सत्य है, यद्यपि इनमें से कोई अभाज्य नहीं है; “जोड़ों में सहअभाज्य” “समग्र रूप से सहअभाज्य” से प्रबल है ( $\gcd(6, 10, 15) = 1$ , पर कोई युग्म सहअभाज्य नहीं)।
घातांक $n$ के सापेक्ष नहीं रहते। $a^k \bmod n$ में घातांक केवल $a$ की कोटि के सापेक्ष घटाया जा सकता है (उदाहरणार्थ $p - 1$ , जब फर्मा लागू हो), कभी $n$ के सापेक्ष नहीं: $2^{10} \bmod 11$ $1$ है, $2^{10 \bmod 11} = 2^{10}$ नहीं — जो घटाव काम करता है वह उदाहरण 6.25 वाला है।

टिप्पणी 6.27 (यह अध्याय कहाँ काम आता है)

यह अध्याय जितना औज़ार-संदूक है उतना ही एक आदर्श भी। पूरी शृंखला — यूक्लिडीय भाग, महत्तम समापवर्तक, बेज़ू, गाउस, अद्वितीय गुणनखंडन — अध्याय 8 में बहुपदों के लिए अक्षरशः दोहराई जाती है, जहाँ निरपेक्ष मान की भूमिका “घात” निभाती है; दोनों अध्यायों को साथ-साथ रखकर देखना दोनों को समझने का सर्वोत्तम उपाय है। सर्वांगसमताओं का कलन अध्याय 7 में वलय $\Z/n\Z$ बन जाता है, जिसके व्युत्क्रमणीय अवयव (प्रतिज्ञप्ति 6.20) इकाई-समूह का पहला अतुच्छ उदाहरण बनाते हैं। मूल्यांकन नीचे दी गई सप्ताहांत समस्या में (लजांद्र का सूत्र) लौटते हैं और अध्याय 10 की अपरिमेयता की उपपत्तियों को शक्ति देते हैं। इस खंड से आगे, $n$ के सापेक्ष बेज़ू प्रतिलोमन सार्वजनिक-कुंजी गूढ़लेखन का इंजन है, और फर्मा की लघु प्रमेय उन अभाज्यता परीक्षणों की पितामही है जो वहाँ प्रयुक्त बड़े अभाज्यों को प्रमाणित करते हैं।

टिप्पणी 6.28 (मध्यांतर: $\Z$ एक आदर्श के रूप में)

अलग-अलग प्रमेयों से पीछे हटकर इस अध्याय की वास्तुकला देखिए: एक औज़ार (यूक्लिडीय भाग) ने एक वर्गीकरण ( $n\Z$ उपसमूह) दिया, उसने एक अस्तित्व प्रमेय (महत्तम समापवर्तक, बेज़ू) दी, उसने एक विभाज्यता-कलन (गाउस) दिया, और उसने अद्वितीय गुणनखंडन — हर मंज़िल केवल अपने नीचे वाली पर टिकी हुई। यही भवन इस खंड में दो बार और, भिन्न भूतलों पर, खड़ा किया जाएगा: अध्याय 8 में, जहाँ आकार से भाग की जगह घात से भाग आ जाता है और ऊपर का सब कुछ अक्षरशः दोहराता है; और लघु रूप में अध्याय 7 के हर $\Z/n\Z$ के भीतर, जहाँ व्युत्क्रमणीयता के प्रश्न (इस अध्याय के प्रतिज्ञप्ति 6.20) वलयों और क्षेत्रों के विषय में संरचनात्मक कथन बन जाते हैं। किसी तर्क को “ $\Z$ -वाला तर्क, प्रतिरोपित” के रूप में पहचान लेना उन अध्यायों को सीखने का सबसे तेज़ उपाय है — और बीजगणित की मूल आदत का पहला स्वाद, अर्थात् वस्तुओं के बदले अभिगृहीतों के विषय में प्रमेय सिद्ध करना।

पास्कल त्रिभुज की 0 से 7 तक की पंक्तियाँ, जिनमें विषम प्रविष्टियाँ भरी हुई हैं: पंक्ति n में उनकी संख्या 2s_2(n) है, जहाँ s_2(n) n के द्विआधारी लेखन में इकाइयों की संख्या है (पंक्तियाँ 1, 2, 4: दो विषम प्रविष्टियाँ; पंक्ति 7 = (111)_2: सभी आठ)। यह स्वसमरूप प्रतिरूप — हर “विषमों का त्रिभुज” अपनी दो प्रतियाँ जनता है — चित्र रूप में कुमर की प्रमेय है, जो नीचे दी गई सप्ताहांत समस्या में सिद्ध की गई है। — पास्कल त्रिभुज की $0$ से $7$ तक की पंक्तियाँ, जिनमें *विषम* प्रविष्टियाँ भरी हुई हैं: पंक्ति $n$ में उनकी संख्या $2^{s_2(n)}$ है, जहाँ $s_2(n)$ $n$ के द्विआधारी लेखन में इकाइयों की संख्या है (पंक्तियाँ $1, 2, 4$ : दो विषम प्रविष्टियाँ; पंक्ति $7 = (111)_2$ : सभी आठ)। यह स्वसमरूप प्रतिरूप — हर “विषमों का त्रिभुज” अपनी दो प्रतियाँ जनता है — चित्र रूप में कुमर की प्रमेय है, जो नीचे दी गई सप्ताहांत समस्या में सिद्ध की गई है।

6.5 अभ्यास

अभ्यास 6.1 ★

यूक्लिडीय कलनविधि से $\gcd(1\,001, 777)$ संगणित कीजिए, और उसके लिए एक बेज़ू युग्म भी।

हल

हल — अभ्यास 6.1.

$1001 = 1 \times 777 + 224$ ; $777 = 3 \times 224 + 105$ ; $224 = 2 \times 105 + 14$ ; $105 = 7 \times 14 + 7$ ; $14 = 2 \times 7 + 0$ । अतः $\gcd(1001, 777) = 7$ । उलटी दिशा में:

7 = 105 - 7 \times 14 = 105 - 7(224 - 2\times 105) = 15 \times 105 - 7 \times 224

= 15(777 - 3\times 224) - 7\times 224 = 15 \times 777 - 52 \times 224 = 15 \times 777 - 52(1001 - 777) = 67 \times 777 - 52 \times 1001 .

जाँच: $67 \times 777 = 52\,059$ और $52 \times 1001 = 52\,052$ ; अंतर $7$ । बेज़ू युग्म: $1001u + 777v = 7$ के लिए $(u, v) = (-52, 67)$ ।

अभ्यास 6.2 ★

आधार $10$ में विभाज्यता के नियम सिद्ध कीजिए: कोई पूर्णांक $9$ के सापेक्ष अपने अंकों के योग के सर्वांगसम है, और $11$ के सापेक्ष अपने अंकों के एकांतरित योग के। $9$ के सापेक्ष और $11$ के सापेक्ष $123\,456\,789$ क्या है?

हल

हल — अभ्यास 6.2.

चूँकि $10 \equiv 1 \pmod 9$ : $10^k \equiv 1$ , अतः $\sum_k d_k 10^k \equiv \sum_k d_k \pmod 9$ । चूँकि $10 \equiv -1 \pmod{11}$ : $10^k \equiv (-1)^k$ , अतः पूर्णांक $11$ के सापेक्ष एकांतरित योग $\sum_k (-1)^k d_k$ के सर्वांगसम है (इकाई अंक से चिह्न $+$ के साथ आरंभ करते हुए)।

$123\,456\,789$ : अंकों का योग $45 \equiv 0 \pmod 9$ । इकाई से एकांतरित योग: $9 - 8 + 7 - 6 + 5 - 4 + 3 - 2 + 1 = 5$ , अतः संख्या $\equiv 5 \pmod{11}$ ।

अभ्यास 6.3 ★

$\Z$ में हल कीजिए: $91x \equiv 1 \pmod{237}$ (विस्तारित यूक्लिड)।

हल

हल — अभ्यास 6.3.

यूक्लिड: $237 = 2 \times 91 + 55$ ; $91 = 1 \times 55 + 36$ ; $55 = 1 \times 36 + 19$ ; $36 = 1 \times 19 + 17$ ; $19 = 1 \times 17 + 2$ ; $17 = 8 \times 2 + 1$ । उलटी दिशा में:

1 = 17 - 8\times 2 = 17 - 8(19 - 17) = 9\times 17 - 8\times 19 = 9(36 - 19) - 8\times 19 = 9\times 36 - 17\times 19

= 9\times 36 - 17(55 - 36) = 26\times 36 - 17\times 55 = 26(91 - 55) - 17\times 55 = 26\times 91 - 43\times 55

= 26\times 91 - 43(237 - 2\times 91) = 112 \times 91 - 43 \times 237.

अतः $91 \times 112 \equiv 1 \pmod{237}$ : हल $x \equiv 112 \pmod{237}$ हैं। (जाँच: $91 \times 112 = 10\,192 = 43 \times 237 + 1$ ।)

अभ्यास 6.4 ★

$17x + 39y = 1$ वाले सभी युग्म $(x, y) \in \Z^2$ खोजिए; फिर $17 x + 39 y = 5$ वाले सभी युग्म।

हल

हल — अभ्यास 6.4.

$\gcd(17, 39) = 1$ : यूक्लिड $39 = 2\times 17 + 5$ , $17 = 3\times 5 + 2$ , $5 = 2\times 2 + 1$ देता है, और उलटी दिशा में

1 = 5 - 2\times 2 = 5 - 2(17 - 3\times 5) = 7\times 5 - 2\times 17 = 7(39 - 2\times 17) - 2\times 17 = 7\times 39 - 16\times 17 .

विशिष्ट हल $(x_0, y_0) = (-16, 7)$ । समांगी समीकरण $17x + 39y = 0$ का व्यापक हल: $x = 39k$ , $y = -17k$ (क्योंकि $17 \mid 39y$ और $\gcd(17,39) = 1$ $17 \mid y$ पर बाध्य कर देते हैं — गाउस की प्रमेयिका)। अतः

(x, y) = (-16 + 39k,\; 7 - 17k), \qquad k \in \Z .

दाएँ पक्ष $5$ के लिए विशिष्ट हल को $5$ से गुणा कीजिए: $(x, y) = (-80 + 39k,\; 35 - 17k)$ , $k \in \Z$ ।

अभ्यास 6.5 ★★

सिद्ध कीजिए कि $a, b \in \N^*$ के लिए $\gcd(a,b) \times \operatorname{lcm}(a,b) = ab$ । (प्रतिज्ञप्ति 6.16 और $\min(\alpha,\beta) + \max(\alpha,\beta) = \alpha + \beta$ के मूल्यांकन-सूत्रों का प्रयोग कीजिए।)

हल

हल — अभ्यास 6.5.

प्रत्येक अभाज्य $p$ के लिए, $\alpha = v_p(a)$ और $\beta = v_p(b)$ के साथ:

v_p\bigl(\gcd(a,b)\bigr) + v_p\bigl(\operatorname{lcm}(a,b)\bigr) = \min(\alpha, \beta) + \max(\alpha, \beta) = \alpha + \beta = v_p(ab) .

जिन दो धनात्मक पूर्णांकों का प्रत्येक अभाज्य पर मूल्यांकन समान हो, वे बराबर होते हैं (प्रतिज्ञप्ति 6.16), अतः $\gcd(a,b)\operatorname{lcm}(a,b) = ab$ ।

अभ्यास 6.6 ★★

मान लीजिए $a = 2^{10} \times 3^4 \times 5^2$ और $b = 2^6 \times 3^7 \times 7$ । $\gcd(a, b)$ , $\operatorname{lcm}(a,b)$ , तथा $a$ के धनात्मक भाजकों की संख्या संगणित कीजिए। (भाजक-गणना सूत्र $\prod_i (\alpha_i + 1)$ सिद्ध कीजिए।)

हल

हल — अभ्यास 6.6.

मूल्यांकन: $\gcd(a, b) = 2^{\min(10,6)} 3^{\min(4,7)} 5^{\min(2,0)} 7^{\min(0,1)} = 2^6\, 3^4 = 5184$ ; $\operatorname{lcm}(a,b) = 2^{10}\, 3^7\, 5^2\, 7$ ।

भाजकों की गणना: $n = \prod p_i^{\alpha_i}$ का धनात्मक भाजक ठीक ऐसा चयन $\prod p_i^{\beta_i}$ है कि $0 \leq \beta_i \leq \alpha_i$ (प्रतिज्ञप्ति 6.16); चयन स्वतंत्र हैं, अतः $\prod_i (\alpha_i + 1)$ भाजक हैं। $a$ के लिए: $(10+1)(4+1)(2+1) = 165$ ।

अभ्यास 6.7 ★★

मूल्यांकनों का प्रयोग करके सिद्ध कीजिए कि प्रत्येक अभाज्य $p$ के लिए $\sqrt p$ अपरिमेय है: $p q^2 = r^2$ के दोनों पक्षों के $v_p$ की तुलना कीजिए।

हल

हल — अभ्यास 6.7.

मान लीजिए $r, q \in \N^*$ के साथ $\sqrt p = \frac rq$ , अर्थात् $p q^2 = r^2$ । $v_p$ लगाइए: $v_p(pq^2) = 1 + 2v_p(q)$ विषम है, जबकि $v_p(r^2) = 2 v_p(r)$ सम। कोई पूर्णांक एक ही साथ विषम और सम $p$ -मूल्यांकन नहीं रख सकता: विरोधाभास। अतः $\sqrt p \notin \Q$ ।

अभ्यास 6.8 ★★

(चीनी शेषफल समस्या) ऐसे सभी पूर्णांक $x$ खोजिए कि

x \equiv 2 \pmod 7, \qquad x \equiv 5 \pmod{11}.

साथ ही सिद्ध कीजिए कि सहअभाज्य $m, n$ के लिए सर्वांगसमताओं के युग्म $x \equiv a \ (m)$ , $x \equiv b\ (n)$ का सदा हल होता है, जो $mn$ के सापेक्ष अद्वितीय है।

हल

हल — अभ्यास 6.8.

व्यापक तथ्य। $\gcd(m,n) = 1$ के साथ बेज़ू $mu + nv = 1$ देता है। $x_0 = b\,mu + a\,nv$ रखिए। तब $x_0 \equiv a\,nv \equiv a(1 - mu) \equiv a \pmod m$ और इसी प्रकार $x_0 \equiv b \pmod n$ : अस्तित्व। यदि $x$ और $x'$ दो हल हैं, तो $m$ और $n$ $x - x'$ को विभाजित करते हैं, अतः $mn \mid x - x'$ (प्रमेय 6.8 (2)): $mn$ के सापेक्ष अद्वितीयता।

संख्यात्मक रूप से: $m = 7$ , $n = 11$ : $7 \times (-3) + 11 \times 2 = 1$ । अतः $x_0 = 5 \times 7 \times (-3) + 2 \times 11 \times 2 = -105 + 44 = -61 \equiv 16 \pmod{77}$ । जाँच: $16 = 2\times 7 + 2 \equiv 2 \pmod 7$ ; $16 = 11 + 5 \equiv 5 \pmod{11}$ । हल: $x \equiv 16 \pmod{77}$ ।

अभ्यास 6.9 ★★

$7$ के सापेक्ष $3^{1000}$ संगणित कीजिए, और $7^{100}$ के अंतिम दो दशमलव अंक ( $100 = 4 \times 25$ के सापेक्ष: अभ्यास 6.8 का प्रयोग कीजिए)।

हल

हल — अभ्यास 6.9.

$7$ के सापेक्ष: फर्मा $3^6 \equiv 1$ देता है, और $1000 = 6 \times 166 + 4$ , अतः $3^{1000} \equiv 3^4 = 81 \equiv 4 \pmod 7$ ।

$7^{100}$ के अंतिम दो अंक: $4$ के सापेक्ष और $25$ के सापेक्ष काम कीजिए। $4$ के सापेक्ष: $7 \equiv -1$ , अतः $7^{100} \equiv 1$ । $25$ के सापेक्ष: $7^2 = 49 \equiv -1$ , अतः $7^4 \equiv 1$ और $7^{100} = (7^4)^{25} \equiv 1$ । चीनी शेषफल प्रमेय (अभ्यास 6.8) से $7^{100} \equiv 1 \pmod{100}$ : अंतिम दो अंक $01$ हैं।

अभ्यास 6.10 ★★★

$m, n \in \N^*$ के लिए सिद्ध कीजिए कि $\gcd(2^m - 1,\, 2^n - 1) = 2^{\gcd(m,n)} - 1$ । संकेत: पहले दिखाइए कि $2^n - 1$ के सापेक्ष $2^m - 1$ का शेषफल $2^r - 1$ है, जहाँ $r$ $n$ के सापेक्ष $m$ का शेषफल है; फिर यूक्लिडीय कलनविधि का अनुसरण कीजिए।

हल

हल — अभ्यास 6.10.

$m = nq + r$ , $0 \leq r < n$ लिखिए। तब

2^m - 1 = 2^r\bigl(2^{nq} - 1\bigr) + 2^r - 1,

और $2^n - 1$ $2^{nq} - 1 = (2^n - 1)(2^{n(q-1)} + \dots + 1)$ को विभाजित करता है। अतः $2^n - 1$ के सापेक्ष $\;2^m - 1 \equiv 2^r - 1$ , और चूँकि $0 \leq 2^r - 1 < 2^n - 1$ , यही यूक्लिडीय शेषफल है।

अतः युग्म $(2^m - 1, 2^n - 1)$ पर यूक्लिडीय कलनविधि, घातांक-दर-घातांक, $(m, n)$ पर की कलनविधि का दर्पण है: हर भाग-पद ऊपर $(m, n)$ के स्थान पर $(n, r)$ और नीचे $(2^m - 1, 2^n - 1)$ के स्थान पर $(2^n - 1, 2^r - 1)$ रख देता है। ऊपर की कलनविधि $\gcd(m,n)$ पर समाप्त होती है, अतः नीचे वह $2^{\gcd(m,n)} - 1$ पर समाप्त होती है।

अभ्यास 6.11 ★★★

(विल्सन की प्रमेय) मान लीजिए $p$ अभाज्य है। सिद्ध कीजिए कि

(p-1)! \equiv -1 \pmod p ,

— इसके लिए $(p-1)!$ के प्रत्येक गुणनखंड को $p$ के सापेक्ष उसके प्रतिलोम के साथ युग्मित कीजिए और स्वयं से युग्मित होने वाले गुणनखंडों की पहचान कीजिए (पहले $x^2 \equiv 1 \pmod p$ हल कीजिए)। विलोम भी जाँचिए: यदि $n \geq 2$ अभाज्य नहीं है, तो $(n-1)! \not\equiv -1 \pmod n$ ।

हल

हल — अभ्यास 6.11.

पहले $x^2 \equiv 1 \pmod p$ हल कीजिए: $p \mid (x-1)(x+1)$ , अतः यूक्लिड की प्रमेयिका से $x \equiv 1$ या $x \equiv -1 \pmod p$ ।

गुणनफल $(p-1)! = 1 \times 2 \times \dots \times (p-1)$ में प्रत्येक गुणनखंड $a$ $p$ के सापेक्ष व्युत्क्रमणीय है, और उसका प्रतिलोम $a^{-1}$ फिर उन्हीं गुणनखंडों में से एक है (प्रतिज्ञप्ति 6.20)। प्रत्येक $a$ को $a^{-1}$ के साथ युग्मित कीजिए: युग्मों का गुणनफल $1$ होता है, केवल स्वयं से युग्मित होने वाले गुणनखंड ( $a = a^{-1}$ , अर्थात् $a^2 \equiv 1$ ) अकेले खड़े रहते हैं — और वे ठीक $1$ तथा $p - 1$ हैं। अतः

(p-1)! \equiv 1 \times (p - 1) \equiv -1 \pmod p .

( $p = 2$ के लिए: $1! = 1 \equiv -1 \pmod 2$ ; युग्मन का तर्क अपकर्षित हो जाता है पर परिणाम सत्य रहता है।)

विलोम। मान लीजिए $n \geq 2$ भाज्य है, $1 < a \leq b < n$ के साथ $n = ab$ । यदि $a < b$ , तो दोनों $(n-1)!$ के भिन्न गुणनखंडों के रूप में आते हैं, अतः $n \mid (n-1)!$ और $(n-1)! \equiv 0 \not\equiv -1$ । यदि $a = b$ (अर्थात् $n = a^2$ ): $a \geq 3$ के लिए $a$ और $2a$ दोनों $< n$ हैं, अतः $n = a^2 \mid a \times 2a \mid (n-1)!$ , वही निष्कर्ष; और $n = 4$ के लिए $(n-1)! = 6 \equiv 2 \not\equiv -1 \pmod 4$ ।

अभ्यास 6.12 ★★★

(फर्मा संख्याएँ) $n \in \N$ के लिए $F_n = 2^{2^n} + 1$ रखिए।

सिद्ध कीजिए कि $n \geq 1$ के लिए $F_0 F_1 \cdots F_{n-1} = F_n - 2$ (आगमन)।
उससे निकालिए कि फर्मा संख्याएँ जोड़ों में सहअभाज्य हैं।
उससे प्रमेय 6.14 से स्वतंत्र यह दूसरी उपपत्ति निकालिए कि अभाज्य संख्याएँ अनंत हैं।

हल

हल — अभ्यास 6.12.

आगमन। $n = 1$ के लिए: $F_0 = 3 = F_1 - 2 = 5 - 2$ । $F_0\cdots F_{n-1} = F_n - 2$ मानने पर:

$F_0 \cdots F_n = (F_n - 2)F_n = \bigl(2^{2^n} - 1\bigr)\bigl(2^{2^n} + 1\bigr) = 2^{2^{n+1}} - 1 = F_{n+1} - 2 .$
मान लीजिए $m < n$ और $d = \gcd(F_m, F_n)$ । (1) से $F_m$ $F_n - 2$ को विभाजित करता है, अतः $d$ $F_n$ और $F_n - 2$ दोनों को विभाजित करता है, इसलिए $2$ को भी। पर हर फर्मा संख्या विषम है, अतः $d = 1$ ।
प्रत्येक $F_n \geq 3$ का कोई अभाज्य भाजक $p_n$ है (प्रमेय 6.14 का पहला पद)। यदि $m \neq n$ , तो $p_m \neq p_n$ , क्योंकि कोई उभयनिष्ठ अभाज्य $\gcd(F_m, F_n) = 1$ को विभाजित करता। अतः प्रतिचित्रण $n \mapsto p_n$ $\N$ से अभाज्यों में एकैकी है: अभाज्य संख्याएँ अनंत हैं।

6.6 समस्या: लजांद्र का सूत्र और कुमर के हासिल

समस्या 6.1

$1000!$ के दशमलव लेखन के अंत में कितने शून्य आते हैं — और, इससे गहरे, $n!$ को, अथवा किसी द्विपद गुणांक को, विभाजित करने वाली अभाज्य $p$ की ठीक-ठीक घात क्या है? पूरे उत्तर प्रारंभिक अंकगणित के दो रत्न हैं: लजांद्र का सूत्र $v_p(n!) = \sum_{k\geq1} \lfloor n/p^k \rfloor$ , अपने अंकीय अवतार $v_p(n!) = \frac{n - s_p(n)}{p-1}$ के साथ, और कुमर की प्रमेय: $v_p\binom{m+n}m$ आधार $p$ में $m$ और $n$ जोड़ते समय के हासिलों की गणना करता है। यह समस्या दोनों सिद्ध करती है, उन्हें संख्यात्मक रूप से एक-दूसरे के सामने जाँचती है, और चिरपरिचित परिणाम बटोरती है — अंत के शून्य, पास्कल त्रिभुज की सम-विषमता, और अभाज्य संख्या प्रमेय की दिशा में पहला परिबंध। आगे सर्वत्र $p$ अभाज्य है, $\floor{x}$ पूर्णांक भाग है, और $s_p(n)$ आधार $p$ में लिखी $n$ के अंकों का योग दर्शाता है।

भाग I — फ़र्श, मूल्यांकन और लजांद्र का सूत्र।

अभ्यास: $10!$ संगणित कीजिए और अंत के शून्यों की संख्या पढ़िए; $v_2(10!)$ और $v_5(10!)$ प्रत्येक गुणनखंड $1, 2, \dots, 10$ के गुणनखंडन से सीधे संगणित कीजिए।
सिद्ध कीजिए कि $x \in \R$ और $n \in \N^*$ के लिए $\bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor = \lfloor x/n \rfloor$ ।
सिद्ध कीजिए कि सभी $a, b \in \N^*$ के लिए $v_p(a + b) \geq \min\bigl(v_p(a), v_p(b)\bigr)$ , और जब $v_p(a) \neq v_p(b)$ हो तब समता।
दिखाइए कि $\intint1n$ में $m$ के गुणजों की संख्या $\lfloor n/m \rfloor$ है।
लजांद्र का सूत्र सिद्ध कीजिए: प्रत्येक $n \in \N^*$ के लिए

$v_p(n!) = \sum_{k=1}^{\infty} \Bigl\lfloor \frac{n}{p^k} \Bigr\rfloor$

(यह परिमित योग है: $p^k > n$ होते ही पद लुप्त हो जाते हैं)। प्रत्येक $k$ के लिए $\intint1n$ के उन गुणनखंडों को गिनिए जो $p^k$ से विभाज्य हैं: वे जिस-जिस स्तर तक पहुँचते हैं, हर स्तर पर ठीक एक इकाई का योगदान करते हैं।

भाग II — अंकीय रूप और अंत के शून्य।

$v_5(1000!)$ और $v_2(1000!)$ संगणित कीजिए, और निष्कर्ष निकालिए: $1000!$ के अंत में कितने शून्य हैं?
लजांद्र के सूत्र का अंकीय रूप सिद्ध कीजिए: $n = \sum_i a_i p^i$ को आधार $p$ में लिखने पर,

$v_p(n!) = \frac{n - s_p(n)}{p - 1} .$
$p = 2$ के लिए दो परिणाम: दिखाइए कि $2^n$ $n!$ को कभी विभाजित नहीं करता, और यह कि $2^{n-1}$ $n!$ को ठीक तभी विभाजित करता है जब $n$ $2$ की कोई घात हो।
न्यूनता का परिबंध दीजिए: दिखाइए $\frac n{p-1} - \log_p(n) - 1 \leq v_p(n!) < \frac n{p-1}$ , जिससे $\frac{v_p(n!)}{n} \to \frac1{p-1}$ : दीर्घकाल में प्रति इकाई एक गुणनखंड $p$ का अनुपात $\frac1{p-1}$ जुड़ता जाता है।
मान लीजिए $Z(n) = v_5(n!)$ $n!$ के अंत के शून्यों की संख्या है। दिखाइए $Z(n) - Z(n-1) = v_5(n)$ , उससे निकालिए कि $Z$ मान $5$ को पूरी तरह छोड़ देता है ( $Z(24)$ और $Z(25)$ संगणित कीजिए), और सिद्ध कीजिए कि किसी भी क्रमगुणित के अंत में ठीक पाँच शून्य नहीं होते।

भाग III — कुमर की प्रमेय।

सिद्ध कीजिए कि सभी $x, y \in \R$ के लिए $\lfloor x + y \rfloor - \lfloor x \rfloor - \lfloor y \rfloor \in \{0, 1\}$ , और लजांद्र के सूत्र से निकालिए कि

$v_p\binom{m+n}m = \sum_{k\geq1}\Bigl( \Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac{m}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac{n}{p^k}\Bigr\rfloor\Bigr),$

जो ऐसे पदों का योग है जिनमें से हर एक $0$ या $1$ है।
कुमर की प्रमेय सिद्ध कीजिए: उस योग का $k$ -वाँ पद ठीक तब $1$ के बराबर है जब आधार $p$ में $m$ और $n$ का योग स्थान $k$ में हासिल उत्पन्न करता हो; अतः $v_p\binom{m+n}m$ हासिलों की कुल संख्या है। ( $0 \leq m_0, n_0 < p^k$ के साथ $m = p^km_1 + m_0$ और $n = p^kn_1 + n_0$ लिखिए और $\lfloor (m_0 + n_0)/p^k \rfloor$ का निरीक्षण कीजिए।)
उससे $0 < j < p^k$ के लिए निकालिए:

$v_p\binom{p^k}{j} = k - v_p(j) ,$

जोड़ $j + (p^k - j)$ में हासिल गिनकर। (विशेष रूप से $0 < j < p$ के लिए $p \mid \binom p j$ : प्रमेय 6.23 का मुख्य पद, फिर से प्राप्त।)
सिद्ध कीजिए कि $v_2\binom{2n}n = s_2(n)$ । उससे निकालिए कि केंद्रीय द्विपद गुणांक सदा सम है, और यह कि $\binom{2n}n \equiv 2 \pmod 4$ ठीक तब जब $n$ $2$ की कोई घात हो।
वांडरमोंड सर्वसमिका (अभ्यास 2.7) और प्रश्न 13 का प्रयोग करके दिखाइए कि प्रत्येक अभाज्य $p$ के लिए $\binom{2p}p \equiv 2 \pmod p$ ।
$v_3\binom{1000}{500}$ दो बार संगणित कीजिए: एक बार कुमर से (आधार $3$ में $500$ लिखिए और $500 + 500$ में हासिल गिनिए), और एक बार लजांद्र के अंकीय रूप से ( $s_3(500)$ और $s_3(1000)$ संगणित कीजिए); जाँचिए कि दोनों वही मान देते हैं।

भाग IV — पास्कल त्रिभुज की सम-विषमता, और अभाज्य-घनत्व का एक परिबंध।

अंक-कसौटी सिद्ध कीजिए: $\binom nk$ विषम है यदि और केवल यदि $k$ का प्रत्येक द्विआधारी अंक $n$ के तदनुरूप अंक से अधिक न हो। आधार $p$ में $p \nmid \binom nk$ के लिए अनुरूप कसौटी बताइए और सिद्ध कीजिए।
उससे निकालिए कि पास्कल त्रिभुज की पंक्ति $n$ में ठीक $2^{s_2(n)}$ विषम प्रविष्टियाँ हैं; पंक्तियों $4$ और $5$ पर सत्यापित कीजिए।
उससे निकालिए कि सभी भीतरी प्रविष्टियाँ $\binom nk$ ( $0 < k < n$ ) सम हैं यदि और केवल यदि $n$ $2$ की कोई घात हो।
सिद्ध कीजिए कि $\binom{m+n}m$ को विभाजित करने वाली प्रत्येक अभाज्य घात अधिक से अधिक $m + n$ है: यदि $p^a \mid \binom{m+n}m$ , तो $p^a \leq m + n$ । (प्रश्न 11 के योग में कितने अशून्य पद हो सकते हैं?)
उससे निकालिए कि $\binom{2n}n$ $\operatorname{lcm}(1, 2, \dots, 2n)$ को विभाजित करता है, और इसे निम्न परिबंध $\binom{2n}n \geq \frac{4^n}{2n+1}$ (जिसे आप सिद्ध करेंगे: पंक्ति $2n$ की $2n + 1$ प्रविष्टियों में केंद्रीय सबसे बड़ी है) के साथ मिलाकर प्राप्त कीजिए

$\operatorname{lcm}(1, \dots, 2n) \geq \frac{4^n}{2n+1} :$

अर्थात् आरंभिक पूर्णांकों के उभयनिष्ठ गुणज चरघातांकी रूप से बढ़ते हैं — अभाज्यों की प्रचुरता की पहली परिमाणात्मक झलक।

भाग V — संश्लेषण।

ऐसा लघुतम $n$ खोजिए कि $n!$ के अंत में कम से कम $2026$ शून्य हों। ( $Z(n) \approx n/4$ का आकलन कीजिए, फिर यथार्थ सूत्र से समायोजन कीजिए।)
एक अंतिम प्रति-जाँच: दिखाइए कि $7$ $\binom{100}{50}$ को विभाजित नहीं करता — पहले $50$ को आधार $7$ में लिखकर और जाँचकर कि जोड़ $50 + 50$ में कोई हासिल नहीं है, फिर लजांद्र के सूत्र से $v_7(100!)$ और $v_7(50!)$ संगणित करके।
इस समस्या में ठीक कहाँ प्रयोग हुआ: (क) अद्वितीय गुणनखंडन; (ख) यूक्लिडीय भाग का वियोजन $n = p^k n_1 + n_0$ ; (ग) अध्याय 2 का कोई गणना-तर्क? प्रत्येक के लिए एक वाक्य।
एक छोटे अनुच्छेद में संश्लेषण: लजांद्र का सूत्र विभाज्यता के प्रश्न को अंकों के अंकगणित में बदल देता है, और कुमर की प्रमेय उत्तर को एक ही जोड़ के हासिलों से पढ़ लेती है — इस अनुवाद पर, प्रश्न 16 की जाँचों पर, और प्रश्न 21 का परिबंध अभाज्यों के विषय में जो संकेत देता है उस पर टिप्पणी कीजिए (पूरा कथन, अर्थात् अभाज्य संख्या प्रमेय, इस खंड से बहुत परे है; इस अध्याय के औज़ार-संदूक का बहुपदीय अनुरूप अध्याय 8 है)।

हल

हल — समस्या 6.1.

1. $10! = 3\,628\,800$ : अंत में दो शून्य। गुणनखंड-दर-गुणनखंड मूल्यांकन: $2$ की घातें $2, 4 = 2^2, 6, 8 = 2^3, 10$ से आती हैं, कुल $v_2(10!) = 1 + 2 + 1 + 3 + 1 = 8$ ; $5$ की घातें $5$ और $10$ से: $v_5(10!) = 2$ । अंत के शून्य $= \min(v_2, v_5) = 2$ , जो संगत है।

2. यूक्लिडीय भाग $\lfloor x\rfloor = nq + r$ , $0 \leq r \leq n - 1$ लिखिए। तब $0 \leq r + \{x\} < n$ के साथ $x = nq + r + \{x\}$ , अतः $\lfloor x/n \rfloor = q = \bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor$ ।

3. मान लीजिए $\alpha = v_p(a) \leq \beta = v_p(b)$ (आवश्यकता हो तो अदला-बदली कीजिए) और $p \nmid a', b'$ के साथ $a = p^\alpha a'$ , $b = p^\beta b'$ लिखिए। तब $a + b = p^\alpha\bigl(a' + p^{\beta - \alpha}b'\bigr)$ , अतः $v_p(a + b) \geq \alpha = \min$ । यदि $\alpha < \beta$ , तो कोष्ठक $a' + p^{\beta-\alpha}b' \equiv a' \not\equiv 0 \pmod p$ है: मूल्यांकन ठीक $\alpha$ है।

4. $\intint1n$ में $m$ के गुणज $m, 2m, \dots, qm$ हैं, जहाँ $q$ वह बृहत्तम पूर्णांक है जिसके लिए $qm \leq n$ , अर्थात् $q = \lfloor n/m \rfloor$ ।

5. अद्वितीय गुणनखंडन से $v_p(n!) = \sum_{j=1}^{n} v_p(j)$ । दूसरी तरह गिनिए: प्रत्येक $j$ $v_p(j) = \#\{k \geq 1 : p^k \mid j\}$ का योगदान करता है, अतः

v_p(n!) = \sum_{j=1}^n \#\{k : p^k \mid j\} = \sum_{k\geq1} \#\{j \leq n : p^k \mid j\} = \sum_{k\geq1} \Bigl\lfloor \frac n{p^k} \Bigr\rfloor

प्रश्न 4 से — यही लजांद्र का सूत्र है। योग परिमित है: $p^k > n$ वाले पद लुप्त हो जाते हैं।

6. $v_5(1000!) = 200 + 40 + 8 + 1 = 249$ ( $5, 25, 125, 625$ से भाग); $v_2(1000!) = 500 + 250 + 125 + 62 + 31 + 15 + 7 + 3 + 1 = 994$ । $1000!$ के अंत के शून्य: हर शून्य एक $2$ और एक $5$ खाता है, अतः उनकी संख्या $\min(994, 249) = 249$ है।

7. $n = \sum_i a_ip^i$ के साथ प्रश्न 2 $\lfloor n/p^k \rfloor = \sum_{i \geq k} a_ip^{i-k}$ देता है (आधार- $p$ प्रसार को काट दीजिए)। $k \geq 1$ पर योग करके और दोनों परिमित योगों की अदला-बदली करके:

v_p(n!) = \sum_{i\geq1} a_i \sum_{k=1}^{i} p^{i-k} = \sum_{i\geq0} a_i\,\frac{p^i - 1}{p - 1} = \frac{n - s_p(n)}{p - 1} .

8. $p = 2$ के लिए: $v_2(n!) = n - s_2(n)$ । चूँकि $n \geq 1$ में $s_2(n) \geq 1$ है, सदा $v_2(n!) \leq n - 1 < n$ : $2^n \nmid n!$ । और $v_2(n!) = n - 1$ तभी जब $s_2(n) = 1$ , अर्थात् तभी जब $n$ $2$ की घात हो।

9. $n$ के $\lfloor \log_p n \rfloor + 1$ आधार- $p$ अंक हैं, जिनमें से हर अधिक से अधिक $p - 1$ है, अतः $1 \leq s_p(n) \leq (p-1)\bigl(\log_p(n) + 1\bigr)$ । प्रश्न 7 में प्रतिस्थापित करने पर:

\frac n{p-1} - \log_p(n) - 1 \;\leq\; v_p(n!) \;<\; \frac n{p-1},

और $n$ से भाग देने पर: $\frac{v_p(n!)}n \to \frac1{p-1}$ ।

10. $Z(n) - Z(n-1) = v_5(n!/(n-1)!) = v_5(n)$ : अंत के शून्यों की गणना $5$ के प्रत्येक गुणज पर $v_5(n)$ से कूदती है और बीच में अचर रहती है। $Z(24) = \lfloor24/5\rfloor = 4$ और $Z(25) = 5 + 1 = 6$ : $n = 25$ पर गणना $4$ से सीधे $6$ पर कूद जाती है ( $v_5(25) = 2$ ), और चूँकि $Z$ अह्रासमान है और पहले $Z \leq 4$ तथा बाद में $Z \geq 6$ है, मान $5$ कभी प्राप्त नहीं होता: किसी क्रमगुणित के अंत में ठीक पाँच शून्य नहीं होते।

11. $x = \lfloor x\rfloor + \{x\}$ लिखिए: $\lfloor x + y\rfloor = \lfloor x\rfloor + \lfloor y\rfloor + \lfloor \{x\} + \{y\}\rfloor$ , और $0 \leq \{x\} + \{y\} < 2$ अंतिम फ़र्श को $0$ या $1$ बना देता है। फिर लजांद्र को तीन बार लगाने पर,

v_p\binom{m+n}m = v_p\bigl((m{+}n)!\bigr) - v_p(m!) - v_p(n!) = \sum_{k\geq1}\Bigl( \Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac{m}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac{n}{p^k}\Bigr\rfloor\Bigr),

जो $0$ और $1$ का परिमित योग है (पहला दावा $x = m/p^k$ , $y = n/p^k$ पर लगाइए)।

12. $k \geq 1$ नियत कीजिए और $0 \leq m_0, n_0 < p^k$ के साथ $m = p^km_1 + m_0$ , $n = p^kn_1 + n_0$ लिखिए (यूक्लिडीय भाग: $m_0$ $m$ के $k$ निचले अंकों से बनी संख्या है)। तब

\Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac m{p^k}\Bigr\rfloor - \Bigl\lfloor\frac n{p^k}\Bigr\rfloor = \Bigl\lfloor\frac{m_0 + n_0}{p^k}\Bigr\rfloor ,

जो $m_0 + n_0 \geq p^k$ होने पर $1$ है और अन्यथा $0$ । पर $m_0 + n_0 \geq p^k$ ठीक यही कहता है कि $m$ और $n$ के $k$ निचले अंकों को जोड़ने पर स्थान $k$ में उफान आता है — अर्थात् विद्यालय की जोड़-विधि में स्थान $k$ में एक हासिल। $k$ पर योग करने पर: $v_p\binom{m+n}m$ आधार- $p$ जोड़ $m + n$ में हासिलों की संख्या है। (कुमर, 1852।)

13. कुमर को $m = j$ , $n = p^k - j$ , योग $p^k = (1\underbrace{0\cdots0}_{k})_p$ पर लगाइए। मान लीजिए $a = v_p(j)$ , अतः $j$ के स्थानों $0, \dots, a-1$ पर आधार- $p$ अंक $0$ हैं और स्थान $a$ पर अंक अशून्य है। $p^k - j$ के स्थान $a$ से नीचे के अंक भी $0$ हैं ( $p^k - j = p^a(p^{k-a} - j/p^a)$ )। स्थान $a$ पर दोनों अशून्य अंकों का योग $p$ होना ही चाहिए (परिणामी अंक $0$ ): एक हासिल; और $a+1, \dots, k-1$ के प्रत्येक स्थान पर अंक तथा आता हुआ हासिल मिलकर $p$ बनते हैं (परिणामी अंक फिर $0$ ): हासिल आगे बढ़ता जाता है। कुल: $k - a$ हासिल, अतः $v_p\binom{p^k}j = k - v_p(j)$ । $k = 1$ के लिए: $0 < j < p$ के लिए $v_p\binom pj = 1$ , अर्थात् वही विभाज्यता जो प्रमेय 6.23 में प्रयुक्त हुई।

14. अंकीय रूप (प्रश्न 7) से, $s_2(2n) = s_2(n)$ का प्रयोग करते हुए (एक शून्य अंक जोड़कर):

v_2\binom{2n}n = \bigl(2n - s_2(2n)\bigr) - 2\bigl(n - s_2(n)\bigr) = 2s_2(n) - s_2(2n) = s_2(n) \geq 1 :

$\binom{2n}n$ सदा सम है, और $v_2 = 1$ (अर्थात् $\binom{2n}n \equiv 2 \pmod 4$ ) ठीक तब जब $s_2(n) = 1$ , अर्थात् जब $n$ $2$ की घात हो।

15. $m = n = k = p$ के साथ वांडरमोंड: $\binom{2p}p = \sum_{j=0}^p \binom pj\binom p{p-j} = \sum_{j=0}^p \binom pj^2$ । $0 < j < p$ के लिए $p \mid \binom pj$ (प्रश्न 13), अतः $\binom pj^2 \equiv 0 \pmod p$ ; और सिरों के पद $1 + 1$ देते हैं: $\binom{2p}p \equiv 2 \pmod p$ ।

16. आधार $3$ : $500 = 486 + 9 + 3 + 2$ , अंक (निम्न से उच्च) $(2, 1, 1, 0, 0, 2)$ , अतः $s_3(500) = 6$ ; और $1000 = 729 + 243 + 27 + 1$ , अंक $(1, 0, 0, 1, 0, 1, 1)$ , अतः $s_3(1000) = 4$ । कुमर: आधार $3$ में $500 + 500$ जोड़िए: स्थान $0$ : $2 + 2 = 4$ , अंक $1$ हासिल $1$ ; स्थान $1$ : $1 + 1 + 1 = 3$ , अंक $0$ हासिल $1$ ; स्थान $2$ : $1 + 1 + 1 = 3$ , अंक $0$ हासिल $1$ ; स्थान $3$ : $0 + 0 + 1 = 1$ , कोई हासिल नहीं; स्थान $4$ : $0$ ; स्थान $5$ : $2 + 2 = 4$ , अंक $1$ हासिल $1$ ; स्थान $6$ : हासिल आ गिरता है: अंक $1$ । चार हासिल: $v_3\binom{1000}{500} = 4$ । लजांद्र: $v_3(1000!) = \frac{1000 - 4}2 = 498$ और $v_3(500!) = \frac{500 - 6}2 = 247$ , अतः $v_3\binom{1000}{500} = 498 - 2\times247 = 4$ । दोनों संगणनाएँ मेल खाती हैं — और जोड़ के अंक $(1, 0, 0, 1, 0, 1, 1)$ $1000$ को फिर से बना देते हैं, जैसा होना ही चाहिए।

17. कुमर ( $p = 2$ , $m = k$ , $n' = n - k$ ) से: $\binom nk$ विषम है तभी जब आधार $2$ में जोड़ $k + (n - k)$ में कोई हासिल न हो, अर्थात् तभी जब हर स्थान पर अंक $k_i + (n - k)_i = n_i$ को संतुष्ट करें; उस स्थिति में सभी $i$ के लिए $k_i \leq n_i$ । विलोमतः, यदि सभी $i$ के लिए $k_i \leq n_i$ , तो अंकों $n_i - k_i$ वाली संख्या $n - k$ है और जोड़ हासिल-रहित है। आधार $p$ में वही उपपत्ति: $p \nmid \binom nk$ तभी जब $k$ का प्रत्येक आधार- $p$ अंक $n$ के तदनुरूप अंक से अधिक न हो।

18. ऐसे $k \in \intint0n$ गिनिए जिनके अंक $k_i \leq n_i$ का पालन करते हों: $k$ का हर अंक स्वतंत्र रूप से $n_i + 1$ मानों में से चुना जाता है, जिससे $\prod_i (n_i + 1)$ चयन मिलते हैं; आधार $2$ में यह $2^{\#\{i : n_i = 1\}} = 2^{s_2(n)}$ है। पंक्ति $4 = (100)_2$ : $2^1 = 2$ विषम प्रविष्टियाँ — और सचमुच $1, 4, 6, 4, 1$ की विषम प्रविष्टियाँ केवल सिरों पर हैं। पंक्ति $5 = (101)_2$ : $2^2 = 4$ — और सचमुच $1, 5, 10, 10, 5, 1$ ।

19. सभी भीतरी प्रविष्टियाँ सम हैं $\iff$ पंक्ति में ठीक $2$ विषम प्रविष्टियाँ हैं (दोनों सिरे सदा विषम होते हैं) $\iff 2^{s_2(n)} = 2 \iff s_2(n) = 1 \iff n$ $2$ की घात है।

20. प्रश्न 11 के योग में $k$ -वाँ पद तभी लुप्त हो जाता है जब $p^k > m + n$ (तब तीनों फ़र्श बराबर हैं; वस्तुतः $p^k > m+n$ होने पर पहला $0$ है; और सरलता से, हर पद $0$ है)। अतः अधिक से अधिक $\lfloor \log_p(m+n)\rfloor$ पद अशून्य हैं, और हर एक $1$ का है: $a = v_p\binom{m+n}m \leq \log_p(m+n)$ , अर्थात् $p^a \leq m + n$ ।

21. प्रत्येक अभाज्य $p$ के लिए $v_p\bigl(\operatorname{lcm}(1, \dots, 2n)\bigr) = \lfloor\log_p(2n)\rfloor$ ( $2n$ से अधिक न होने वाली $p$ की बृहत्तम घात $1, \dots, 2n$ में आती है)। $m = n$ के साथ प्रश्न 20 प्रत्येक $p$ के लिए $v_p\binom{2n}n \leq \lfloor\log_p(2n)\rfloor$ देता है: प्रतिज्ञप्ति 6.16 से $\binom{2n}n \mid \operatorname{lcm}(1, \dots, 2n)$ । आकार के लिए: अनुपात $\binom{2n}{k+1}/\binom{2n}k = \frac{2n-k}{k+1} \geq 1$ ठीक $k < n$ के लिए है, अतः पंक्ति $2n$ की $2n + 1$ प्रविष्टियों में केंद्रीय सबसे बड़ी है, जिससे $4^n = \sum_k \binom{2n}k \leq (2n+1)\binom{2n}n$ । मिलाकर:

\operatorname{lcm}(1, \dots, 2n) \geq \binom{2n}n \geq \frac{4^n}{2n + 1} .

यदि $2n$ से नीचे अभाज्य कम होते, तो लघुत्तम समापवर्त्य इतना बड़ा नहीं हो सकता था: लघुत्तम समापवर्त्य की चरघातांकी वृद्धि अभाज्यों की प्रचुरता का परिमाणात्मक चिह्न है।

22. $Z(n) = \sum_k\lfloor n/5^k\rfloor \approx \frac n4$ , अतः $n = 4 \times 2026 = 8104$ के आसपास निशाना लगाइए: $Z(8104) = 1620 + 324 + 64 + 12 + 2 = 2022$ । $5$ के गुणजों से आगे बढ़िए: $Z(8110) = 2024$ , $Z(8115) = 2025$ , और

Z(8120) = 1624 + 324 + 64 + 12 + 2 = 2026 .

चूँकि $Z$ $5$ और $Z(8119) = Z(8115) = 2025$ के गुणजों के बीच अचर है, कम से कम $2026$ अंत के शून्यों वाला लघुतम $n$ $n = 8120$ है।

23. आधार $7$ : $50 = 49 + 1$ , अंक (निम्न से उच्च) $(1, 0, 1)$ । $50 + 50$ जोड़ने पर: स्थान $0$ : $1 + 1 = 2 < 7$ , कोई हासिल नहीं; स्थान $1$ : $0 + 0 = 0$ ; स्थान $2$ : $1 + 1 = 2 < 7$ , कोई हासिल नहीं। हासिल-रहित, अतः कुमर से $v_7\binom{100}{50} = 0$ : $7 \nmid \binom{100}{50}$ । लजांद्र भी यही कहता है: $v_7(100!) = \lfloor 100/7 \rfloor + \lfloor 100/49 \rfloor = 14 + 2 = 16$ और $v_7(50!) = 7 + 1 = 8$ , अतः $v_7\binom{100}{50} = 16 - 2\times8 = 0$ ।

24. (क) अद्वितीय गुणनखंडन $v_p$ की परिभाषा और उसकी योगात्मकता के मूल में है, अतः लजांद्र के सूत्र और हर विभाज्यता-निष्कर्ष के भी (प्रतिज्ञप्ति 6.16)। (ख) यूक्लिडीय भाग ने प्रश्न 2 की कटाई-सर्वसमिका दी और वह विभाजन $m = p^km_1 + m_0$ दिया जो हासिल को अलग कर देता है (प्रश्न 12)। (ग) गणना: $m$ के गुणजों की गणना (प्रश्न 4), अंक-चयन का गुणनफल (प्रश्न 18), और पंक्ति-योग का परिबंध $4^n \leq (2n+1)\binom{2n}n$ (प्रश्न 21) — ये सब अध्याय 2 की शैली के तर्क हैं।

25. लजांद्र “ $n!$ को $p$ की कौन-सी घात विभाजित करती है” को आधार- $p$ के अंक-अंकगणित में बदल देता है; कुमर द्विपद गुणांकों के लिए उत्तर को एक ही जोड़ के हासिलों में सिकोड़ देता है — विभाज्यता, जो विशाल संख्याओं का समग्र गुणधर्म लगती है, स्थानीय रूप से, अंक-दर-अंक, पढ़ ली जाती है। प्रश्न 16 इसका आदर्श है: हाथ से गिने हुए चार हासिल सैकड़ों अंकों वाली संख्या में $3$ की ठीक-ठीक घात निर्धारित कर देते हैं। और प्रश्न 21 दिखाता है कि यही विचार-मंडल गहरे जल को छू रहा है: $\operatorname{lcm}(1, \dots, 2n)$ के लिए चरघातांकी निम्न परिबंध अभाज्य संख्या प्रमेय की दिशा में पहला, पूर्णतः प्रारंभिक पद है, जिसकी उपपत्ति इस खंड से बहुत परे है। पूरा औज़ार-संदूक — भाग, महत्तम समापवर्तक, मूल्यांकन — अध्याय 8 में बहुपदों के लिए फिर चलाया जाता है, जहाँ अंक-प्रसार का अनुरूप $(X - a)$ की घातों में प्रसार है।