इरेटोस्थिनीज़ की चलनी-विधि (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, बुधवार)