विभाज्यता

विभाज्यता संख्या सिद्धांत का वास्तविक प्रारंभिक बिंदु है, क्योंकि यह पूर्णांकों को संरचना वाले एक तंत्र में बदल देती है: अब आप संख्याओं को “मात्राएँ” नहीं, बल्कि ऐसे घटक मानते हैं जो एक-दूसरे के साथ मेल खाते हैं या नहीं। एक ही संरचना, a\mid b, के माध्यम से आप सरलीकरण और गुणनखंडन के मानदंडों से लेकर यूक्लिड एल्गोरिथ्म जैसी कुछ प्रक्रियाओं के मूल तक सब कुछ व्यक्त कर सकते हैं, जो बड़े संख्याओं के साथ भी कुछ ही सेकंड में महत्तम समापवर्तक निकालना संभव बनाता है। इसके अतिरिक्त, यह उन विचारों का तकनीकी आधार है जो अनुप्रयुक्त गणित और संगणन में बार-बार प्रकट होते हैं: सर्वांगसमताएँ, मॉड्यूलर अंकगणित, सत्यापन, कोड, और (आगे चलकर) क्रिप्टोग्राफी। विभाज्यता में दक्ष होना, मूलतः, पूर्णांकों में अदृश्य प्रतिरूपों का पता लगाना और उन्हें ऐसे प्रक्रियाओं में रूपांतरित करना सीखना है जो हमेशा काम करती हैं।

अधिगम उद्देश्य
इस अपunte के अंत में छात्र सक्षम होगा:

1. पूर्णांकों के बीच विभाज्यता संबंध को समझना।
2. विभाज्यता की परिभाषा और उसके गुणों को समझना।
3. विभाज्यता से संबंधित परिणामों और प्रमेयों की गणितीय सिद्धियाँ विकसित करना।

विषय-सूची
विभाज्यता की परिभाषा
विभाज्यता के मौलिक गुण
प्रस्तावित अभ्यास

विभाज्यता की परिभाषा

“a, b को विभाजित करता है” का अनौपचारिक विचार तब सटीक हो जाता है जब हम उसे पूर्णांकों के बीच एक संबंध के रूप में व्यक्त करते हैं। हम कहेंगे कि एक पूर्णांक a एक पूर्णांक b को विभाजित करता है, यदि b को a के एक ठीक-ठीक गुणज के रूप में लिखा जा सके। यह परिभाषा पूरे अपunte का आधार है, क्योंकि यह “ठीक से फिट होता है” जैसी बातों को एक सत्यापनीय मानदंड में बदल देती है।

परिभाषा. मान लें a,b\in\mathbb{Z} जहाँ a\neq 0। हम कहते हैं कि a b को विभाजित करता है, और लिखते हैं a\mid b, यदि और केवल यदि कोई पूर्णांक k\in\mathbb{Z} ऐसा हो कि b=ka। अन्यथा, हम लिखते हैं a\nmid b।

a\mid b := (\exists k \in \mathbb{Z})(b = ka )

इस परिभाषा में, संख्या k को विभाज्यता से संबद्ध भागफल (या गुणक) कहा जाता है। उदाहरण के लिए, यह कहना कि 6\mid 42 इसके समतुल्य है कि कोई k\in\mathbb{Z} ऐसा मौजूद है कि 42=6k; इस स्थिति में, k=7 लेना पर्याप्त है।

यह ध्यान में रखना महत्वपूर्ण है

• शर्त a\neq 0 अनिवार्य है। क्योंकि यदि हम a=0 को अनुमति देने का प्रयास करें, तो विभाज्यता की शर्त यह माँगेगी कि कोई k\in\mathbb{Z} ऐसा हो कि b=0\cdot k। परंतु 0\cdot k=0 हर k के लिए होता है, इसलिए एकमात्र संभावना b=0 ही होगी। उस स्थिति में, संबंध द्वारा “निर्धारित” कोई k नहीं होगा, क्योंकि कोई भी k\in\mathbb{Z} 0=0\cdot k को संतुष्ट करता है। दूसरे शब्दों में, अनौपचारिक अभिव्यक्ति k=b/a k=0/0 बन जाती है, जो परिभाषित नहीं है। इस विकृति से बचने के लिए (जहाँ भागफल की धारणा अर्थपूर्ण नहीं रहती), a\neq 0 की माँग की जाती है। इसी कारण 0\mid b संबंध को वैध नहीं माना जाता।
• इसके विपरीत, a\mid 0 हर a\in\mathbb{Z} के लिए सत्य है जहाँ a\neq 0, क्योंकि k=0 लेना पर्याप्त है और 0=a\cdot 0 सत्य हो जाता है।

इस परिभाषा से एक समतुल्यता निकलती है जिसका हम बार-बार उपयोग करेंगे: यह कहना कि a\mid b उसी के बराबर है कि b a के पूर्णांक गुणजों के समुच्चय का सदस्य है, अर्थात b\in a\mathbb{Z}, जहाँ a\mathbb{Z}=\{ak:\,k\in\mathbb{Z}\}। इसे लिखने का यह तरीका इस बात पर बल देता है कि विभाज्यता कोई “चाल” नहीं, बल्कि \mathbb{Z} के भीतर अत्यंत संरचित उपसमुच्चयों का वर्णन करने का एक उपाय है।

विभाज्यता के मूलभूत गुण

• परावर्तिता: a\mid a.
  प्रमाण:

  \begin{array}{rll} (1)&\vdash a=ka \leftrightarrow k=1 &\text{; $\mathbb{Z}$ में गुणनात्मक एकक}\\ (2)&\vdash(\exists k \in \mathbb{Z})(a=ka) &\text{; (1) से अस्तित्वात्मक-परिचय}\\ (3) &\vdash a \mid a &\text{; विभाज्यता की परिभाषा (2)} \\ &\blacksquare & \end{array}

• संक्रामकता: यदि a\mid b और b\mid c, तो a\mid c।

  प्रमाण:

  \begin{array}{rll} (1)& \{a\mid b , b\mid c\} \vdash (\exists k_1\in\mathbb{Z})(b=k_1a) &\text{; विभाज्यता की परिभाषा, पूर्वधारणा}\\ (2)& \{a\mid b , b\mid c\} \vdash (\exists k_2\in\mathbb{Z})(c=k_2b) &\text{; विभाज्यता की परिभाषा, पूर्वधारणा}\\ (3)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(b=k_1a \wedge c=k_2b) &\text{; $\exists$-संकुचन(1,2)}\\ (4)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(k_2b=k_1k_2a \wedge c=k_2b) &\text{; (3) से}\\ (5)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})( c=k_1k_2a) &\text{; (4) से}\\ &\text{मात्रक के भीतर बीजगणित}& \\ (6)& \{a\mid b , b\mid c\} \vdash (\exists k\in\mathbb{Z})( c=ka) &\text{; (5) से}\\ &\text{गुणन के लिए $\mathbb{Z}$ की बंदता}& \\ (7)& \{a\mid b , b\mid c\} \vdash a\mid c &\text{; विभाज्यता की परिभाषा (6)}\\ (8)& \vdash (a\mid b \wedge b\mid c) \rightarrow a\mid c &\text{; $\wedge$-TD(7)}\\ &\blacksquare& \end{array}

• योग और घटाव के साथ संगतता: यदि a\mid b और a\mid c, तो a\mid (b+c) और a\mid (b-c)।
  प्रमाण:

  \begin{array}{rll} (1)&\{a\mid b, a\mid c\}\vdash (\exists k_1 \in \mathbb{Z})(b=k_1 a) &\text{; विभाज्यता की परिभाषा, पूर्वधारणा}\\ (2)&\{a\mid b, a\mid c\}\vdash (\exists k_2 \in \mathbb{Z})(c=k_2 a) &\text{; विभाज्यता की परिभाषा, पूर्वधारणा}\\ (3)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b=k_1 a \wedge c=k_2 a) &\text{; $\exists$-संकुचन(1,2)}\\ (4)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b+c= (k_1+k_2)a) &\text{; (3) से}\\ &\text{मात्रक के भीतर बीजगणित.}& \\ (5)&\{a\mid b, a\mid c\}\vdash (\exists k \in \mathbb{Z})(b+c= ka) &\text{; (4) से}\\ &\text{योग के लिए $\mathbb{Z}$ की बंदता.}& \\ (6)&\{a\mid b, a\mid c\}\vdash a\mid (b+c) &\text{; विभाज्यता की परिभाषा (5)}\\ (7)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b+c) &\text{; $\wedge$-TD(6)}\\ (8)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b-c= (k_1-k_2)a) &\text{; (3) से}\\ &\text{मात्रक के भीतर बीजगणित.}& \\ (9)&\{a\mid b, a\mid c\}\vdash (\exists \overline{k} \in \mathbb{Z})(b-c= \overline{k}a) &\text{; (8) से}\\ &\text{घटाव के लिए $\mathbb{Z}$ की बंदता.}& \\ (10)&\{a\mid b, a\mid c\}\vdash a\mid (b-c) &\text{; विभाज्यता की परिभाषा (9)}\\ (11)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b-c) &\text{; $\wedge$-TD(10)}\\ (12)&\vdash (a\mid b \wedge a\mid c) \rightarrow \left(a\mid (b+c) \wedge a\mid (b-c)\right) &\text{;$\wedge$-परिणाम में परिचय(7,11) }\\ &\blacksquare& \end{array}

• गुणन के साथ संगतता: यदि a\mid b, तो a\mid (bc) सभी c\in\mathbb{Z} के लिए।
  प्रमाण:

  \begin{array}{rll} (1)& \{a\mid b\}\vdash (\exists k\in\mathbb{Z})(b=ka) &\text{; विभाज्यता की परिभाषा, पूर्वधारणा}\\ (2)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists k\in\mathbb{Z})(cb=cka) &\text{; (1) से, $\forall$-परिचय (c मनमाना)}\\ &\text{ में बीजगणित }\mathbb{Z}\text{ अस्तित्वात्मक मात्रक के भीतर.}&\\ (3)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists \overline{k}\in\mathbb{Z})(cb=\overline{k}a) &\text{; (2) से, बंदता: }\overline{k}=ck\\ (4)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; विभाज्यता की परिभाषा (3)}\\ (5)& \vdash a\mid b \rightarrow \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; TD(4)}\\ &\blacksquare& \end{array}

याद रखें कि \text{ } टैगों के भीतर के पाठों का अनुवाद करें।

प्रमेय: भाजक की सीमा

यदि b\neq 0 और a\mid b, तो |a|\le |b|।

प्रमाण:

\begin{array}{rll} (1) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash b \neq 0 & \text{; पूर्वधारणा} \\ (2) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (b=ka) & \text{; विभाज्यता की परिभाषा, पूर्वधारणा} \\ (3) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (|b|=|k||a|) & \text{; परम मान का गुण, (2) से} \\ (4) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (k\neq 0 \wedge |b|=|k||a|) & \text{; (1,3) से} \\ (5) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (1\le |k| \wedge |b|=|k||a|) & \text{; (4) से, यदि }k\neq 0\Rightarrow |k|\ge 1 \\ (6) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash |a|\le |b| & \text{; (5) से} \\ &\blacksquare& \end{array}

प्रस्तावित अभ्यास

1. दिखाएँ कि प्रमेय “भाजक की सीमा” अनिवार्य रूप से सत्य नहीं होता यदि b=0
2. एक समुच्चय A तथा उस पर एक संबंध \rho पर विचार करें। यदि तत्व x,y\in A ऐसे हों कि x का y से \rho के माध्यम से संबंध हो, तो इसे x\rho y लिखा जाता है। संबंध \rho को A पर आंशिक क्रम कहा जाता है यदि:

   a)(\forall x\in A) (x\rho x),
   b) (\forall x,y\in A) ( (x\rho y \wedge y\rho x) \rightarrow x=y)
   c) (\forall x,y,z\in A) ( (x\rho y \wedge y\rho z) \rightarrow x\rho z)।

   सिद्ध कीजिए कि विभाज्यता का संबंध पूर्णांकों पर एक आंशिक क्रम संबंध है।

3. प्रेरण द्वारा सिद्ध करें कि यदि a\mid b_1, a\mid b_2, \cdots, a\mid b_n, तो a\mid \sum_{i=1}^n b_i x_i किसी भी समुच्चय \{x_i\}_{i=1}^n \subset \mathbb{Z} के लिए। इसके अतिरिक्त सिद्ध करें कि यदि a\mid b_i, जहाँ i\in \{1,2,3,\cdots, n\} और c को उन b_i के रैखिक संयोजन के रूप में लिखा जा सकता है, तो a\mid c।
4. यदि a\neq 0, दिखाएँ कि समुच्चय \{x\;:\; d\mid a\} एक सीमित समुच्चय है।
5. एक नियत n\in\mathbb{Z}^+ पर विचार करें, और मान लें

   S=\{d\,:\,d\in\mathbb{Z}^+ \wedge d\mid n\}

   सिद्ध करें:

   1. d\in S \leftrightarrow n/d\in S
   2. यदि S के तत्त्व आरोही क्रम में रखे जाएँ: 1=d_1 \lt d_2 \lt \cdots \lt d_t =n, तो अनुरूप तत्त्व n\mid d_i जहाँ i \in \{1,2,\cdots, t\} अवरोही क्रम में होंगे।
6. मान लें कि a,b\in\mathbb{Z}^+ और ab=c। सिद्ध करें कि \min\{a,b\}\le \sqrt{c}।
7. एक पूर्णांक n को सम कहा जाता है यदि 2\mid n, तथा विषम कहा जाता है यदि 2\nmid n। सिद्ध करें कि निम्न की योग और अंतर:
   1. दो सम संख्याओं का परिणाम एक सम संख्या होता है।
   2. दो विषम संख्याओं का परिणाम एक सम संख्या होता है।
   3. एक सम और एक विषम का परिणाम एक विषम संख्या होता है।
8. यदि n एक विषम संख्या है जो \pm 1 से भिन्न है, सिद्ध करें कि n दो क्रमागत सम संख्याओं को विभाजित नहीं कर सकता।
9. मान लें a,b,n\in\mathbb{Z} ऐसे कि |a-b|\lt |n|। सिद्ध करें कि n न तो a को और न ही b को विभाजित कर सकता है।
10. मान लें कि a\in\mathbb{Z}। सिद्ध करें कि:
    1. (\forall n \in \mathbb{Z})(a\mid n) \leftrightarrow a=\pm 1
    2. (\forall n \in \mathbb{Z})(n\mid a) \leftrightarrow a=0
11. मान लें a,b,c\in\mathbb{Z} तथा c\neq 0। दिखाएँ कि ac\mid bc से यह निष्कर्ष निकलता है कि a\mid b