---
title: "पूर्णांक अंकगणित"
book: "विश्वविद्यालय गणित — स्नातक वर्ष 1"
subject: math
language: hi
chapter: 6
exercises: 12
source: https://one-course.com/books/math/3/hi/chapter/6-integer-arithmetic
---

# अध्याय 6 — पूर्णांक अंकगणित

अंकगणित — $\Z$ में [विभाज्यता](#def-b1-arith-divides) का अध्ययन — उच्चतर माध्यमिक खंड में आरंभ हुआ था। यह अध्याय उसे यूक्लिडीय भाग से पूरी उपपत्तियों के साथ नए सिरे से खड़ा करता है: [महत्तम समापवर्तक](#thm-b1-arith-gcd) और [यूक्लिडीय कलनविधि](#met-b1-arith-euclid), बेज़ू सर्वसमिका और गाउस की प्रमेयिका, [अभाज्य गुणनखंडन](#thm-b1-arith-fta), तथा फर्मा की लघु प्रमेय तक सर्वांगसमताओं का कलन। अपने आकर्षण से आगे, यह सामग्री वह आदर्श है जिसका अनुकरण [अध्याय 8](https://one-course.com/books/math/3/hi/chapter/8-polynomials#ch-b1-poly) बहुपदों के लिए करता है।

## 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 .
$$

**उपपत्ति.** *अस्तित्व।* [समुच्चय](https://one-course.com/books/math/3/hi/chapter/1-logic-sets-and-maps#def-b1-logic-sets) $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\ZZ के उपसमूह; महत्तम समापवर्तक का अस्तित्व).**

1. $(\Z, +)$ का प्रत्येक उपसमूह किसी अद्वितीय $n \in \N$ के लिए $n\Z =  \{nk : k \in \Z\}$ रूप का है।
2. जो $a, b \in \Z$ दोनों शून्य न हों, उनके लिए [समुच्चय](https://one-course.com/books/math/3/hi/chapter/1-logic-sets-and-maps#def-b1-logic-sets) $a\Z + b\Z =  \{au + bv : u, v \in \Z\}$ $\Z$ का उपसमूह है, अतः किसी अद्वितीय $d \in  \N^*$ के लिए $d\,\Z$ के बराबर है। यही $d$ *महत्तम समापवर्तक* $\gcd(a, b)$ है: वह $a$ और $b$ को [विभाजित करता है](#def-b1-arith-divides) , और $a$ तथा $b$ का प्रत्येक उभयनिष्ठ भाजक $d$ को [विभाजित करता है](#def-b1-arith-divides) ।

**उपपत्ति.** (1) मान लीजिए $H \subseteq \Z$ उपसमूह है (अरिक्त, घटाव के अंतर्गत स्थायी; औपचारिक परिभाषा [अध्याय 7](https://one-course.com/books/math/3/hi/chapter/7-algebraic-structures#ch-b1-structures) में है, और केवल यही दो गुणधर्म प्रयुक्त होते हैं)। यदि $H = \{0\}$, तो $n = 0$ लीजिए। अन्यथा $H$ में कोई अशून्य अवयव और उसका विपरीत भी है, अतः उसमें एक लघुतम पूर्णतः धनात्मक अवयव $n$ है। तब $n\Z \subseteq H$। $x \in H$ के लिए $0 \leq r < n$ ([प्रमेय 6.2](#thm-b1-arith-division)) के साथ $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$ दोनों को [विभाजित करता है](#def-b1-arith-divides)। और यदि $c$ $a$ तथा $b$ को [विभाजित करता है](#def-b1-arith-divides), तो $c$ प्रत्येक $au + bv$ को [विभाजित करता है](#def-b1-arith-divides) — विशेष रूप से $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$ [सहअभाज्य](#cor-b1-arith-bezout) हैं यदि और केवल यदि $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$ होने तक दोहराइए; अंतिम अशून्य शेषफल ही [महत्तम समापवर्तक](#thm-b1-arith-gcd) है। भागों को उलटी दिशा में चलाने से (या नीचे उतरते समय गुणांक बनाए रखने से) एक बेज़ू युग्म $(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$।

1. (गाउस की प्रमेयिका) यदि $a \mid bc$ और $\gcd(a, b) = 1$ , तो $a \mid c$ ।
2. यदि $a \mid c$ , $b \mid c$ और $\gcd(a,b) = 1$ , तो $ab \mid c$ ।
3. यदि $\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](#cor-b1-arith-bezout) से $\gcd(a, bc) = 1$। ∎

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

$6x + 10y = 4$ वाले सभी $(x, y) \in \Z^2$ खोजिए। पहले *अस्तित्व की जाँच*: $\gcd(6, 10) = 2$ $4$ को [विभाजित करता है](#def-b1-arith-divides), अतः हल विद्यमान हैं (यदि [महत्तम समापवर्तक](#thm-b1-arith-gcd) दाएँ पक्ष को विभाजित न करता, तो बायाँ पक्ष सदा उसका गुणज होता और कोई हल न होता)। पूरे समीकरण को भाग दीजिए: $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](https://one-course.com/books/math/3/hi/chapter/5-linear-differential-equations#ch-b1-diffeq) में है, जहाँ अद्वितीयता की भूमिका गाउस की प्रमेयिका निभाती है।

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

$\operatorname{lcm}(a, b)$ उपसमूह $a\Z \cap b\Z$ का $\N$ में जनक है: वह $a$ और $b$ का ऐसा उभयनिष्ठ गुणज है जो प्रत्येक उभयनिष्ठ गुणज को [विभाजित करता है](#def-b1-arith-divides), और $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$)। व्यावहारिक मार्ग पर ध्यान दीजिए: *पहले [महत्तम समापवर्तक](#thm-b1-arith-gcd) संगणित कीजिए* (यूक्लिड: $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](#thm-b1-arith-gauss)) *यूक्लिड की प्रमेयिका* सत्य है: यदि $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$ का सदा कोई [अभाज्य](#def-b1-arith-prime) भाजक $\leq \sqrt n$ होता है। अतः यह जाँचने के लिए कि $n$ [अभाज्य](#def-b1-arith-prime) है या नहीं, $\sqrt n$ तक के [अभाज्य](#def-b1-arith-prime) आज़मा लेना पर्याप्त है। $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$): अतः [अभाज्य](#def-b1-arith-prime), और वह भी दो सौ के बदले छह भागों में। $\sqrt n$ की बाधा एक सच्ची देहली है: सौ अंकों वाली संख्याओं के लिए उसे कुशलता से पार करने के लिए वे आधुनिक अभाज्यता-परीक्षण चाहिए जो [प्रमेय 6.23](#thm-b1-arith-fermat) से उपजे हैं।

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

[अभाज्य](#def-b1-arith-prime) संख्याएँ अनंत हैं।

**उपपत्ति.** प्रत्येक पूर्णांक $n \geq 2$ का कोई [अभाज्य](#def-b1-arith-prime) भाजक है: उसका लघुतम भाजक $\geq 2$ [अभाज्य](#def-b1-arith-prime) है (उसका उचित गुणनखंडन $n$ का उससे छोटा भाजक दे देता)। अब मान लीजिए $p_1, \dots, p_k$ ही सारे [अभाज्य](#def-b1-arith-prime) हैं, और $N = p_1 p_2 \cdots p_k + 1 \geq 2$ रखिए। कोई [अभाज्य](#def-b1-arith-prime) $p_i$ $N$ को [विभाजित करता है](#def-b1-arith-divides); पर $p_i$ $N - 1 = p_1\cdots
p_k$ को भी [विभाजित करता है](#def-b1-arith-divides), अतः $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](https://one-course.com/books/math/3/hi/chapter/1-logic-sets-and-maps#thm-b1-logic-induction)) से: $n = 2$ [अभाज्य](#def-b1-arith-prime) है; $n > 2$ के लिए या तो $n$ [अभाज्य](#def-b1-arith-prime) है, या $2 \leq a, b < n$ के साथ $n = ab$, और आगमन परिकल्पना $a$ तथा $b$ का गुणनखंडन कर देती है।

*अद्वितीयता।* मान लीजिए $p_1 \cdots p_r = q_1 \cdots q_s$ ([अभाज्य](#def-b1-arith-prime) पुनरावृत्ति सहित सूचीबद्ध, मान लीजिए $r \leq s$), और $r$ पर आगमन कीजिए। यदि $r = 0$, तो बायाँ पक्ष $1$ है, जो $s = 0$ पर बाध्य कर देता है (अभाज्यों का अरिक्त गुणनफल $1$ से बड़ा होता है)। $r \geq 1$ के लिए: [अभाज्य](#def-b1-arith-prime) $p_1$ $q_1(q_2\cdots q_s)$ को [विभाजित करता है](#def-b1-arith-divides), अतः यूक्लिड की प्रमेयिका से या तो $p_1 \mid q_1$ या $p_1 \mid q_2\cdots q_s$; दोहराने पर $p_1$ किसी $q_j$ को [विभाजित करता है](#def-b1-arith-divides)। पर $q_j$ [अभाज्य](#def-b1-arith-prime) है और $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 (मूल्यांकन).**

[अभाज्य](#def-b1-arith-prime) $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$ को संतुष्ट करता है। [महत्तम समापवर्तक](#thm-b1-arith-gcd) का सूत्र: कसौटी से पूर्णांक $d
= \prod p^{\min}$ दोनों को [विभाजित करता है](#def-b1-arith-divides), और प्रत्येक उभयनिष्ठ भाजक $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 .
$$

सार: गुणात्मक प्रश्न (वर्ग, घन, भाजक, [महत्तम समापवर्तक](#thm-b1-arith-gcd), लघुत्तम समापवर्त्य) घातांक सदिशों $(v_2, v_3, v_5, \dots)$ पर *निर्देशांक-दर-निर्देशांक* प्रश्न बन जाते हैं — और अद्वितीय गुणनखंडन ठीक यही [कथन](https://one-course.com/books/math/3/hi/chapter/1-logic-sets-and-maps#def-b1-logic-statement) है कि ये निर्देशांक विद्यमान और सुपरिभाषित हैं।

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

**परिभाषा 6.18.**

$n \in \N^*$ के लिए: $a \equiv b \pmod n$ जब $n \mid a -
b$। यह ऐसा [तुल्यता संबंध](https://one-course.com/books/math/3/hi/chapter/1-logic-sets-and-maps#def-b1-logic-equiv) है जो योग और गुणन के अनुकूल है: यदि $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](#exo-b1-arith-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](#ex-b1-arith-pseudoprime) वाला छद्म-अभाज्य पाठ है: [सर्वांगसमता](#def-b1-arith-congruence) की जाँच खंडन करती है, प्रमाणित नहीं करती।

**प्रतिज्ञप्ति 6.20 (nnn के सापेक्ष व्युत्क्रमणीयता).**

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

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

**उदाहरण 6.21 (262626 के सापेक्ष 777 का प्रतिलोम).**

चूँकि $\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$। प्रतिलोम हाथ में होने पर कोई भी [सर्वांगसमता](#def-b1-arith-congruence) $7x \equiv c \pmod{26}$ एक ही गुणा में हल हो जाती है: $x \equiv 15c$। यही यांत्रिक प्रतिलोमन मापांकी अंकगणित का परिश्रमी घोड़ा है — और [टिप्पणी 6.27](#rem-b1-arith-whereused) में उल्लिखित सार्वजनिक-कुंजी प्रोटोकॉलों का भी, जहाँ [मापांक](https://one-course.com/books/math/3/hi/chapter/3-complex-numbers#def-b1-complex-field) सैकड़ों अंकों के होते हैं पर कलनविधि ठीक यही है।

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

$12x \equiv 8 \pmod{20}$ हल कीजिए। यहाँ $\gcd(12, 20) = 4$, अतः $12$ $20$ के सापेक्ष व्युत्क्रमणीय नहीं है — फिर भी समीकरण साधा जा सकता है। [सर्वांगसमता](#def-b1-arith-congruence) कहती है $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$ के सापेक्ष *चार* वर्ग, जो [महत्तम समापवर्तक](#thm-b1-arith-gcd) से मेल खाते हैं। (यदि दायाँ पक्ष $4$ से विभाज्य न होता, मान लीजिए $12x \equiv 6
\pmod{20}$, तो कोई हल होता ही नहीं: बायाँ पक्ष सदा $\equiv 0 \pmod 4$ रहता है।) व्यापक आकार: $ax \equiv b \pmod n$ तभी हल हो सकता है जब $\gcd(a, n)
\mid b$, और तब उसके ठीक $\gcd(a, n)$ हल-वर्ग होते हैं — सब कुछ [महत्तम समापवर्तक](#thm-b1-arith-gcd) से भाग दीजिए और प्रतिलोम लीजिए।

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

मान लीजिए $p$ [अभाज्य](#def-b1-arith-prime) है। प्रत्येक $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$ के लिए [द्विपद गुणांक](https://one-course.com/books/math/3/hi/chapter/2-counting#def-b1-counting-objects) $\binom pk =
\frac{p!}{k!(p-k)!}$ $p$ से विभाज्य है: वस्तुतः $k!\,(p-k)!\, \binom pk =
p!$ और $p$ $p!$ को [विभाजित करता है](#def-b1-arith-divides) पर $k!(p-k)!$ से [सहअभाज्य](#cor-b1-arith-bezout) है (सभी गुणनखंड $< 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](#prop-b1-arith-invmod))। ∎

**उदाहरण 6.24 (फर्मा का विलोम विफल है: 341341341).**

फर्मा की लघु प्रमेय एक सस्ता *भाज्यता* परीक्षण देती है: यदि $n$ से [सहअभाज्य](#cor-b1-arith-bezout) किसी $a$ के लिए $a^{n-1} \not\equiv 1 \pmod n$, तो $n$ [अभाज्य](#def-b1-arith-prime) नहीं है। क्या यह परीक्षण अभाज्यता प्रमाणित भी कर सकता है? नहीं: $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](#rem-b1-arith-whereused) के बड़े अभाज्यों को प्रमाणित करते हैं। उपदेश: निहितार्थ और उसका विलोम अलग-अलग जीवन जीते हैं ([टिप्पणी 1.10](https://one-course.com/books/math/3/hi/chapter/1-logic-sets-and-maps#rem-b1-logic-pitfalls)), प्रमेयों के लिए भी।

**उदाहरण 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 (अंकगणित की सामान्य भूलें).**

1. *[सर्वांगसमता](#def-b1-arith-congruence) में भाग देना।* $ac \equiv bc \pmod n$ से $a \equiv  b$ तब तक *नहीं* निकाला जा सकता जब तक $\gcd(c, n) = 1$ न हो: $6 \equiv  2 \pmod 4$ , पर $3 \not\equiv 1 \pmod 4$ । सही व्यापक नियम [मापांक](https://one-course.com/books/math/3/hi/chapter/3-complex-numbers#def-b1-complex-field) को भी भाग देता है: $ac \equiv bc \pmod n \iff a \equiv b \pmod{n/\gcd(c,n)}$ ।
2. *यूक्लिड की प्रमेयिका का दुरुपयोग।* $a \mid bc$ से $a \mid b$ या $a \mid c$ केवल तभी निकलता है जब $a$ *[अभाज्य](#def-b1-arith-prime)* हो (या किसी एक गुणनखंड से [सहअभाज्य](#cor-b1-arith-bezout) ): $6 \mid 4 \times 9$ , फिर भी $6$ किसी भी गुणनखंड को विभाजित नहीं करता।
3. *[सहअभाज्य](#cor-b1-arith-bezout) होना संबंध है, गुणधर्म नहीं।* “ $8$ और $9$ [सहअभाज्य](#cor-b1-arith-bezout) हैं” सत्य है, यद्यपि इनमें से कोई [अभाज्य](#def-b1-arith-prime) नहीं है; “जोड़ों में [सहअभाज्य](#cor-b1-arith-bezout) ” “समग्र रूप से [सहअभाज्य](#cor-b1-arith-bezout) ” से प्रबल है ( $\gcd(6, 10, 15) = 1$ , पर कोई युग्म [सहअभाज्य](#cor-b1-arith-bezout) नहीं)।
4. *घातांक $n$ के सापेक्ष नहीं रहते।* $a^k \bmod n$ में घातांक केवल $a$ की *कोटि* के सापेक्ष घटाया जा सकता है (उदाहरणार्थ $p - 1$ , जब फर्मा लागू हो), कभी $n$ के सापेक्ष नहीं: $2^{10} \bmod 11$ $1$ है, $2^{10 \bmod 11} = 2^{10}$ नहीं — जो घटाव काम करता है वह [उदाहरण 6.25](#ex-b1-arith-congruences) वाला है।

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

यह अध्याय जितना औज़ार-संदूक है उतना ही एक आदर्श भी। पूरी शृंखला — यूक्लिडीय भाग, [महत्तम समापवर्तक](#thm-b1-arith-gcd), बेज़ू, गाउस, अद्वितीय गुणनखंडन — [अध्याय 8](https://one-course.com/books/math/3/hi/chapter/8-polynomials#ch-b1-poly) में बहुपदों के लिए अक्षरशः दोहराई जाती है, जहाँ निरपेक्ष मान की भूमिका “घात” निभाती है; दोनों अध्यायों को साथ-साथ रखकर देखना दोनों को समझने का सर्वोत्तम उपाय है। सर्वांगसमताओं का कलन [अध्याय 7](https://one-course.com/books/math/3/hi/chapter/7-algebraic-structures#ch-b1-structures) में वलय $\Z/n\Z$ बन जाता है, जिसके व्युत्क्रमणीय अवयव ([प्रतिज्ञप्ति 6.20](#prop-b1-arith-invmod)) इकाई-समूह का पहला अतुच्छ उदाहरण बनाते हैं। मूल्यांकन नीचे दी गई सप्ताहांत समस्या में (लजांद्र का सूत्र) लौटते हैं और [अध्याय 10](https://one-course.com/books/math/3/hi/chapter/10-real-numbers#ch-b1-reals) की अपरिमेयता की उपपत्तियों को शक्ति देते हैं। इस खंड से आगे, $n$ के सापेक्ष बेज़ू प्रतिलोमन सार्वजनिक-कुंजी गूढ़लेखन का इंजन है, और फर्मा की लघु प्रमेय उन अभाज्यता परीक्षणों की पितामही है जो वहाँ प्रयुक्त बड़े अभाज्यों को प्रमाणित करते हैं।

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

अलग-अलग प्रमेयों से पीछे हटकर इस अध्याय की वास्तुकला देखिए: एक औज़ार (यूक्लिडीय भाग) ने एक वर्गीकरण ($n\Z$ उपसमूह) दिया, उसने एक अस्तित्व प्रमेय ([महत्तम समापवर्तक](#thm-b1-arith-gcd), बेज़ू) दी, उसने एक विभाज्यता-कलन (गाउस) दिया, और उसने अद्वितीय गुणनखंडन — हर मंज़िल केवल अपने नीचे वाली पर टिकी हुई। यही भवन इस खंड में दो बार और, भिन्न भूतलों पर, खड़ा किया जाएगा: [अध्याय 8](https://one-course.com/books/math/3/hi/chapter/8-polynomials#ch-b1-poly) में, जहाँ आकार से भाग की जगह घात से भाग आ जाता है और ऊपर का सब कुछ *अक्षरशः* दोहराता है; और लघु रूप में [अध्याय 7](https://one-course.com/books/math/3/hi/chapter/7-algebraic-structures#ch-b1-structures) के हर $\Z/n\Z$ के भीतर, जहाँ व्युत्क्रमणीयता के प्रश्न (इस अध्याय के [प्रतिज्ञप्ति 6.20](#prop-b1-arith-invmod)) वलयों और क्षेत्रों के विषय में संरचनात्मक [कथन](https://one-course.com/books/math/3/hi/chapter/1-logic-sets-and-maps#def-b1-logic-statement) बन जाते हैं। किसी तर्क को “$\Z$-वाला तर्क, प्रतिरोपित” के रूप में पहचान लेना उन अध्यायों को सीखने का सबसे तेज़ उपाय है — और बीजगणित की मूल आदत का पहला स्वाद, अर्थात् वस्तुओं के बदले *अभिगृहीतों* के विषय में प्रमेय सिद्ध करना।

![पास्कल त्रिभुज की 0 से 7 तक की पंक्तियाँ, जिनमें विषम प्रविष्टियाँ भरी हुई हैं: पंक्ति n में उनकी संख्या 2s_2(n) है, जहाँ s_2(n) n के द्विआधारी लेखन में इकाइयों की संख्या है (पंक्तियाँ 1, 2, 4: दो विषम प्रविष्टियाँ; पंक्ति 7 = (111)_2: सभी आठ)। यह स्वसमरूप प्रतिरूप — हर “विषमों का त्रिभुज” अपनी दो प्रतियाँ जनता है — चित्र रूप में कुमर की प्रमेय है, जो नीचे दी गई सप्ताहांत समस्या में सिद्ध की गई है।](https://one-course.com/images/onecourse/chapters/math-3/b1-arith/fig-8546c89fa14c.svg)

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

## 6.5 अभ्यास

**अभ्यास 6.1 ★.**

[यूक्लिडीय कलनविधि](#met-b1-arith-euclid) से $\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$ में [विभाज्यता](#def-b1-arith-divides) के नियम सिद्ध कीजिए: कोई पूर्णांक $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](#prop-b1-arith-valuation) और $\min(\alpha,\beta) + \max(\alpha,\beta) = \alpha + \beta$ के मूल्यांकन-सूत्रों का प्रयोग कीजिए।)*

**हल — अभ्यास 6.5.**

प्रत्येक [अभाज्य](#def-b1-arith-prime) $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) .
$$

जिन दो धनात्मक पूर्णांकों का प्रत्येक [अभाज्य](#def-b1-arith-prime) पर मूल्यांकन समान हो, वे बराबर होते हैं ([प्रतिज्ञप्ति 6.16](#prop-b1-arith-valuation)), अतः $\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](#prop-b1-arith-valuation)); चयन स्वतंत्र हैं, अतः $\prod_i (\alpha_i +
1)$ भाजक हैं। $a$ के लिए: $(10+1)(4+1)(2+1) = 165$।

**अभ्यास 6.7 ★★.**

मूल्यांकनों का प्रयोग करके सिद्ध कीजिए कि प्रत्येक [अभाज्य](#def-b1-arith-prime) $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}.
$$

साथ ही सिद्ध कीजिए कि [सहअभाज्य](#cor-b1-arith-bezout) $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](#thm-b1-arith-gauss) (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](#exo-b1-arith-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](#exo-b1-arith-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$ का शेषफल है; फिर [यूक्लिडीय कलनविधि](#met-b1-arith-euclid) का अनुसरण कीजिए।*

**हल — अभ्यास 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)$ को [विभाजित करता है](#def-b1-arith-divides)। अतः $2^n - 1$ के सापेक्ष $\;2^m - 1 \equiv 2^r - 1$, और चूँकि $0
\leq 2^r - 1 < 2^n - 1$, यही यूक्लिडीय शेषफल *है*।

अतः युग्म $(2^m - 1, 2^n - 1)$ पर [यूक्लिडीय कलनविधि](#met-b1-arith-euclid), घातांक-दर-घातांक, $(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$ [अभाज्य](#def-b1-arith-prime) है। सिद्ध कीजिए कि

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

— इसके लिए $(p-1)!$ के प्रत्येक गुणनखंड को $p$ के सापेक्ष उसके प्रतिलोम के साथ युग्मित कीजिए और स्वयं से युग्मित होने वाले गुणनखंडों की पहचान कीजिए (पहले $x^2 \equiv 1 \pmod p$ हल कीजिए)। विलोम भी जाँचिए: यदि $n \geq 2$ [अभाज्य](#def-b1-arith-prime) नहीं है, तो $(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](#prop-b1-arith-invmod))। प्रत्येक $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$ रखिए।

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

**हल — अभ्यास 6.12.**

1. आगमन। $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 .$$
2. मान लीजिए $m < n$ और $d = \gcd(F_m, F_n)$ । (1) से $F_m$ $F_n - 2$ को [विभाजित करता है](#def-b1-arith-divides) , अतः $d$ $F_n$ और $F_n - 2$ दोनों को [विभाजित करता है](#def-b1-arith-divides) , इसलिए $2$ को भी। पर हर फर्मा संख्या विषम है, अतः $d = 1$ ।
3. प्रत्येक $F_n \geq 3$ का कोई [अभाज्य](#def-b1-arith-prime) भाजक $p_n$ है ( [प्रमेय 6.14](#thm-b1-arith-euclidprimes) का पहला पद)। यदि $m \neq n$ , तो $p_m  \neq p_n$ , क्योंकि कोई उभयनिष्ठ [अभाज्य](#def-b1-arith-prime) $\gcd(F_m, F_n) = 1$ को विभाजित करता। अतः [प्रतिचित्रण](https://one-course.com/books/math/3/hi/chapter/1-logic-sets-and-maps#def-b1-logic-map) $n \mapsto p_n$ $\N$ से अभाज्यों में [एकैकी](https://one-course.com/books/math/3/hi/chapter/1-logic-sets-and-maps#def-b1-logic-inj) है: [अभाज्य](#def-b1-arith-prime) संख्याएँ अनंत हैं।

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

**समस्या 6.1.**

$1000!$ के दशमलव लेखन के अंत में कितने शून्य आते हैं — और, इससे गहरे, $n!$ को, अथवा किसी [द्विपद गुणांक](https://one-course.com/books/math/3/hi/chapter/2-counting#def-b1-counting-objects) को, विभाजित करने वाली [अभाज्य](#def-b1-arith-prime) $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$ जोड़ते समय के *हासिलों* की गणना करता है। यह समस्या दोनों सिद्ध करती है, उन्हें संख्यात्मक रूप से एक-दूसरे के सामने जाँचती है, और चिरपरिचित परिणाम बटोरती है — अंत के शून्य, पास्कल त्रिभुज की सम-विषमता, और [अभाज्य संख्या](#def-b1-arith-prime) प्रमेय की दिशा में पहला परिबंध। आगे सर्वत्र $p$ [अभाज्य](#def-b1-arith-prime) है, $\floor{x}$ पूर्णांक भाग है, और $s_p(n)$ आधार $p$ में लिखी $n$ के अंकों का योग दर्शाता है।

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

1. अभ्यास: $10!$ संगणित कीजिए और अंत के शून्यों की संख्या पढ़िए; $v_2(10!)$ और $v_5(10!)$ प्रत्येक गुणनखंड $1, 2, \dots, 10$ के गुणनखंडन से सीधे संगणित कीजिए।
2. सिद्ध कीजिए कि $x \in \R$ और $n \in \N^*$ के लिए $\bigl\lfloor  \lfloor x \rfloor / n \bigr\rfloor = \lfloor x/n \rfloor$ ।
3. सिद्ध कीजिए कि सभी $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)$ हो तब समता।
4. दिखाइए कि $\intint1n$ में $m$ के गुणजों की संख्या $\lfloor n/m  \rfloor$ है।
5. *लजांद्र का सूत्र* सिद्ध कीजिए: प्रत्येक $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 — अंकीय रूप और अंत के शून्य।**

6. $v_5(1000!)$ और $v_2(1000!)$ संगणित कीजिए, और निष्कर्ष निकालिए: $1000!$ के अंत में कितने शून्य हैं?
7. लजांद्र के सूत्र का अंकीय रूप सिद्ध कीजिए: $n = \sum_i a_i p^i$ को आधार $p$ में लिखने पर, $$v_p(n!) = \frac{n - s_p(n)}{p - 1} .$$
8. $p = 2$ के लिए दो परिणाम: दिखाइए कि $2^n$ $n!$ को कभी विभाजित नहीं करता, और यह कि $2^{n-1}$ $n!$ को ठीक तभी [विभाजित करता है](#def-b1-arith-divides) जब $n$ $2$ की कोई घात हो।
9. न्यूनता का परिबंध दीजिए: दिखाइए $\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}$ जुड़ता जाता है।
10. मान लीजिए $Z(n) = v_5(n!)$ $n!$ के अंत के शून्यों की संख्या है। दिखाइए $Z(n) - Z(n-1) = v_5(n)$ , उससे निकालिए कि $Z$ मान $5$ को पूरी तरह छोड़ देता है ( $Z(24)$ और $Z(25)$ संगणित कीजिए), और सिद्ध कीजिए कि किसी भी क्रमगुणित के अंत में ठीक पाँच शून्य नहीं होते।

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

11. सिद्ध कीजिए कि सभी $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$ है।
12. *कुमर की प्रमेय* सिद्ध कीजिए: उस योग का $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$ का निरीक्षण कीजिए।)*
13. उससे $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](#thm-b1-arith-fermat) का मुख्य पद, फिर से प्राप्त।)
14. सिद्ध कीजिए कि $v_2\binom{2n}n = s_2(n)$ । उससे निकालिए कि केंद्रीय [द्विपद गुणांक](https://one-course.com/books/math/3/hi/chapter/2-counting#def-b1-counting-objects) सदा सम है, और यह कि $\binom{2n}n \equiv 2 \pmod 4$ ठीक तब जब $n$ $2$ की कोई घात हो।
15. वांडरमोंड सर्वसमिका ( [अभ्यास 2.7](https://one-course.com/books/math/3/hi/chapter/2-counting#exo-b1-counting-7) ) और प्रश्न 13 का प्रयोग करके दिखाइए कि प्रत्येक [अभाज्य](#def-b1-arith-prime) $p$ के लिए $\binom{2p}p \equiv 2  \pmod p$ ।
16. $v_3\binom{1000}{500}$ दो बार संगणित कीजिए: एक बार कुमर से (आधार $3$ में $500$ लिखिए और $500 + 500$ में हासिल गिनिए), और एक बार लजांद्र के अंकीय रूप से ( $s_3(500)$ और $s_3(1000)$ संगणित कीजिए); जाँचिए कि दोनों वही मान देते हैं।

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

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

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

22. ऐसा लघुतम $n$ खोजिए कि $n!$ के अंत में कम से कम $2026$ शून्य हों। *($Z(n) \approx n/4$ का आकलन कीजिए, फिर यथार्थ सूत्र से समायोजन कीजिए।)*
23. एक अंतिम प्रति-जाँच: दिखाइए कि $7$ $\binom{100}{50}$ को विभाजित *नहीं* करता — पहले $50$ को आधार $7$ में लिखकर और जाँचकर कि जोड़ $50  + 50$ में कोई हासिल नहीं है, फिर लजांद्र के सूत्र से $v_7(100!)$ और $v_7(50!)$ संगणित करके।
24. इस समस्या में ठीक कहाँ प्रयोग हुआ: (क) अद्वितीय गुणनखंडन; (ख) यूक्लिडीय भाग का वियोजन $n = p^k n_1 + n_0$ ; (ग) [अध्याय 2](https://one-course.com/books/math/3/hi/chapter/2-counting#ch-b1-counting) का कोई गणना-तर्क? प्रत्येक के लिए एक वाक्य।
25. एक छोटे अनुच्छेद में संश्लेषण: लजांद्र का सूत्र [विभाज्यता](#def-b1-arith-divides) के प्रश्न को अंकों के अंकगणित में बदल देता है, और कुमर की प्रमेय उत्तर को एक ही जोड़ के हासिलों से पढ़ लेती है — इस अनुवाद पर, प्रश्न 16 की जाँचों पर, और प्रश्न 21 का परिबंध अभाज्यों के विषय में जो संकेत देता है उस पर टिप्पणी कीजिए (पूरा [कथन](https://one-course.com/books/math/3/hi/chapter/1-logic-sets-and-maps#def-b1-logic-statement) , अर्थात् [अभाज्य संख्या](#def-b1-arith-prime) प्रमेय, इस खंड से बहुत परे है; इस अध्याय के औज़ार-संदूक का बहुपदीय अनुरूप [अध्याय 8](https://one-course.com/books/math/3/hi/chapter/8-polynomials#ch-b1-poly) है)।

**हल — समस्या 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$, अर्थात् वही [विभाज्यता](#def-b1-arith-divides) जो [प्रमेय 6.23](#thm-b1-arith-fermat) में प्रयुक्त हुई।

**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.** प्रत्येक [अभाज्य](#def-b1-arith-prime) $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](#prop-b1-arith-valuation) से $\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$ से नीचे [अभाज्य](#def-b1-arith-prime) कम होते, तो लघुत्तम समापवर्त्य इतना बड़ा नहीं हो सकता था: लघुत्तम समापवर्त्य की चरघातांकी वृद्धि अभाज्यों की प्रचुरता का परिमाणात्मक चिह्न है।

**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](#prop-b1-arith-valuation))। (ख) यूक्लिडीय भाग ने प्रश्न 2 की कटाई-सर्वसमिका दी और वह [विभाजन](https://one-course.com/books/math/3/hi/chapter/1-logic-sets-and-maps#thm-b1-logic-partition) $m = p^km_1 + m_0$ दिया जो हासिल को अलग कर देता है (प्रश्न 12)। (ग) गणना: $m$ के गुणजों की गणना (प्रश्न 4), अंक-चयन का गुणनफल (प्रश्न 18), और पंक्ति-योग का परिबंध $4^n \leq (2n+1)\binom{2n}n$ (प्रश्न 21) — ये सब [अध्याय 2](https://one-course.com/books/math/3/hi/chapter/2-counting#ch-b1-counting) की शैली के तर्क हैं।

**25.** लजांद्र “$n!$ को $p$ की कौन-सी घात विभाजित करती है” को आधार-$p$ के अंक-अंकगणित में बदल देता है; कुमर द्विपद गुणांकों के लिए उत्तर को एक ही जोड़ के हासिलों में सिकोड़ देता है — [विभाज्यता](#def-b1-arith-divides), जो विशाल संख्याओं का समग्र गुणधर्म लगती है, स्थानीय रूप से, अंक-दर-अंक, पढ़ ली जाती है। प्रश्न 16 इसका आदर्श है: हाथ से गिने हुए चार हासिल सैकड़ों अंकों वाली संख्या में $3$ की ठीक-ठीक घात निर्धारित कर देते हैं। और प्रश्न 21 दिखाता है कि यही विचार-मंडल गहरे जल को छू रहा है: $\operatorname{lcm}(1, \dots, 2n)$ के लिए चरघातांकी निम्न परिबंध [अभाज्य संख्या](#def-b1-arith-prime) प्रमेय की दिशा में पहला, पूर्णतः प्रारंभिक पद है, जिसकी उपपत्ति इस खंड से बहुत परे है। पूरा औज़ार-संदूक — भाग, [महत्तम समापवर्तक](#thm-b1-arith-gcd), मूल्यांकन — [अध्याय 8](https://one-course.com/books/math/3/hi/chapter/8-polynomials#ch-b1-poly) में बहुपदों के लिए फिर चलाया जाता है, जहाँ अंक-प्रसार का अनुरूप $(X - a)$ की घातों में प्रसार है।