आव्यूह वियोजन (Matrix Decomposition)

किसी आव्यूह (Matrix) को कुछ विशेष प्रकार के आव्युहों के गुणनफल के रूप में लिखने की प्रक्रिया आव्यूह वियोजन (Matrix Decomposition) कहलाती है. आव्यूह वियोजन के द्वारा किसी आव्यूह के गुणधर्मों और उससे संबंधित समस्याओं का अध्ययन आसान हो जाता है, क्योंकि इस प्रक्रिया के द्वारा किसी आव्यूह को ज्ञात गुणधर्मों वाले आव्यूहों के गुणनफल के रूप में व्यक्त किया जाता है.. अतः आव्यूह - सिद्धांत (Matrix Theory) में और अनुप्रयुक्त गणित में इस प्रक्रिया का विशेष महत्त्व है. यहाँ पर हम कुछ विशेष प्रकार के आव्यूह वियोजन, जैसे - शुर वियोजन (Schur Decomposition), स्पेक्ट्रमी वियोजन (Spectral Decomposition),  विचित्र मान वियोजन (Singular Value Decomposition) और ध्रुवीय वियोजन (Polar Decomposition) पर विस्तृत चर्चा करेंगे.

गणितज्ञ कैसे बनें ? दूसरी कड़ी : अभाज्य संख्याओं की अनंतता (Infinitude of Prime Numbers)

"गणितज्ञ कैसे बनें ?" गणितीय आलेखों की एक श्रृंखला है, जिसके अंतर्गत विविध गणितीय विषयों पर ऐसे लेख प्रस्तुत किये जाते हैं, जो पाठकों को ज्ञात गणितीय तथ्यों, परिणामों और सूत्रों को स्वयं खोजने के लिए क्रमबद्ध तरीके से प्रेरित करते हैं और जिनसे उनके अंदर गणितीय शोध की स्वाभाविक प्रवृति जागृत होती है.

एक से बड़ी वैसी प्राकृत संख्या (natural numbers) जिसके गुणनखंड केवल $1$ और वही संख्या हों, अभाज्य संख्या (prime number) कहलाती है. दूसरे शब्दों में अभाज्य संख्याओं को $1$ और उस संख्या के अतिरिक्त किसी अन्य संख्या से विभाजित नहीं किया जा सकता है. उदाहरण के लिए $2, 3, 5, 7, 11, 13$ इत्यादि अभाज्य संख्याएँ हैं. परन्तु $4$ एक अभाज्य संख्या नहीं है, क्योंकि इसे $1$ और $4$ के अतिरिक्त $2$ से भी विभाजित किया जा सकता है. इसी प्रकार $6, 8, 9, 10, 12$ इत्यादि अभाज्य संख्याएँ नहीं हैं. ये संख्याएँ संयुक्त संख्याएँ है. एक से बड़ी वैसी प्राकृत संख्या, जो अभाज्य नहीं है, संयुक्त संख्या (composite number) कहलाती है. अभाज्य संख्याओं के गुणधर्मों की विस्तृत जानकारी के लिए अभाज्य संख्याएँ देखें. अंकगणित के मूलभूत प्रमेय (Fundamental Theorem of Arithmetic) से हम जानते हैं कि एक से बड़ी किसी भी प्राकृत संख्या को अभाज्य संख्याओं के गुणनफल के रूप में अद्वितीयतः (uniquely) लिखा जा सकता है. अतः अभाज्य संख्याएँ मूलभूत संख्याएँ  हैं और इन्हें संख्याओं की निर्माण - इकाई कहना तर्कसंगत होगा.
 

हम जानते हैं कि प्राकृत संख्याओं की संख्या अनंत हैं. परिभाषा के अनुसार सभी अभाज्य संख्याएँ प्राकृत संख्याएँ हैं. अतः यह स्वाभाविक जिज्ञासा होती है कि क्या अभाज्य संख्याओं की संख्याओं भी अनंत है ? प्रस्तुत लेख में हम इसी विषय पर चर्चा करने जा रहे हैं.

गणितज्ञ कैसे बनें ? पहली कड़ी : द्विपद प्रमेय (Binomial Theorem)

"गणितज्ञ कैसे बनें ?" गणितीय आलेखों की एक श्रृंखला है, जिसके अंतर्गत विविध गणितीय विषयों पर ऐसे लेख प्रस्तुत किये जाते हैं, जो पाठकों को ज्ञात गणितीय तथ्यों, परिणामों और सूत्रों को स्वयं खोजने के लिए क्रमबद्ध तरीके से प्रेरित करते हैं और जिनसे उनके अंदर गणितीय शोध की स्वाभाविक प्रवृति जागृत होती है.

यदि कोई वास्तविक संख्या (real number) $a$ दी हुई हों, तो इसके  $n$-वें घात $a^n$, जहाँ $n$ एक ॠणेतर (non-negative) संख्या है, का परिकलन आसानी से कर सकते हैं. इसके लिए हम $\underbrace{a \times \cdots \times a}_{n \text{बार}}$ का परिकलन करते हैं. उदाहरण के लिए, $5^2 = 5 \times 5 = 25$ और $(-2)^3 = (-2) \times (-2) \times (-2) = -8$. ध्यान रखें कि किसी शून्येतर (nonzero) वास्तविक संख्या $a$ के लिए $a^0$ का मान $1$ परिभाषित किया जाता है.

अभाज्य संख्याओं की अनंतता (Infinitude of Prime Numbers)

अभाज्य संख्याओं की परिभाषा से हम सब परिचित हैं.  एक स्वाभाविक जिज्ञासा होती है कि सबसे बड़ी अभाज्य संख्या कौन है या इनकी संख्या अनंत है. इस प्रश्न का उत्तर यूक्लिड (Euclid) की पुस्तक संख्या - IX में देखा जा सकता है, जहाँ उन्होंने सिद्ध किया है कि अभाज्य संख्याओं की संख्या अनंत है. उनका तर्क मोटे तौर पर इस प्रकार है: यदि अभाज्यों की एक परिमित सूची दी हुई हो, तो हम एक अन्य अभाज्य संख्या ज्ञात कर सकते हैं, जो इस सूची में नहीं हैं. नीचे के प्रमेय में हम इस तथ्य की स्पष्ट उपपत्ति देते हैं.

प्रमेय (यूक्लिड). अभाज्य संख्याओं की संख्या अनंत है.

उपपत्ति: 

मान लीजिए कि अभाज्य संख्याओं की संख्या परिमित है. इन अभाज्यों की सूची $p_1, p_2, \ldots , p_n$ बनाईये. अब एक धन पूर्णांक $m = p_1p_2\cdots p_n + 1$ परिभाषित कीजिये. क्योंकि $m > 1$, अंकगणित के मूलभूत प्रमेय के अनुसार, कम से कम एक अभाज्य $p$ धन पूर्णांक $m$ को अवश्य विभाजित करेगा. क्योंकि हमारे पास परिमित संख्या में अभाज्य संख्याएँ हैं, अतः $p$ इन्हीं अभाज्यों में से कोई एक अभाज्य होगा. परन्तु तब $p \mid p_1\cdots p_n$. क्योंकि $p \mid m$, इसलिए अवश्य ही $p \mid (m - p_1\cdots p_n)$, अर्थात $p \mid 1$, जो एक अंतर्विरोध है. अतः अभाज्य संख्याओं की संख्या परिमित नहीं हो सकती. इस प्रकार हमारी उपपत्ति पूर्ण होती है. 

क्योंकि किसी भी विषम धन पूर्णांक को $4n + 1$ या $4n + 3$ के रूप में व्यक्त किया जा सकता है, इसलिए विषम अभाज्य संख्याएँ भी इन रूपों में व्यक्त किये जा सकते हैं. एक स्वाभाविक प्रश्न उठता है कि क्या $4n + 1$ के रूप में या $4n + 3$ के रूप में व्यक्त किये जा सकने वाले अभाज्य संख्याओं की संख्या अनंत है. इस प्रश्न का उत्तर "हाँ" है | नीचे के प्रमेय में हम सिद्ध करेंगे कि $4n + 3$ के रूप में व्यक्त किये जा सकने वाले अभाज्य संख्याओं की संख्या अनंत है. परन्तु उससे पहले हम निम्नलिखित प्रमेयिका सिद्ध करेंगे.

प्रमेयिका. यदि दो या अधिक पूर्णांक $4n + 1$ के रूप के हों, तो उनका गुणनफल भी इसी रूप का होता है.

उपपत्ति: 

केवल $4n + 1$ के रूप वाले दो पूर्णांकों पर विचार करना पर्याप्त है. मान लीजिए $m_1 = 4m +1$ और $m_2 = 4n + 1$. तब $m_1m_2 = (4m + 1)(4n + 1) = 4(4mn + m + n) + 1$, जो अभीष्ट रूप में है.

प्रमेय. $4n + 3$ के रूप में व्यक्त किये जा सकने वाले अभाज्यों की संख्या अनंत हैं.

उपपत्ति: 

इस कथन को हम अंतर्विरोध द्वारा सिद्ध करेंगे. मान लीजिए कि $4n + 3$ के रूप में व्यक्त किये जा सकने वाले अभाज्य संख्याओं की संख्या परिमित हैं और ये अभाज्य $p_1, \ldots, p_k$ हैं. अब एक धनात्मक पूर्णांक 
\[m = 4p_1\cdots p_k - 1 = 4(p_1\cdots p_k - 1) + 3\]
परिभाषित कीजिए. ध्यान दीजिए कि $m \geq 3$. अतः $m$ किसी अभाज्य संख्या से विभाजित होगा. क्योंकि $m$ एक विषम संख्या है, अतः इसके सभी अभाज्य गुणनखंड विषम होंगे और ये सभी गुणनखंड या तो $4n + 1$ के रूप के होंगे या $4n + 3$ के रूप के होंगे. यदि सभी गुणनखंड $4n + 1$ के रूप के हों, तो उपरोक्त प्रमेयिका के अनुसार $m$ भी $4n + 1$ के रूप का होगा, जो सत्य नहीं है. अतः $m$ का कम से कम एक अभाज्य गुणनखंड $4n + 3$ के रूप का अवश्य होगा. क्योंकि हम यह मानकर चले थे कि $4n + 3$ के रूप में व्यक्त किये जा सकने वाले अभाज्य केवल $p_1,\ldots , p_k$ हैं, अतः $m$ का कम से कम एक अभाज्य गुणनखंड इन्हीं अभाज्यों में से कोई एक अभाज्य, मान लीजिए $p_1$, होगा. परन्तु तब क्योंकि $p_1 \mid 4p_1\cdots p_k$, इसलिए $p_1 \mid 4p_1\cdots p_k - m = 1$, जो एक अंतर्विरोध है. अतः ऐसे अभाज्यों की संख्या परिमित नहीं हो सकती. इस प्रकार हमारी उपपत्ति पूर्ण होती है.

उपरोक्त उपपत्ति की ही तरह इस तथ्य की उपपत्ति नहीं दी जा सकती है कि $4n + 1$ के रूप में व्यक्त किये जा सकने वाले अभाज्यों की संख्या अनंत हैं. इस कथन की उपपत्ति हम आगे के किसी अध्याय में देंगे. उपरोक्त दोनों कथन डिरिक्ले (Dirichlet) के निम्नलिखित प्रमेय की विशेष स्थिति है.

प्रमेय. यदि $a$ और $b$ असहभाज्य धन पूर्णांक हों, तो सामानांतर अनुक्रम

\[a, a+b, a+2b, a+3b, \ldots\]

अनंततः अनेक अभाज्य संख्याओं को आविष्ट करता है.

उपरोक्त प्रमेय के अनुसार, किन्हीं दो असहभाज्य धन पूर्णांकों $a$ और $b$ के लिए $a+nb$ के रूप में व्यक्त किये जा सकने वाले अभाज्य संख्याओं की संख्या अनंत होती हैं. इस प्रमेय की उपपत्ति यहाँ हम नहीं देंगे. इसकी उपपत्ति वैश्लेषिक संख्या सिद्धांत (Analytic Number Theory) के अंतर्गत किसी अध्याय में (इसी ब्लॉग में अन्यत्र) दी जाएगी.

इस विषय से संबंधित अन्य जानकारी के लिए मूल आलेख अभाज्य संख्याएँ देखें.

ध्यातव्य: इस विषय से संबंधित किसी भी प्रश्न या जिज्ञासा के लिए इस पृष्ठ पर टिप्पणी करें या ganitanjalii@gmail.com पर ई-मेल करें.

(चैत्र शुक्ल पक्ष, त्रयोदशी, वि. सं. 2072, वृहस्तपतिवार)

(चैत्र 12, राष्ट्रीय शाके 1937, वृहस्तपतिवार)

 

इरेटोस्थिनीज़ की चलनी-विधि (The Sieve of Eratosthenes)

यदि एक धन पूर्णांक दिया हुआ हो, तो स्वाभाविक प्रश्न उठता है कि दी गई संख्या अभाज्य है या नहीं. यह निर्णय करना सैद्धांतिक रूप से संभव है. मान लीजिए दी गई संख्या $n$ है. इस संख्या के तुच्छ गुणनखंड $1$ और $n$ हैं. यदि हम $n$ कोई अतुच्छ गुणनखंड $a$ ज्ञात कर सके, तो $a \mid n$, और इस प्रकार $n$ एक संयुक्त संख्या होगी. यदि कोई भी अतुच्छ गुणनखंड (nontrivial factor) न हो, तो $n$ के केवल तुच्छ गुणनखंड (trivial factors) $1$ और $n$ होंगे और $n$ एक अभाज्य संख्या होगी. इस प्रकार किसी धन पूर्णांक $n$ की अभाज्यता (primality) की जाँच करने के लिए हमें $n$ से छोटी सभी संख्याओं से $n$ की विभाज्यता (divisibility) की जाँच करनी होगी. छोटी संख्याओं के लिए यह विधि आसान है, परन्तु बड़ी संख्याओं के लिए यह विधि व्यावहारिक सिद्ध नहीं होती. परन्तु इस विधि को थोड़ा दक्ष बनाया जा सकता है. इस विधि के अनुसार, हमें किसी धन पूर्णांक $n$ की अभाज्यता की जाँच करने के लिए केवल $\sqrt{n}$ की संख्याओं से $n$ की विभाज्यता की जाँच करना पर्याप्त होता है. यह तथ्य इस प्रेक्षण पर आधारित है कि यदि धन पूर्णांक $n$ अभाज्य नहीं हो, तो इसका कम से कम एक अतुच्छ गुणनखंड $\sqrt{n}$ से कम या इसके बराबर होगा. इसे हम निम्नलिखित प्रमेय के द्वारा स्पष्ट करते हैं:

प्रमेय. एक धन पूर्णांक $n \geq 2$ संयुक्त संख्या होती है यदि और केवल यदि यह $1$ से बड़ी किसी अभाज्य संख्या $p \leq \sqrt{n}$ से विभाज्य हो.

आइये, इसे एक उदाहरण की सहायता से समझें. मान लीजिए हमें $2017$ की अभाज्यता की जाँच करनी है. क्योंकि $44 < \sqrt{2017} < 45$,  इसलिए $44$ से छोटी सभी अभाज्य संख्याओं $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41$ और $43$ से $2017$ की विभाज्यता की जाँच करना पर्याप्त है. हम आसानी से जाँच कर सकते हैं कि $2017$ उपरोक्त अभाज्य संख्याओं में से किसी भी संख्या से विभाज्य नहीं है. अतः $2017$ एक अभाज्य संख्या है. आइये, अब $2093$ की अभाज्यता की जाँच करें. क्योंकि $45 < \sqrt{2093} < 46$, इसलिए $45$ से छोटी सभी अभाज्य संख्याओं $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41$ और $43$ से $2093$ की विभाज्यता की जाँच करना पर्याप्त है. हम देख सकते है कि यह $7$ से विभाज्य है, अर्थात $2093 = 7 \cdot 299$. अतः $2093$ अभाज्य नहीं है.

उपरोक्त विधि में हमने देखा कि किसी धन पूर्णांक $n$ की अभाज्यता जाँच करने के लिए हमें $\sqrt{n}$ तक की अभाज्य संख्याओं से ही $n$ की विभाज्यता की जाँच करनी होती है. फिर भी बड़ी संख्याओं के लिए यह विधि व्यावहारिक सिद्ध नहीं होती, क्योंकि $n$ के बड़े मानों के लिए $\sqrt{n}$ का भी मान बड़ा होता है, और तब हमें बहुत अधिक अभाज्य संख्याओं से $n$ की विभाज्यता की जाँच करनी होती है. किसी धन पूर्णांक $n$ की विभाज्यता की जाँच करने के लिए अभी तक कोई आसान विधि नहीं खोजी जा सकी है. परन्तु इस विधि से अधिक दक्ष ढेर सारी विधियाँ हैं, जिनकी चर्चा हम अगले अध्यायों में उपयुक्त स्थानों पर करेंगे.

आइये अब हम इरेटोस्थिनीज़ की चलनी विधि पर चर्चा करें. यह विधि परिमित संख्या में लिए गए धन पूर्णांकों के समुच्चय से अभाज्य संख्याओं को छाँटने की विधि है. यह विधि उपरोक्त विधि पर ही आधारित है. मान लीजिए हमें $100$ तक की अभाज्य संख्याएँ ज्ञात करनी है | हम निम्नलिखित प्रक्रिया दुहराते हैं :

चरण 1. दस क्षैतिज पंक्तियों में $1$ से $100$ तक की संख्या लिखें.

चरण 2. $1$ को काट दें, क्योंकि यह अभाज्य संख्या नहीं है.

चरण 3. क्योंकि $2$ अभाज्य संख्या है, इस पर घेरा लगाएँ और $2$ के अतिरिक्त इसके अन्य सभी गुणजों $2, 4, 6, 8, 10, \ldots$,  इत्यादि को काट दें.

चरण 4. अब अगली अभाज्य संख्या $3$ को घेर दें और इनके अन्य गुणजों को काट दें.

चरण 5. अगली अभाज्य संख्या $5$ को घेर दें और इनके अन्य गुणजों को काट दें.

चरण 6. पुनः अगली अभाज्य संख्या $7$ को घेर दें और इनके अन्य गुणजों को काट दें.

चरण 7. यह प्रक्रिया तब तक दुहराते रहें, जबतक कि सभी अभाज्य संख्याओं पर घेरा न लग जाएँ.

इस चरण के बाद हम देखते हैं कि हमें निम्नलिखित सारणी प्राप्त होती है, जिसमें वृत्ताकार घेरा के अंदर की सभी संख्याएँ अभाज्य हैं.

इरेटोस्थिनीज़ की चलनी विधि

इस प्रमेय की उपपत्ति और इस विषय से संबंधित अन्य जानकारी के लिए मूल आलेख अभाज्य संख्याएँ देखें.

ध्यातव्य: इस विषय से संबंधित किसी भी प्रश्न या जिज्ञासा के लिए इस पृष्ठ पर टिप्पणी करें या ganitanjalii@gmail.com पर ई-मेल करें.

(चैत्र शुक्ल पक्ष, द्वादशी, वि. सं. 2072, बुधवार)

(चैत्र 11, राष्ट्रीय शाके 1937, बुधवार)

अंकगणित का मूलभूत प्रमेय (Fundamental Theorem of Arithmetic)

एक धन पूर्णांक $a$ को पूर्णांक $n$ का गुणनखंड कहते हैं, यदि $a$ पूर्णांक $n$ को विभाजित करता है.  इस स्थिति में हम $n$ को $a$ और किसी अन्य पूर्णांक $b$ के गुणनफल के रूप में व्यक्त कर सकते हैं. अर्थात $n = ab$ और इस स्थिति में  $b$ भी $n$ का  एक गुणनखंड होता है. उदाहरण के लिए, $30$ का एक गुणनखंड $2$ है. इसलिए हम $30 = 2 \cdot 15$ लिखते हैं.  इस प्रकार हम $30$ को दो पूर्णांकों $2$ और $15$ के गुणनफल के रूप में लिख सकते हैं.  हम देख सकते हैं कि दोनों ही गुणनखंड $30$ से छोटे हैं. अब इसके एक गुणनखंड $15$ पर विचार कीजिये. हम आसानी से कह सकते हैं कि $15$ का एक गुणनखंड $3$ है और इसलिए $15 = 3 \cdot 5$ लिख सकते हैं. इस प्रकार हम $30$ का पुनः गुणनखंडन कर सकते हैं. अर्थात हम $30 = 2 \cdot 3 \cdot 5$ लिख सकते हैं. पुनः हम देखते हैं कि $30$ का प्रत्येक गुणनखंड $30$ से छोटा है. क्या हम इन गुणनखंडों में से किसी गुणनखंड को पुनः छोटे गुणनखंडों के रूप में लिख सकते हैं ? हम $2$ को $1 \cdot 2$ के रूप में लिख सकते हैं. क्योंकि किसी संख्या को $1$ से गुणा करने पर गुणनफल के रूप में वही संख्या प्राप्त होती है, अतः हम ऐसे गुणनखंड पर विचार नहीं करेंगे. इस प्रकार हम देखते हैं $30$ का और अधिक गुणनखंडन नहीं किया जा सकता, जिससे कि प्रत्येक गुणनखंड $1$ से बड़ा और $30$ से छोटा हो. इस प्रकार के गुणनखंडन को अभाज्य गुणनखंडन कहते हैं और गुणनखंडन में सम्मिलित प्रत्येक गुणनखंड को अभाज्य गुणनखंड कहते हैं, क्योंकि इन गुणनखंडों का पुनः विभाजन संभव नहीं है. जिस धन पूर्णांक को $1$ या उस संख्या के अतरिक्त किसी अन्य धन पूर्णांकों के गुणनफल के रूप में व्यक्त नहीं किया जा सके, उसे हम अभाज्य संख्या कहते हैं. दूसरे शब्दों में हम इसे निम्न प्रकार परिभाषित करते हैं:

परिभाषा (अभाज्य संख्या). एक धन पूर्णांक $p > 1$ को अभाज्य संख्या कहा जाता है, यदि इसके गुणनखंड केवल $1$ और $p$ हों. एक से बड़ी वैसी संख्या, जो अभाज्य नहीं है, उसे संयुक्त संख्या कहा जाता है. $1$ न तो अभाज्य संख्या है और न ही संयुक्त संख्या.

 उदाहरण के लिए $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71$ प्रथम बीस अभाज्य संख्याएँ हैं.  इस प्रकार $30$ के गुणनखंडन $2 \cdot 3 \cdot 5$ में सभी गुणनखंड अभाज्य संख्याएँ हैं. क्या सभी धन पूर्णांकों का अभाज्य गुणनखंडन संभव है ? अपने अनुभव और अंतर्ज्ञान से हम जानते हैं कि ऐसा करना सदैव ही संभव है. वास्तव में,  ऐसा करना संभव है. इस तथ्य को हम निम्नलिखित प्रमेय, जिसे "अंकगणित का मूलभूत प्रमेय" कहा जाता है,  में व्यक्त करते हैं.

 प्रमेय (अंकगणित का मूलभूत प्रमेय). प्रत्येक धन पूर्णांक $n > 1$ को अभाज्य संख्याओं के गुणनफल के रूप में निम्न प्रकार व्यक्त किया जा सकता है:

\[n = p_1^{e_1} \cdots p_k^{e_k},\]

जहाँ $p_1, \ldots, p_k$ भिन्न - भिन्न अभाज्य संख्याएँ हैं और $e_1, \ldots, e_k$ धन पूर्णांक हैं. यदि इस निरूपण में अभाज्य गुणनखंडों के क्रम को महत्त्व न दिया जाये तो यह निरूपण अद्वितीय होता है.

इस प्रमेय की उपपत्ति और इस विषय से संबंधित अन्य जानकारी के लिए मूल आलेख अभाज्य संख्याएँ देखें.

***

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

मान लीजिए $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) कहते हैं | इस प्रकार हम निन्लिखित परिभाषा देते हैं:

    

परिभाषा (महत्तम सार्वभाजक). मान लीजिए $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$.

उदाहरण. दो पूर्णांक $-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) के रूप में लिखा जा सकता है |

प्रमेय. यदि $a$ और $b$ दो दिए गए पूर्णांक हों, जिनमें कम से कम एक शून्येतर हो, तो पूर्णांकों $x$ और $y$ का अस्तित्व होता है, जिससे कि 

\[\gcd(a, b) = ax + by.\] 

इस प्रमेय की उपपत्ति और इस विषय से संबंधित अन्य जानकारी के लिए मूल आलेख विभाज्यता - सिद्धांत (The Theory of Divisibility) देखें |

ध्यातव्य: इस विषय से संबंधित किसी भी प्रश्न या जिज्ञासा के लिए इस पृष्ठ पर टिप्पणी करें या ganitanjalii@gmail.com पर ई-मेल करें |

(चैत्र शुक्ल पक्ष, चतुर्थी, वि. सं. 2072, सोमवार)

(चैत्र 02, राष्ट्रीय शाके 1937, सोमवार)