संख्या सिद्धांत और विभाज्यता

ज़रूर, मैं आपकी मदद कर सकता हूँ। नीचे अपडेटेड स्टडी नोट्स दिए गए हैं:

संख्या सिद्धांत

• संख्या सिद्धांत गणित की एक शाखा है जो मुख्य रूप से पूर्णांकों और पूर्णांक-मूल्यवान कार्यों के अध्ययन के लिए समर्पित है।
• अभाज्य संख्याएँ, विभाज्यता, और सर्वांगसमताएँ संख्या सिद्धांत के केंद्र में हैं।

विभाज्यता

• एक पूर्णांक $a$ एक पूर्णांक $b$ से विभाज्य है यदि कोई पूर्णांक $k$ ऐसा है कि $a = bk$।
• संकेतन: $b \mid a$, जिसे "$b$, $a$ को विभाजित करता है" के रूप में पढ़ा जाता है।
• यदि $b \mid a$, तो $b$, $a$ का भाजक या गुणनखंड है, और $a$, $b$ का गुणज है।
• विभाज्यता के गुण:
  • यदि $a \mid b$ और $b \mid c$, तो $a \mid c$।
  • यदि $a \mid b$ और $a \mid c$, तो किसी भी पूर्णांक $x$ और $y$ के लिए $a \mid (bx + cy)$।
  • यदि $a \mid b$, तो किसी भी पूर्णांक $c$ के लिए $a \mid bc$।
  • यदि $a \mid b$ और $b \mid a$, तो $a = \pm b$।
  • यदि $a \mid 1$, तो $a = \pm 1$।
  • यदि $a \mid b$ और $a > 0, b > 0$, तो $a \leq b$।

विभाजन एल्गोरिथ्म

• $b > 0$ के साथ पूर्णांकों $a$ और $b$ के लिए, अद्वितीय पूर्णांक $q$ और $r$ मौजूद हैं जैसे कि $a = bq + r$, जहाँ $0 \leq r < b$।
• $a$ भाज्य है, $b$ भाजक है, $q$ भागफल है, और $r$ शेषफल है।

महत्तम समापवर्तक (GCD)

• दो पूर्णांकों $a$ और $b$ का महत्तम समापवर्तक, जिसे $\gcd(a, b)$ के रूप में दर्शाया गया है, सबसे बड़ा धनात्मक पूर्णांक है जो $a$ और $b$ दोनों को विभाजित करता है।
• यदि $\gcd(a, b) = 1$, तो $a$ और $b$ सापेक्षिक रूप से अभाज्य या सहअभाज्य हैं।
• GCD के गुण:
  • $\gcd(a, b) = \gcd(b, a)$।
  • $\gcd(a, b) = \gcd(a, -b)$।
  • $\gcd(a, 0) = |a|$।
  • यदि $a \mid b$, तो $\gcd(a, b) = |a|$।
  • $\gcd(a, b) = \gcd(b, a \mod b)$।

यूक्लिडियन एल्गोरिथ्म

• यूक्लिडियन एल्गोरिथ्म दो पूर्णांकों के GCD की गणना करने के लिए एक कुशल विधि है।
• यह इस गुण पर आधारित है: $\gcd(a, b) = \gcd(b, a \mod b)$।
• एल्गोरिथ्म:
  • दिए गए पूर्णांक $a$ और $b$, जहाँ $a \geq b > 0$।
  • $r_0 = a$ और $r_1 = b$ सेट करें।
  • पुनरावृत्त रूप से विभाजन एल्गोरिथ्म लागू करें: $r_{i-2} = r_{i-1}q_i + r_i$, जहाँ $0 \leq r_i < r_{i-1}$।
  • $r_n = 0$ तक जारी रखें।
  • तो $\gcd(a, b) = r_{n-1}$।

लघुत्तम समापवर्त्य (LCM)

• दो पूर्णांकों $a$ और $b$ का लघुत्तम समापवर्त्य, जिसे $\operatorname{lcm}(a, b)$ के रूप में दर्शाया गया है, सबसे छोटा धनात्मक पूर्णांक है जो $a$ और $b$ दोनों का गुणज है।
• GCD और LCM के बीच संबंध: $\gcd(a, b) \cdot \operatorname{lcm}(a, b) = |ab|$।

अभाज्य संख्याएँ

• एक अभाज्य संख्या 1 से बड़ी एक पूर्णांक है जिसके ठीक दो अलग-अलग धनात्मक भाजक होते हैं: 1 और स्वयं।
• एक भाज्य संख्या 1 से बड़ा एक पूर्णांक है जो अभाज्य नहीं है; इसके दो से अधिक अलग-अलग धनात्मक भाजक होते हैं।
• संख्या 1 न तो अभाज्य है और न ही भाज्य।
• पहली कुछ अभाज्य संख्याएँ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... हैं।

अंकगणित का मौलिक प्रमेय

• 1 से बड़े प्रत्येक पूर्णांक को अभाज्य संख्याओं के गुणनफल के रूप में विशिष्ट रूप से व्यक्त किया जा सकता है, कारकों के क्रम तक।
• इस निरूपण को पूर्णांक का अभाज्य गुणनखंडन कहा जाता है।
• उदाहरण: $12 = 2^2 \cdot 3$।

सर्वांगसमताएँ

• मान लीजिए कि $a, b, m$ पूर्णांक हैं जहाँ $m > 0$। तब $a$, $b$ के सर्वांगसम मापांक $m$ है, जिसे $a \equiv b \pmod{m}$ के रूप में लिखा जाता है, यदि $m \mid (a - b)$।
• दूसरे शब्दों में, $a$ और $b$ को $m$ से विभाजित करने पर समान शेषफल प्राप्त होता है।
• सर्वांगसमता के गुण:
  • यदि $a \equiv b \pmod{m}$ और $c \equiv d \pmod{m}$, तो $a + c \equiv b + d \pmod{m}$।
  • यदि $a \equiv b \pmod{m}$ और $c \equiv d \pmod{m}$, तो $ac \equiv bd \pmod{m}$।
  • यदि $a \equiv b \pmod{m}$, तो किसी भी धनात्मक पूर्णांक $k$ के लिए $a^k \equiv b^k \pmod{m}$।
  • यदि $ac \equiv bc \pmod{m}$ और $\gcd(c, m) = 1$, तो $a \equiv b \pmod{m}$।
  • $a \equiv b \pmod{m}$ यदि और केवल यदि किसी पूर्णांक $k$ के लिए $a = b + km$।

रैखिक सर्वांगसमताएँ

• एक रैखिक सर्वांगसमता $ax \equiv b \pmod{m}$ के रूप का एक सर्वांगसमता है, जहाँ $a, b, m$ पूर्णांक हैं और $m > 0$।
• सर्वांगसमता $ax \equiv b \pmod{m}$ का हल है यदि और केवल यदि $\gcd(a, m) \mid b$।
• यदि $\gcd(a, m) \mid b$, तो मापांक $m$ के ठीक $\gcd(a, m)$ असंगत हल हैं।

मॉड्यूलर इनवर्स

• एक पूर्णांक $x$, $a$ का मॉड्यूलर इनवर्स मापांक $m$ है यदि $ax \equiv 1 \pmod{m}$।
• $a$ का मॉड्यूलर इनवर्स मापांक $m$ मौजूद है यदि और केवल यदि $\gcd(a, m) = 1$।
• यदि मॉड्यूलर इनवर्स मौजूद है, तो यह मापांक $m$ अद्वितीय है।
• मॉड्यूलर इनवर्स को विस्तारित यूक्लिडियन एल्गोरिथ्म का उपयोग करके पाया जा सकता है।

विस्तारित यूक्लिडियन एल्गोरिथ्म

• दिए गए पूर्णांक $a$ और $b$, विस्तारित यूक्लिडियन एल्गोरिथ्म पूर्णांक $x$ और $y$ ज्ञात करता है जैसे कि $ax + by = \gcd(a, b)$।
• यदि $\gcd(a, m) = 1$, तो $ax + my = 1$, और $x$, $a$ का मॉड्यूलर इनवर्स मापांक $m$ है।

फ़र्मेट का छोटा प्रमेय

• यदि $p$ एक अभाज्य संख्या है और $a$ एक पूर्णांक है जो $p$ से विभाज्य नहीं है, तो $a^{p-1} \equiv 1 \pmod{p}$।
• एक उपप्रमेय यह है कि किसी भी पूर्णाक $a$ के लिए, $a^p \equiv a \pmod{p}$।
• फ़र्मेट का छोटा प्रमेय एक अभाज्य संख्या मापांक के बड़े घातांकों को शामिल करने वाली गणनाओं को सरल बनाने के लिए उपयोगी है।

यूलर का टोटिएंट फंक्शन

• यूलर का टोटिएंट फलन, जिसे $\phi(n)$ के रूप में दर्शाया गया है, $n$ से कम या उसके बराबर धनात्मक पूर्णांकों की संख्या है जो $n$ से सापेक्षिक रूप से अभाज्य हैं।
• $\phi(n) = |{k \in \mathbb{Z}^+ \mid 1 \leq k \leq n \text{ और } \gcd(n, k) = 1}|$।
• यदि $p$ एक अभाज्य संख्या है, तो $\phi(p) = p - 1$।
• यदि $n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$, $n$ का अभाज्य गुणनखंडन है, तो $\phi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_r}\right)$।
• यदि $\gcd(m, n) = 1$, तो $\phi(mn) = \phi(m) \phi(n)$।

यूलर का प्रमेय

• यदि $a$ और $n$ सापेक्षिक रूप से अभाज्य पूर्णांक हैं, तो $a^{\phi(n)} \equiv 1 \pmod{n}$।
• यूलर का प्रमेय फ़र्मेट के छोटे प्रमेय का सामान्यीकरण है।

चीनी शेषफल प्रमेय (CRT)

• चीनी शेषफल प्रमेय युग्मवार सापेक्षिक रूप से अभाज्य मापांकों के साथ सर्वांगसमताओं की एक प्रणाली का हल प्रदान करता है।
• दिए गए पूर्णांक $n_1, n_2, \dots, n_k$ जो युग्मवार सापेक्षिक रूप से अभाज्य हैं (यानी, $i \neq j$ के लिए $\gcd(n_i, n_j) = 1$), और पूर्णांक $a_1, a_2, \dots, a_k$, सर्वांगसमताओं की प्रणाली $$x \equiv a_1 \pmod{n_1}$$ $$x \equiv a_2 \pmod{n_2}$$ $$\vdots$$ $$x \equiv a_k \pmod{n_k}$$ का $N = n_1 n_2 \cdots n_k$ के मापांक के साथ एक अद्वितीय हल है।
• हल ज्ञात करने के लिए:
  • $N = n_1 n_2 \cdots n_k$ की गणना करें।
  • प्रत्येक $i$ के लिए, $N_i = \frac{N}{n_i}$ की गणना करें।
  • मापांक $n_i$ का मॉड्यूलर इनवर्स $x_i$ ज्ञात करें, यानी, $N_i x_i \equiv 1 \pmod{n_i}$।
  • हल $x \equiv \sum_{i=1}^k a_i N_i x_i \pmod{N}$ द्वारा दिया गया है।