परिचय


गणितीय ब्लॉग "गणिताञ्जलि" पर आपका स्वागत है ! $\ast\ast\ast\ast\ast$ प्रस्तुत वेबपृष्ठ गणित के विविध विषयों पर सुरुचिपूर्ण व सुग्राह्य रचनाएँ हिंदी में सविस्तार प्रकाशित करता है.$\ast\ast\ast\ast\ast$ गणिताञ्जलि : शून्य $(0)$ से अनंत $(\infty)$ तक ! $\ast\ast\ast\ast\ast$ इस वेबपृष्ठ पर उपलब्ध लेख मौलिक व प्रामाणिक हैं.

नवीनतम प्रविष्टियाँ सीधे आपके ई-मेल इनबॉक्स में...नीचे अपना ई-मेल पता प्रविष्ट कर सत्यापित करें !

2. विभाज्यता - सिद्धांत (The Theory of Divisibility)

प्रकाशन तिथि : 27 मार्च 2015
**************************************

2.1. विभाजन - कलन विधि (Division Algorithm)

इस अध्याय में हम पूर्णांकों के विभाजन से संबंधित सिद्धांतों और गुणधर्मों के विषय में विस्तार से चर्चा करेंगे |  इन सिद्धांतों में एक आधारभूत सिद्धांत "विभाजन - कलन विधि" है | इस विधि से प्रायः हम सब परिचित है : यदि एक पूर्णांक $a$ को किसी धनपूर्णांक $b$ से विभाजित किया जाए, तो शेषफल (remainder) सदैव $b$ से कम होता है | उदाहरण के लिए,  यदि $13$ को $5$ से विभाजित किया जाए, तो हमें शेषफल $3$ प्राप्त होता है और इसे हम इस प्रकार व्यक्त करते हैं :
\[13 = 5 \times 2 + 3.\]
यहाँ हम संख्या $13$ को  भाज्य (dividend), संख्या $5$ को भाजक (divisor), संख्या $2$ को भागफल (quotient) और संख्या $3$ को शेषफल या शेष कहते हैं | अधिक व्यापक रूप में, यदि भाज्य $a$ को भाजक $b$ से विभाजित करने पर भागफल और शेष क्रमशः $q$ और $r$ हों, तो हम लिखते हैं :
\[a = bq + r.\]
क्या ऐसा करना किन्हीं भी संख्या - युग्म $(a, b)$ के लिए संभव है ? हमारा अंतर्ज्ञान कहता है कि ऐसा करना सदैव संभव है, यदि भाजक $b$ धनात्मक हो | निम्नलिखित प्रमेय इसी तथ्य को व्यक्त करता है |
 
प्रमेय 2.1 (विभाजन - कलन विधि). यदि $a$ और $b$ दो पूर्णांक हों, और $b > 0$, तो अद्वितीय पूर्णांकों $q$ और $r$ का अस्तित्व होता है, जिससे कि 
\[a = bq + r, ~ 0 \leq r < b.\]
पूर्णांकों $q$ और $r$ को क्रमशः भागफल और शेषफल कहा जाता है |

उपपत्ति: 
सर्वप्रथम हम एक समुच्चय $S$ परिभाषित करते हैं:
\[S := \{a - xb : x \in \mathbb{Z}~\text{और}~ a - xb \geq 0.\}\]
 चुँकि $b \geq 1$, इसलिए $|a|b \geq |a|$. अतः 
\[a - (-|a|)b = a + |a|b \geq a + |a| \geq 0.\] 
इस प्रकार $x = -|a|$ के लिए $a - xb \in S$ प्राप्त होता है | अतः $S$ एक अरिक्त समुच्चय है | इसलिए, सुक्रमण सिद्धांत (well ordering principle) के अनुसार, समुच्चय $S$ में एक निम्नतम अवयव है | मान लीजिए यह अवयव $r$ है | अब समुच्चय $S$ की परिभाषा से, एक पूर्णांक $q$ का अस्तित्व है, जिससे कि 
\[r = a - qb \geq 0.\]
हम दिखाएँगे कि $r < b$. मान लीजिए कि $r \geq b$, तब 
\[a - (q+1)b = (a - qb) - b = r -b \geq 0,\]
और इसीलिये $a - (q +1)b \in S$. परन्तु $a - (q + 1)b = r - b < r$, जो इस तथ्य का अंतर्विरोध करता है कि $r$ समुच्चय $S$ का निम्नतम अवयव है | अतः $r < b$ और $a  = bq + r$, जहाँ $0 \leq r < b$.
            आगे हम दिखाएँगे कि $q$ और $r$ अद्वितीय हैं | मान लीजिए कि 
\[a = bq + r = bq' + r',\]
जहाँ $0 \leq r < b$ और $0 \leq r' < b$. तब $r - r' = b(q - q')$. यदि $q' \neq q$, तो $|q' -q| \geq 1$, इसलिए $|r - r'| \geq |b| = b$, जो असंभव है, क्योंकि $|r - r'| < b$. अतः $q' =q$, और इसीलिये $r' =r$. इस प्रकार हमारी उपपत्ति पूर्ण होती है |


उपप्रमेय 2.2 ( व्यापक विभाजन - कलन विधि). यदि $a$ और $b$ दो पूर्णांक हों, और $b \neq 0$, तो अद्वितीय पूर्णांकों $q$ और $r$ का अस्तित्व होता है जिससे कि 
\[a = bq + r, 0 \leq r < |b|.\]

उपपत्ति: 
यदि $b > 0$, तो उपप्रमेय उपरोक्त प्रमेय से सत्यापित हो जाता है | अतः मान लीजिए कि $b < 0$. तब $|b| > 0$. इसलिए उपरोक्त प्रमेय के अनुसार, ऐसे पूर्णांकों $q'$ और $r$ का अस्तित्व होता है, जिससे कि
\[a = |b|q' + r, 0 \leq r < |b|.\]
अब यदि हम $q = -q'$ लें, तो हमें प्राप्त होता है:
\[a = qb + r, 0 \leq r < |b|.\]
इस प्रकार हमारी उपपत्ति पूर्ण होती है |

2.2. महत्तम समापवर्तक (Greatest Common Divisor)

परिभाषा 2.3 ( विभाज्यता). एक पूर्णांक $b$ एक शून्येतर पूर्णांक $a$ से विभाज्य (divisible) होता है, यदि एक ऐसे पूर्णांक $c$ का अस्तित्व हो, जिससे कि $b = ac$. इस स्थिति में हम $a \mid b$ लिखते हैं और कहते हैं - संख्या $a$ संख्या $b$ को विभाजित करता है या संख्या $b$ संख्या $a$ से विभाज्य है | अन्यथा, हम $a \nmid b$ लिखते हैं, और कहते हैं कि संख्या $a$ संख्या $b$ को विभाजित नहीं करता है या संख्या $b$ संख्या $a$ से विभाज्य नहीं है |

           उदाहरण के लिए, $5 \mid(-15)$, क्योंकि $-15 = 5\cdot(-3)$. परन्तु $5 \nmid 13$, क्योंकि किसी ऐसी संख्या $c$ का अस्तित्व नहीं है, जिससे कि $13 = 5c$ हो |
  
प्रमेय 2.4 ( विभाज्यता - गुणधर्म). पूर्णांकों $a \neq 0, b$ और $c$ के लिए निम्नलिखित कथन सत्य हैं: 
(a) $a \mid 0, 1 \mid a, a \mid a$.
(b) $a \mid 1$ यदि और केवल यदि $a = \pm 1$.
(c) यदि  $a \mid b$ और $c \mid d$, तो $ac \mid bd$.
(d) यदि $a \mid b$ और $b \mid c$, तो $a \mid c$.
(e) $a \mid b$ और $b \mid a$ यदि और केवल यदि $a = \pm b$.
(f) यदि $a \mid b$ और $b \neq 0$, तब $|a| \leq |b|$.
(g) यदि $a \mid b$ और $a \mid c$, तो सभी संख्याओं $x$ और $y$ के लिए, $a \mid (bx + cy)$.

उपपत्ति: 
इन तथ्यों की उपपत्तियाँ आसान हैं |

मान लीजिए $a$ और $b$ स्वेच्छ पूर्णांक हैं | एक पूर्णांक $d$ को $a$ और $b$ का समापवर्तक (common factor) या सार्वभाजक (common divisor) कहते हैं, यदि $d \mid a$ और $d \mid b$. क्योंकि $1$ सभी पूर्णांकों को विभाजित करता है, यह $a$ और $b$ का सार्वभाजक है | इस प्रकार $a$ और $b$ के धनात्मक सार्वभाजकों का समुच्चय अरिक्त है | अब, क्योंकि प्रत्येक धन पूर्णांक $0$ को विभाजित करता है, अतः यदि $a = b =0$ हों, तो प्रत्येक धन पूर्णांक $a$ और $b$ का सार्वभाजक होगा | इस प्रकार, इस स्थिति में $a$ और $b$ के धन सार्वभाजकों की संख्या अनंत है | परन्तु,  यदि  $a$ और $b$ में कम से कम एक पूर्णांक शून्येतर (nonzero) हो, तो इनके धन सार्वभाजकों की संख्या परिमित होगी | इन सार्वभाजकों में एक महत्तम संख्या होती है, जिसे हम $a$ और $b$ का महत्तम समापवर्तक (greatest common factor) या महत्तम सार्वभाजक (greatest common divisor) कहते हैं | इस प्रकार हम निन्लिखित परिभाषा देते हैं:
    
परिभाषा 2.5 (महत्तम सार्वभाजक). मान लीजिए $a$ और $b$ पूर्णांक हैं, जिनमें कम से कम एक पूर्णांक शून्येतर है | संख्याओं $a$ और $b$ के महत्तम सार्वभाजक, जिसे $\gcd(a, b)$ से निरुपित किया जाता है, एक धन पूर्णांक $d$ होता है, जो निम्न प्रतिबंधों को संतुष्ट करता है:
(a) $d \mid a$ और $d \mid b$.
(b) यदि $c \mid a$ और $c \mid b$, तो $c \leq d$.

उदाहरण 2.6. दो पूर्णांक $-8$ और $12$ लीजिए | $-8$ के धन भाजक $1, 2, 4$ और $8$ हैं, जबकि $12$ के धन भाजक $1, 2, 3, 4, 6$ और $12$ हैं |इस प्रकार $-8$ और $12$ के सार्वभाजक $1, 2$ और $4$ हैं | इनमें $4$ महत्तम संख्या है | अतः $\gcd(-8, 12)=4$.

        अगला प्रमेय बताता है कि दो संख्याओं $a$ और $b$ के महत्तम सार्वभाजक को $a$ और $b$ के रैखिक संयोजन (linear combination) के रूप में लिखा जा सकता है |

प्रमेय 2.7. यदि $a$ और $b$ दो दिए गए पूर्णांक हों, जिनमें कम से कम एक शून्येतर हो, तो पूर्णांकों $x$ और $y$ का अस्तित्व होता है, जिससे कि 
\[\gcd(a, b) = ax + by.\] 
उपपत्ति: 
संख्याओं $a$ और $b$ के रैखिक संयोजनों के समुच्चय $S$ पर विचार करें:
\[S := \{au + bv : au + bv >0,~\text{जहाँ}~u, v \in \mathbb{Z}\}.\]
ध्यान दीजिये कि $S$ एक अरिक्त समुच्चय है, क्योंकि $a^2 + b^2 \in S$. अतः सुक्रमण सिद्धांत के अनुसार समुच्चय $S$ एक निम्नतम अवयव $d$ आविष्ट करता है | तब समुच्चय $S$ की परिभाषा से, ऐसे पूर्णांकों $x$ और $y$ का अस्तित्व होता है, जिससे कि $d = ax + by$. हम दिखाएँगे कि $d = \gcd(a, b)$. पूर्णांकों $a$ और $d$ पर विभाजन - कलन विधि लागू करने पर हमें दो पूर्णांक $q$ और $r$ प्राप्त होते हैं, जिससे कि $a = qd + r$, जहाँ $0 \leq r < d$. अब 
\[r = a - qd = a- q(ax + by) = a(1-qx) + b(-qy).\] 
यदि $r > 0$, तो $r \in S$, जो इस तथ्य का अंतर्विरोध करता है कि $d$ समुच्चय $S$ का निम्नतम अवयव है | अतः $r = 0$. इसलिए $a = qd$, अर्थात $d \mid a$. इसी प्रकार हम दिखा सकते हैं कि $d \mid b$. अतः $d$ संख्याओं $a$ और $b$ का सार्वभाजक है | 
           अब यदि $c$ संख्याओं $a$ और $b$ का कोई अन्य धन सार्वभाजक हो, तो $c \mid (ax + by)$. अर्थात $c \mid d$. इसलिए $c \leq d$. इस प्रकार $d = \gcd(a, b)$ और हमारी उपपत्ति पूर्ण होती है |

परिभाषा 2.8 (असहभाज्य संख्याएँ).  दो पूर्णांकों $a$ और $b$, जिनमें कम से कम एक पूर्णांक शून्य नहीं है, को असहभाज्य (relatively prime) कहा जाता है, यदि $\gcd(a, b) = 1$.

प्रमेय 2.9.  मान लीजिए $a$ और $b$ दो पूर्णांक हैं, जिनमें कम से कम एक पूर्णांक शून्य नहीं है | तब $a$ और $b$ असहभाज्य होते हैं यदि और केवल यदि ऐसे पूर्णांकों $x$ और $y$ का अस्तित्व होता है, जिससे कि $ax + by = 1$.

उपपत्ति: 
सर्वप्रथम मान लीजिए कि किन्हीं पूर्णांकों $x$ और $y$ के लिए $ax + by = 1$ | मान लीजिए कि $\gcd(a, b) = d$ | तब म.स. की परिभाषा के अनुसार, $d \mid a$ और $d \mid b$ | इसलिए प्रमेय 2.4 (g) के अनुसार $d \mid (ax + by) = 1$ | अतः $d = 1$, क्योंकि $d$ एक धन पूर्णांक है | विलोमतः, मान लीजिए कि $a$ और $b$ असहभाज्य संख्याएँ हैं, अर्थात $\gcd(a, b) = 1$ | तब प्रमेय 2.7 के अनुसार ऐसे पूर्णांकों $x$ और $y$ का अस्तित्व होता है जिससे कि $ax + by = 1$ | इस तरह हमारी उपपत्ति पूर्ण होती है |

उपप्रमेय 2.10. यदि $\gcd(a, b) = d$, तो $\gcd(a/d, b/d) = 1$.

उपपत्ति: 
मान लीजिए कि $\gcd(a, b) = d$, तब ऐसे पूर्णांकों $x$ और $y$ का अस्तित्व होता है जिससे कि $ax + by = d$ | दोनों पक्षों को $d$ से विभाजित करने पर हमें $(\frac{a}{d})x + (\frac{b}{d})y = 1$ प्राप्त होता है | अतः प्रमेय 2.9 के अनुसार, $\gcd(\frac{a}{d}, \frac{b}{d}) = 1$ |

उपप्रमेय 2.11. यदि $a \mid c$, $b \mid c$ $ और \gcd(a, b) = 1$, तो $ab \mid c$.

उपपत्ति: 
क्योंकि $a \mid c$ और $b \ mid c$, हम पूर्णांक $r$ और $s$ ज्ञात कर सकते हैं जिससे कि $c = ar = bs$ | अब क्योंकि $\gcd(a, b) = 1$, इसलिए ऐसे धन पूर्णांकों $x$ और $y$ का अस्तित्व होता है जिससे कि $1 = ax + by$ | अतः
\[c = c \cdot 1= c(ax + by) = acx + bcy = a(bs)x + b(ar)y = ab(sx + ry),\]
और इसीलिए $ab \mid c$ |

प्रमेय 2.12 (यूक्लिड प्रमेयिका). यदि $a \mid bc$ और $\gcd(a, b) = 1$, तो $a \mid c$.

उपपत्ति: 
क्योंकि $\gcd(a, b) =1$ इसलिए ऐसे पूर्णांकों $x$ और $y$ का अस्तित्व होता है जिससे कि $1 = ax + by$ | अब
\[c = c \cdot 1= c(ax + by) = acx + bcy,\]
और क्योंकि $a \mid ac$ और $a \mid bc$, इसलिए $a \mid c$ |

उपप्रमेय 2.13. मान लीजिए $a$ और $b$ दो पूर्णांक हैं, जिनमें कम से कम एक पूर्णांक शून्य नहीं है | तब  $\gcd(a, b) = d$, जहाँ $d$ एक धन पूर्णांक है, यदि और केवल यदि 
(a) $d \mid a$ और $d \mid b$.
(b) यदि $c \mid a$ और $c \mid b$, तो $c \mid d$.

उपपत्ति: 
सर्वप्रथम मान लीजिए कि $d = \gcd(a, b)$ | तब निश्चित रूप से $d \mid a$ और $d \mid b$ | अतः प्रतिबंध (a) संतुष्ट हो जाता है | अब प्रमेय 2.7 के अनुसार ऐसे पूर्णांकों $x$ और $y$ का अस्तित्व होता है, जिससे कि $d = ax + by$ | अतः यदि $c \mid a$ और $c \mid b$, तो $c \mid (ax + by)$ | इसलिए $c \mid d$ | विलोमतः मान लीजिए कि $d$ एक धन पूर्णांक है जो प्रतिबंधों (a) और (b) को संतुष्ट करता है | अब यदि $a$ और $b$ का कोई सार्वभाजक $c$ हो, तो परिकल्पना (b) के अनुसार $c \mid d$, और इसलिए प्रमेय 2.4(f) के अनुसार $c \leq d$ | अतः म.स. की परिभाषा के अनुसार $\gcd(a, b) = d$ |

2.3. यूक्लिडीय कलन - विधि (Euclidean Algorithm)

पिछले अनुभाग में हमने दो पूर्णांकों के महत्तम सार्वभाजक को परिभाषित किया था | यदि दो पूर्णांक दिए हुए हों, तो उनका महत्तम सार्वभाजक ज्ञात करने के लिए सर्वप्रथम हम उनके भाजकों को सूचिबद्ध करते हैं और तब प्रत्येक सूची से सार्व भाजकों का चयन करते हैं | तत्पश्चात, उन सार्वभाजकों में से महत्तम संख्या का चयन करते हैं | यह संख्या ही अभीष्ट महत्तम सार्वभाजक होता है | यह प्रक्रिया सैद्धांतिक दृष्टिकोण से सरल प्रतीत होता है, परन्तु यदि संख्याएँ काफी बड़ी - बड़ी हों, तो यह विधि व्यावहारिक सिद्ध नहीं होती | अतः हमें किसी दक्ष विधि की खोज करनी होगी | एक ऐसी ही विधि दीर्घ विभाजन विधि है, जिससे हमसब प्रायः परिचित हैं | इस विधि को गणित में यूक्लिडीय कलन विधि के नाम से जाना जाता है | पहली बार आपने जब यह विधि सीखी होगी, तो शायद आपने यह प्रश्न नहीं किया होगा कि इस विधि का प्रयोग करने पर हमें महत्तम सार्वभाजक कयों प्राप्त होता है ? इसके पीछे क्या तर्क है ? या इस विधि की तर्कसंगतता को कैसे सत्यापित किया जा सकता है | प्रस्तुत अनुभाग में हम इन्हीं बातों पर चर्चा करेंगे | परन्तु सर्वप्रथम आइये हम यह जानें कि दीर्घ विभाजन विधि से महत्तम सार्वभाजक कैसे प्राप्त किया जाता है | 
            मान लीजिए हम दो पूर्णांकों $a$ और $b$ का महत्तम सार्वभाजक (म.स.) ज्ञात करना चाहते हैं | क्योंकि $\gcd(a, b) = \gcd(|a|, |b|)$, हम मान सकते हैं कि $a \geq b > 0$. प्रथम चरण में हम $a$ और $b$ पर विभाजन कलन विधि लागू करते हैं:
\[a = q_1b + r_1, 0 \leq r_1 < b.\]
यदि $r_1 = 0$, तो $b \mid a$ और $\gcd(a, b) = b$. यदि $r_1 \neq 0$, तो अगले चरण में हम पुनः $r_1$ और $b$ पर विभाजन कलन विधि लागू करते हैं:
\[b = q_2r_1 + r_2, 0 \leq r_2 < r_1.\]
यदि $r_2 = 0$, तो हमारी प्रक्रिया यही समाप्त हो जाती है | अन्यथा हम पिछले चरण की ही तरह प्रक्रिया दोहराते हैं | हमें प्राप्त होता है :
\[r_1 = q_3r_2 + r_3, 0 \leq r_3 < r_2.\]
विभाजन की यह प्रक्रिया हम तब तक जारी रखते हैं, जबतक कि शेषफल शून्य न प्राप्त हो जाए | हमें किसी न किसी चरण में शेषफल शून्य अवश्य प्राप्त होगा, क्योंकि ह्रासमान अनुक्रम $b > r_1 > r_2 > \cdots \geq 0$ में $b$ से ज्यादा पूर्णांक नहीं हो सकते | मान लीजिए हमें $(n + 1)$वें चरण में शेषफल शून्य प्राप्त होता है | तब हमें निम्नलिखित समीकरण निकाय प्राप्त होता है:
$a = q_1b + r_1, ~~~0 < r_1 < b$
$b = q_2r_1 + r_2,~~~ 0 < r_2 < r_1$
$r_1 = q_3r_2 + r_3,~~~ 0 < r_3 < r_2$
$\vdots$
$r_{n-2} = q_nr_{n-1} + r_n,~~~ 0 < r_n < r_{n-1}$
$r_{n-1} = q_{n-1}r_n + 0.$

हम कहते है $r_n$ पूर्णांकों $a$ और $b$ का म.स. है और $\gcd(a, b) = r_n$ लिखते हैं | परन्तु संख्या $r_n$ ही म.स. है, यह हम कैसे सिद्ध कर सकते हैं ? अगला प्रमेय इसी तथ्य की पुष्टि करता है |

प्रमेय 2.14. यदि $a = qb + r$, तो $\gcd(a, b) = gcd(b, r)$.

उपपत्ति: 
मान लीजिए कि $d = \gcd(a, b)$| तब $d \mid a$ और $d \mid b$, और इसलिए $d \mid (a-qb)$ | इस प्रकार $d \mid b$ और $d \mid r$ | अब मान लीजिए कि $c \mid b$ और $c \mid r$ | तब $c \mid qb + r$, अर्थात $c \mid a$ | अतः $c \leq d$ | इस प्रकार $b$ और $r$ के म.स. की परिभाषा के अनुसार, $\gcd(b, r) = d$ |

निम्नलिखित प्रमेय म.स. के अभिकलन में अत्यंत उपयोगी सिद्ध होता है |

प्रमेय 2.15. यदि $k$ एक शून्येतर पूर्णांक हो, तो $\gcd(ka, kb) = |k|\gcd(a, b)$.

उपपत्ति: 
मान लीजिए कि $\gcd(a, b) = d$ और $|k| \gcd(a, b) = |k|d = d'$ | तब $d \mid a$ और $d \mid b$ | इसलिए $d \mid ka$ और $d \mid kb$ | क्योंकि $k \neq 0$, इसलिए $d' \mid ka$ और $d' \mid kb$ | अब मान लीजिए कि  $c \mid ka$ और $c \mid kb$ | हम दिखाएँगे कि $ c \leq d'$ | मान लीजिए $c > d' = |k|a$ | तब $c \nmid d'$, और इसलिए $c \nmid |k|$ और $c \nmid d$ | अर्थात $c \nmid k$ और $c \nmid d$ | अब क्योंकि $c \nmid d$, अतः $\gcd(a, b)$ की परिभाषा के अनुसार, या तो $c \nmid a$ या $c \nmid b$ | मान लीजिए $c \nmid a$ | तब क्योंकि $c \nmid k$, इसलिए $c \nmid ka$, जो इस मान्यता का अंतर्विरोध करता है कि $c \mid ka$ | अतः हमारी मान्यता गलत है | इसलिए $c \leq d'$ | इस प्रकार म.स. की परिभाषा के अनुसार, $\gcd(ka, kb) = d' = |k|\gcd(a, b)$ |

2.4. लघुतम समापवर्त्य (Lowest Common Multiple)

इस अनुभाग में हम पूर्णांकों के लघुतम समापवर्त्य (ल.स.) पर चर्चा करेंगे और ल.स. और म.स. के बीच संबंध स्थापित करेंगे | म.स. की ही तरह गणित में ल.स. भी महत्वपूर्ण है | एक पूर्णांक $c$ को शून्येतर पूर्णांकों $a$ और $b$ का समापवर्त्य कहा जाता है, यदि $a \mid c$ और $b \mid c$. स्पष्टतः शून्य $a$ और $b$ का समापवर्त्य है | ध्यान दें कि $ab$ और $-ab$ दोनों ही $a$ और $b$ के समापवर्त्य हैं, जिनमें से एक धनात्मक है | अतः शून्येतर पूर्णांकों $a$ और $b$ के समापवर्त्यों का समुच्चय अरिक्त है | इसलिए सुक्रमण सिद्धांत (well ordering principle) के अनुसार, यह समुच्चय एक निम्नतम अवयव $m$ को आविष्ट करता है | इस निम्नतम अवयव को ही शून्येतर पूर्णांकों $a$ और $b$ का ल.स. कहते हैं और हम $\mathrm{lcm}(a, b) = m$ लिखते हैं | नीचे हम स्पष्ट गणितीय परिभाषा देते हैं:

परिभाषा 2.16 (लघुतम समापवर्त्य). दो शून्येतर पूर्णांकों $a$ और $b$ का ल.स., जिसे $\mathrm{lcm}(a, b)$ से व्यक्त किया जाता है, एक धन पूर्णांक $m$ होता है, जो निम्नलिखित प्रतिबंधों को संतुष्ट करता है:
(a) $a \mid m$ और $b \mid m$,
(b) यदि $a \mid c$ और $b \mid c$, जहाँ $c > 0$, तो $m \leq c$.

निम्नलिखित प्रमेय म.स. और ल.स. के बीच संबंध को व्यक्त करता है |

प्रमेय 2.17. (म.स. - ल.स. संबंध) यदि $a$ और $b$ दो शून्येतर पूर्णांक हों,तो
\[\gcd(a, b) \mathrm{lcm}(a, b) = ab.\]

उपपत्ति: 
मान लीजिए कि $d = \gcd(a, b)$. क्योंकि $d \mid a$ और $d \mid b$, हम किन्हीं पूर्णांकों $r$ और $s$ के लिए $a = dr$ और $b = ds$ लिख सकते हैं. यदि $m = ab/d$, तो $m = as = br$. इस प्रकार $a \mid m$ और $b \mid m$. अब मान लीजिए कि $c$ एक ऐसा धन पूर्णांक है जिससे कि $a \mid c$ और $b \mid c$, अर्थात $c = au = bv$. क्योंकि $d = \gcd(a, b)$, ऐसे पूर्णांकों $x$ और $y$ का अस्तित्व होता है जिससे कि $d = ax + by$. फलस्वरूप,
\[\frac{c}{m} =  \frac{cd}{ab} = \frac{c(ax + by)}{ab} = \frac{c}{b}x + \frac{c}{a}y = vx + uy.\]
इस प्रकार $m \mid c$. परिणामतः, $m \leq c$. अतः ल.स. की परिभाषा से, $m = \mathrm{lcm}$. इस प्रकार हमारी उपपत्ति पूर्ण होती है.

उपप्रमेय 2.18. किन्हीं भी  शून्येतर पूर्णांकों $a$ और $b$ के लिए $\mathrm{lcm}(a, b) = ab$ यदि और केवल यदि $\gcd(a, b) = 1$.

उपपत्ति: 
इसकी उपपत्ति अत्यंत स्पष्ट है |

यह अध्याय हम यहीं समाप्त करते हैं | अगले अध्याय में हम अभाज्य संख्याओं (prime numbers) पर चर्चा करेंगे और एक अत्यंत ही आधारभूत और महत्वपूर्ण प्रमेय - अंकगणित का मूलभूत प्रमेय (Fundamental Theorem of Arithmetic) - का कथन देंगे और उसकी उपपत्ति भी देंगे |

राज कुमार राजहंस
शोधार्थी, गणित विभाग
भारतीय प्रौद्योगिकी संस्थान पटना 
भारत
ई-मेल: ganitanjalii@gmail.com


कोई टिप्पणी नहीं :

एक टिप्पणी भेजें

शीर्ष पर जाएँ