परिचय


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

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

4. समशेषता सिद्धांत

4.1. परिचय

यदि पूर्णांक संख्याओं $a$ और $b$ को किसी धनात्मक पूर्णांक $n$ से विभाजित करने पर समान शेषफल प्राप्त हों, तो $a$ और $b$ को $n$ के सापेक्ष समशेष संख्याएँ कहते हैं, क्योंकि इन्हें $n$ से विभाजित करने पर समान शेषफल प्राप्त होता है. गणितीय संकेत में इस तथ्य को हम प्रतीक $a \equiv b \pmod n$ से व्यक्त करते हैं और "$a$ समशेष $b$ मॉड्यूलो $n$" पढ़ते हैं. उदाहरण के लिए, $7 \equiv 17 \pmod 5$ क्योंकि $5$ और $7$ में प्रत्येक को $5$ से विभाजित करने पर शेषफल $2$ ही प्राप्त होता है. इसी प्रकार, $-9 \equiv 12 \pmod 7$, क्योंकि $-9$ और $12$ में प्रत्येक को $7$ से विभाजित करने पर समान शेष $5$ प्राप्त होता है.

विभाजन कलन विधि से हम जानते हैं कि यदि किसी पूर्णांक $a$ को धनात्मक पूर्णांक $n$ से विभाजित किया जाए, तो शेषफल सदैव ॠणेतर होता है और $n$ से छोटा होता है. इस प्रकार संभावित शेषफल $0, 1, \ldots, n-1$ होते हैं. अब इनमें से कोई शेषफल $r \in \{0, 1, \ldots, n-1\}$ नियत कीजिये. क्या आप उन पूर्णांकों की सूची तैयार कर सकते हैं जिससे कि प्रत्येक को $n$ से विभाजित करने पर समान शेष $r$ प्राप्त हों ? उदाहरण के लिए, यदि हम $n= 2$ लें, तो किसी पूर्णांक को $2$ से विभाजित करने पर शेषफल या तो $0$ होगा या $1$ होगा. हम $r = 0$ नियत करते हैं. तब विभाजन कलन विधि के अनुसार वैसी संख्याएँ, जिन्हें $2$ से विभाजित करने पर शेषफल शून्य हों, $2k + 0 = 2k$ के रूप की होंगी, जहाँ $k$ एक पूर्णांक है. इसी प्रकार, यदि हम $r = 1$ नियत करें, तो वैसी संख्याएँ, जिन्हें $2$ से विभाजित करने पर शेषफल $1$ हों, $2k + 1$ के रूप की होंगी, जहाँ $k$ एक पूर्णांक है. इस प्रकार संख्याओं को शेषफल के अनुसार भिन्न - भिन्न समूहों में वर्गीकृत किया जा सकता है. यदि $2$ से विभाजित करने पर शेषफल $0$ देने वाले संख्याओं को हम $[0]_2$ से निरूपित करें, तो
\begin{equation}\label{ex1}
[0]_2 = \{\ldots, -6, -4, -2, 0, 2, 4, 6, \ldots\}.
\end{equation}
इसी प्रकार, यदि $2$ से विभाजित करने पर शेषफल $1$ देने वाले संख्याओं को हम $[1]_2$ से निरूपित करें, तो
\begin{equation}\label{ex2}
[1]_2 = \{\ldots, -7, -5, -3, -1, 1, 3, 5, 7, \ldots\}.
\end{equation}
ध्यान दीजिये कि $[0]_2 \cap [1]_2 = \emptyset$, परन्तु $[0]_2 \cup [1]_2 = \mathbb{Z}$, जहाँ $\mathbb{Z}$ पूर्णांकों का समुच्चय है. इस प्रकार $[0]_2$ और $[1]_2$ पूर्णांकों के समुच्चय $\mathbb{Z}$ को दो समशेष वर्गों में बाँटता है और ये वर्ग एक - दूसरे को प्रतिच्छेद नहीं करते हैं.  यह भी ध्यान दीजिए कि $[0]_2$ की कोई भी दो संख्याएँ $2$ के सापेक्ष समशेष हैं, अर्थात यदि $a, b \in [0]_2$, तो $a \equiv b \pmod 2$. यही बात $[1]_2$ के लिए भी सत्य है. इसी प्रकार यदि हम $n = 3$ लें, तो हमें शेषफल $0, 1, 2$ के संगत निम्नलिखित समशेष वर्ग प्राप्त होंगे:
\begin{align}\label{ex3}
[0]_3 &= \{\cdots, -9, -6, -3, 0, 3, 6, 9, \cdots\};\\
[1]_3 &= \{\cdots, -8, -5, -2, 1, 4, 7, 10, \cdots\};\\
[2]_3 &= \{\cdots, -7, -4, -1, 2, 5, 8, 11, \cdots\}.
\end{align}
यहाँ भी आप देख सकते हैं कि कोई भी दो समशेष वर्ग एक दूसरे को प्रतिच्छेद नहीं करते हैं और $[0]_3 \cup [1]_3 \cup [2]_3 = \mathbb{Z}$.

यह कोई संयोग नहीं है. वास्तव में किसी भी धनात्मक पूर्णांक $n$ के लिए पूर्णांकों के समुच्चय $\mathbb{Z}$ को $n$ असंयुक्त समशेष वर्गों के सम्मिलन के रूप में लिखा जा सकता है. हम जानते हैं कि किसी पूर्णांक को $n$ से विभाजित किया जाए, तो संभावित शेषफल $0, 1, 2, \ldots, n-1$ होंगे. प्रत्येक शेषफल के संगत समशेष वर्ग निम्नलिखित होंगे:
\begin{aligned}\label{ex4}
[0]_n &= \{nk : k \in \mathbb{Z}\};\\
[1]_n &= \{nk+1 : k \in \mathbb{Z}\};\\
[2]_n &= \{nk+2 : k \in \mathbb{Z}\};\\
&\vdots \\
[n-1]_n  &= \{nk + (n-1) : k \in \mathbb{Z}\}.
\end{aligned}
हम सिद्ध करेंगे कि
\begin{equation}\label{ex5}
[0]_n \cup [1]_n \cup [2]_n \cup \cdots \cup [n-1]_n = \mathbb{Z}
\end{equation}
स्पष्टतः $[0]_n \cup [1]_n \cup [2]_n \cup \cdots \cup [n-1]_n \subseteq \mathbb{Z}$. अब कोई स्वेच्छ संख्या $a \in \mathbb{Z}$ लीजिए. तब विभाजन कलन विधि के अनुसार $a = nk + r$, जहाँ $k \in \mathbb{Z}$ एक पूर्णांक है और $0 \leq r \leq n-1$. अतः $a \in [r]_n$. इस प्रकार $\mathbb{Z} \subseteq [0]_n \cup [1]_n \cup [2]_n \cup \cdots \cup [n-1]_n$. इस प्रकार हमने सिद्ध किया है कि
\[[0]_n \cup [1]_n \cup [2]_n \cup \cdots \cup [n-1]_n \subseteq \mathbb{Z}\]
और
\[\mathbb{Z} \subseteq [0]_n \cup [1]_n \cup [2]_n \cup \cdots \cup [n-1]_n,\]
जिससे यह सिद्ध होता है कि
\[[0]_n \cup [1]_n \cup [2]_n \cup \cdots \cup [n-1]_n = \mathbb{Z}.\]
अब हम दिखाएँगे कि कोई भी दो समशेष वर्ग असंयुक्त हैं. इसके लिए मान लीजिए कि $[r]_n$ और $[s]_n$ दो भिन्न - भिन्न समशेष वर्ग हैं. हम सिद्ध करेंगे कि $[r]_n \cap [s]_n = \emptyset$. इसे हम अंतर्विरोध द्वारा सिद्ध करेंगे. मान लीजिए $[r]_n \cap [s]_n \neq \emptyset$. तब एक पूर्णांक $a$ का अस्तित्व होता है जिससे कि $a \in [r]_n \cap [s]_n $. अब क्योंकि $a \in [r]_n$, इसलिए $a = nk + r$. इसी प्रकार, क्योंकि $a \in [s]_n$, इसलिए $a = nk' + s$. परन्तु तब $nk + r = nk' + s$. इसलिए $n(k - k') = s-r$. अब यदि $k = k'$, तो $s = r$, जो इस बात का अंतर्विरोध करता है कि $r \neq s$. यदि $k \neq k'$, तो $n \mid (s - r)$. परन्तु $-(n-1) \leq s-r \leq (n-1)$, क्योंकि $0 \leq r, s \leq (n-1)$. इसलिए केवल एक ही सम्भावना है $s - r =0$. अतः $r = s$ और हमें फिर अंतर्विरोध प्राप्त होता है. इसलिए $[r]_n \cap [s]_n \neq \emptyset$ संभव नहीं है. इस प्रकार हमने सिद्ध किया है कि $[r]_n \cap [s]_n \emptyset$. अंततः हमने सिद्ध कर दिखाया कि  $\mathbb{Z}$ को $n$ असंयुक्त समशेष वर्गों के सम्मिलन के रूप में लिखा जा सकता है. इस प्रकार प्रत्येक पूर्णांक एक और केवल एक समशेष वर्ग में आविष्ट होता है.

आइये समशेष पूर्णांकों के गुणधर्मों पर विस्तार से चर्चा करें. हम जानते हैं कि $7$ और $12$ धनात्मक पूर्णांक $5$ के सापेक्ष समशेष हैं, अर्थात दोनों ही संख्याओं को $5$ से विभाजित करने पर समान शेषफल प्राप्त होता है. अतः यदि दोनों संख्याओं का अंतर लिया जाए, तो परिणामी संख्या $5$ से विभाज्य होती है. यह कोई संयोग नहीं है. यह प्रेक्षण व्यापक रूप में सत्य है. मान लीजिए $a$ और $b$ किसी धनात्मक पूर्णांक $n $ के सापेक्ष समशेष हैं, अर्थात $a \equiv b \pmod n$. तब $a$ और $b$ को $n$ से विभाजित करने पर समान शेषफल, मान लीजिए $r$, प्राप्त होता है. अतः हम $a$ और $b$ को निम्नलिखित रूप में लिख सकते हैं:
\begin{aligned}
a &= nk + r,\\
b &= nk' + r.
\end{aligned}
इसीलिये,
\[a - b = n(k-k').\]
इस प्रकार $n \mid (a - b)$. अब एक स्वाभाविक प्रश्न हमारे मन में उठता है कि यदि $n \mid (a - b)$, तो क्या $a$ और $b$ समशेष होंगे ? इसका उत्तर "हाँ" है. मान लीजिए $a$ और $b$ को $n$ से विभाजित करने शेषफल क्रमशः $r$ और $s$ प्राप्त होते हैं. तब हम लिख सकते हैं कि
\[a = nk + r ~ \text{और}~ b = nk' + s,\]
जहाँ $0 \leq r, s \leq n-1$. इसीलिये $a - b = n(k - k') + r - s$. फलस्वरूप $r - s = (a - b) - n(k - k')$. अब क्योंकि $n$ दोनों ही संख्याओं $a-b$ और $n(k - k')$ को विभाजित करता है, इसलिए $n \mid (a-b) - n(k-k')$. अर्थात $n \mid (r - s)$. क्योंकि $-(n-1) \leq (r-s) \leq (n-1)$, अतः एक ही संभावना बचती है : $r - s = 0$. इसलिए $r = s$. इस प्रकार $a \equiv b \pmod n$. उपरोक्त चर्चा को हम निम्नलिखित प्रमेय के रूप में व्यक्त करते हैं:

प्रमेय 4.1. यदि $a$ और $b$ पूर्णांक हों और $n$ एक धनात्मक पूर्णांक हो, तो $a \equiv b \pmod n$ यदि और केवल यदि $n \mid (a - b)$.

उदाहरण के लिए $17 \equiv 2 \pmod 5$, क्योंकि $5 \mid (17 - 2)$. इसी प्रकार $-13 \equiv -4 \pmod 3$, क्योंकि $-13 -(-4) = -13 + 4 = -9$ और $3 \mid (-9)$. अब हम समशेषता की एक वैकल्पिक परिभाषा दे सकते हैं.

परिभाषा 4.2. पूर्णांक $a$ और $b$ किसी नियत धनात्मक पूर्णांक $n$ के सापेक्ष समशेष होते हैं यदि $n \mid (a - b)$. इस स्थिति में हम $a \equiv b \pmod n$ लिखते हैं.

4.2. आधारभूत समशेषता गुणधर्म

इस अनुच्छेद में हम समशेष संख्याओं के गुणधर्मों पर चर्चा करेंगे. मान लीजिए $n$ एक नियत धनात्मक पूर्णांक है. अब क्योंकि किसी भी पूर्णांक $a$ के लिए, $n \mid (a - a)$, अतः $a \equiv a \pmod n$. यदि $a$ और $b$ समशेष पूर्णांक हों, अर्थात $a \equiv b \pmod n$, तो $n \mid (a-b)$. तब $n \mid (b-a)$. इसलिए $b \equiv a \pmod n$. इस प्रकार यदि $a \equiv b \pmod n$, तो $b \equiv a \pmod n$ भी होता है. अब मान लीजिए कि $a \equiv b \pmod n$ और $b \equiv c \pmod n$, तो क्या $a \equiv c \pmod n$ संभव है ? इस स्थिति में, $n \mid (a -b)$ और $n \mid (b-c)$. इसलिए $n \mid (a -b) + (b-c)$. अर्थात $n \mid (a - c)$. इस प्रकार $a \equiv c \pmod n$. उपरोक्त चर्चा में हमने निम्नलिखित प्रमेय सिद्ध किया है:

प्रमेय 4.3. मान लीजिए $n$ एक धनात्मक पूर्णांक है और $a, b, c$ स्वेच्छ पूर्णांक हैं. तब
(a) $a \equiv a \pmod n$;
(b) यदि $a \equiv b \pmod n$, तो $b \equiv a \pmod n$;
(c) यदि $a \equiv b \pmod n$ और $b \equiv c \pmod n$, तो $a \equiv c \pmod n$.

अगले प्रमेय में हम कुछ और महत्त्वपूर्ण गुणधर्मों को सिद्ध करते हैं.

प्रमेय 4.4. मान लीजिए $n$ एक धनात्मक पूर्णांक है और $a, b, c, d$ स्वेच्छ पूर्णांक हैं. तब
(a) यदि $a \equiv b \pmod n$, तो $a + c \equiv b + c \pmod n$;
(b) यदि $a \equiv b \pmod n$, तो $ac \equiv bc \pmod n$;
(c) यदि $a \equiv b \pmod n$ और $c \equiv d \pmod n$, तो $a + c \equiv b + d \pmod n$.
(d) यदि $a \equiv b \pmod n$ और $c \equiv d \pmod n$, तो $ac \equiv bd \pmod n$. 
(e) यदि $a \equiv b \pmod n$, तो प्रत्येक धनात्मक पूर्णांक $k$ के लिए $a^k \equiv b^k \pmod n$.


उपपत्ति: 
(a) (a + c) - (b + c) = a - b. अब क्योंकि $a \equiv b \pmod n$ जिससे कि $n \mid (a -b)$, इसलिए $a + c \equiv b + c \pmod n$.

(b) ac - bc = (a - b)c. अब क्योंकि $a \equiv b \pmod n$ जिससे कि $n \mid (a - b)$. फलस्वरूप $n \mid (a - b)c$. इसलिए $ac \equiv bc \pmod n$.

(c) (a + c) - (b + d) = (a - b) + (c - d). अब क्योंकि $a \equiv b \pmod n$ और $c \equiv d \pmod n$, इसलिए $n \mid (a - b)$ और $n \mid (c - d)$. फलतः $n \mid (a - b) + (c - d)$, अर्थात $n \mid (a + c) - (b + d)$. इसलिए $a + c \equiv b + d \pmod n$.

(d) क्योंकि $a \equiv b \pmod n$, इसलिए $a - b = nk$, जहाँ $k$ एक उपयुक्त पूर्णांक है. इस प्रकार $a = b + nk$. इसी प्रकार $c = d + n\ell$. इसलिए 
\[ac = (b + nk)(d + n\ell) = bd + bn\ell + nkd + n^2k\ell = bd + n(b\ell + kd + nk\ell).\]
अतः
\[ac - bd = n(b\ell + kd + nk\ell).\]
इस प्रकार $n \mid (ac - bd)$. अतः $ac \equiv bd \pmod n$.

(e) इसे सिद्ध करने के लिए हम $k$ पर आगमन सिद्धांत का प्रयोग करेंगे. स्पष्टतः हमारा कथन $k = 1$ के लिए सत्य है. मान लीजिए हमारा कथन किसी नियत $k$ के लिए सत्य है, अर्थात $a^k \equiv b^k \pmod n$. तब क्योंकि $a \equiv b \pmod n$ और $a^k \equiv b^k \pmod n$, भाग (d) का प्रयोग करने पर हमें $a^{k+1} \equiv b^{k + 1} \pmod n$ प्राप्त होता है. अतः हमारा कथन $k + 1$ के लिए भी सत्य होता है. अतः यह कथन सभी धनात्मक पूर्णांक $k$ के लिए सत्य है.

आइये हम कुछ और गुणधर्मों पर चर्चा करते है. मान लीजिए $a \equiv b \pmod n$. तब $n \mid (a - b)$. इसलिए $a - b = nk$, जहाँ $k$ एक उपयुक्त पूर्णांक है. अब यदि $d \mid n$, तो स्पष्टतः $d \mid (a -b)$. इसलिए $a \equiv b \pmod d$. उपरोक्त चर्चा में हमने निम्नलिखित प्रमेय सिद्ध किया है:

प्रमेय 4.5. मान लीजिए $n$ एक नियत धनात्मक पूर्णांक है और $a , b$ स्वेच्छ पूर्णांक हैं. पुनः मान लीजिए कि $a \equiv b \pmod n$. यदि $d \mid n$, तो $a \equiv b \pmod d$.

प्रमेय 4.4(b) में हमने सिद्ध किया था कि यदि $a \equiv b \pmod n$, तो $ac \equiv bc \pmod n$. क्या इसका विलोम भी सत्य है ? हमारा तात्पर्य है - यदि $ac \equiv bc \pmod n$, तो क्या $a \equiv b \pmod n$ सत्य होता है ? आइये एक उदाहरण पर विचार करते हैं. ध्यान दीजिये कि $5.11 \equiv 5.2 \pmod {15}$, परन्तु $11 \not\equiv 2 \pmod {15}$. अतः उपरोक्त कथन सत्य नहींहै. परन्तु निम्नलिखित कथन सत्य होता है.

प्रमेय 4.6. मान लीजिए $n$ एक नियत धनात्मक पूर्णांक है और $a , b, c$ स्वेच्छ पूर्णांक हैं. पुनः मान लीजिए कि $ac \equiv bc \pmod n$. तब $a \equiv b \pmod {n/d}$, जहाँ $d = \gcd(c, n)$.

उपपत्ति: 
क्योंकि $ac \equiv bc \pmod n$, हम लिख सकते हैं कि 
\[(a - b)c = ac - bc = nk,\]
जहाँ $k$ एक उपयुक्त पूर्णांक है. क्योंकि $d = \gcd(c, n)$, इसीलिए किन्हीं उपयुक्त पूर्णांकों $r$ और $s$ के लिए हम $c = dr$ और $n = ds$ लिख सकते हैं. अब इन मानों को उपरोक्त समीकरण में प्रतिस्थापित करने पर हमें प्राप्त होता है:
\[(a -b)dr = dsk.\]
इसलिए 
\[(a - b)r = sk.\]
अर्थात $s \mid (a - b)r$. अब क्योंकि $\gcd(r, s) = 1$ (देखें विभाज्यता सिद्धांत, उपप्रमेय 2.10), यूक्लिड प्रमेयिका (देखें विभाज्यता सिद्धांत, प्रमेय 2.12) के अनुसार $s \mid (a -b)$. अर्थात $a \equiv b \pmod s$. अतः $a \equiv b \pmod {n/d}$.






यह पृष्ठ अभी प्रगति में है.......

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

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

शीर्ष पर जाएँ