विभाज्यता और यूक्लिड विभाजन
हम कहते हैं n, a को विभाजित करता है (n | a) यदि किसी पूर्णांक k के लिए a = n × k हो। उदाहरण: 5 | 35, क्योंकि 35 = 5 × 7।
यूक्लिड विभाजन: किसी भी पूर्णांक a और पूर्ण संख्या n ≥ 1 के लिए ठीक एक जोड़ी q, r ऐसी होती है कि
a = n × q + r, और 0 ≤ r < n।
q भागफल और r शेषफल है। ऋणात्मक a के लिए भी शेषफल 0 से n − 1 के बीच रहता है: −7 = 5 × (−2) + 3, इसलिए शेषफल 3 है, −2 नहीं।
उपयोगी बात: यदि n | a और n | b, तो n, a + b, a − b और a × x + b × y को भी विभाजित करता है।
मॉड्यूलो n सर्वांगसमता
a ≡ b (mod n) का अर्थ है a और b को n से भाग देने पर शेषफल समान है। यानी n | (a − b)।
- 17 ≡ 2 (mod 5), क्योंकि 17 − 2 = 15 = 5 × 3।
- हर पूर्णांक 0, 1, …, n − 1 में से ठीक एक के सर्वांगसम होता है: अपने शेषफल के।
- a ≡ 0 (mod n) यानी n, a को विभाजित करता है।
n अंकों वाली घड़ी सोचिए: सर्वांगसम संख्याएँ एक ही जगह रुकती हैं।
सर्वांगसमताओं पर संक्रियाएँ
यदि a ≡ b और c ≡ d (mod n), तो:
- a + c ≡ b + d और a − c ≡ b − d
- a × c ≡ b × d
- किसी भी पूर्ण संख्या k के लिए ak ≡ bk
घातों के शेषफल चक्र में दोहराते हैं। चक्र ढूँढिए, फिर घातांक का शेषफल लीजिए।
उदाहरण: 3k mod 7: 3, 2, 6, 4, 5, 1, फिर हर 6 पर दोहराव। 100 = 6 × 16 + 4, इसलिए 3100 ≡ 34 ≡ 4 (mod 7)।
सावधान: भाग हमेशा नहीं कर सकते। 2 × 3 ≡ 2 × 8 (mod 10), पर 3 ≢ 8 (mod 10)। कोई गुणनखंड तभी काट सकते हैं जब उसका n से कोई उभयनिष्ठ गुणनखंड न हो।
सर्वांगसमता से विभाज्यता के नियम
- 2, 5, 10 से: 10 ≡ 0, इसलिए केवल अंतिम अंक मायने रखता है।
- 4 (और 25) से: 100 ≡ 0, इसलिए केवल अंतिम दो अंक।
- 3 और 9 से: 10 ≡ 1, इसलिए 10 की हर घात ≡ 1। संख्या ≡ अंकों का योग।
- 11 से: 10 ≡ −1, इसलिए संख्या ≡ दाएँ से अंकों का एकांतर योग (+ − + …)।
उदाहरण: 7 392: अंकों का योग 21, 3 से विभाज्य, तो 7 392 भी। एकांतर योग 2 − 9 + 3 − 7 = −11, तो 11 से भी विभाज्य।
सरल पूर्णांक समीकरण
सर्वांगसमता जल्दी बता देती है कि समीकरण का कोई पूर्णांक हल नहीं है। उदाहरण: x² = 4y + 3। mod 4 में वर्ग केवल 0 या 1 होते हैं (0² = 0, 1² = 1, 2² = 4 ≡ 0, 3² = 9 ≡ 1), पर दायाँ पक्ष ≡ 3 (mod 4)। इसलिए कोई पूर्णांक हल नहीं।
रैखिक सर्वांगसमता 3x ≡ 4 (mod 7): x = 0…6 आज़माइए: 3 × 6 = 18 ≡ 4, इसलिए x ≡ 6 (mod 7), यानी x = 7k + 6।
मुख्य सूत्र और परिभाषाएँ
- a = n × q + r, 0 ≤ r < n
- a ≡ b (mod n) ⇔ n | (a − b)
- a ≡ b, c ≡ d ⇒ a ± c ≡ b ± d, ac ≡ bd
- a ≡ b ⇒ aᵏ ≡ bᵏ (mod n)
- 10 ≡ 1 (mod 9) and 10 ≡ −1 (mod 11)
हल किए गए उदाहरण
1. 100 का 7 से यूक्लिड विभाजन लिखिए।
7 × 14 = 98 और 100 − 98 = 2। तो 100 = 7 × 14 + 2: q = 14, r = 2।
2. −23 को 6 से भाग देने पर शेषफल?
6 × (−4) = −24, और −23 − (−24) = 1। तो −23 = 6 × (−4) + 1, शेषफल 1।
3. क्या 1 234 ≡ 4 (mod 9)?
अंकों का योग 10 ≡ 1 (mod 9)। तो 1 234 ≡ 1, 4 नहीं। कथन ग़लत है।
4. 47 × 58 को 5 से भाग देने पर शेषफल?
47 ≡ 2, 58 ≡ 3 (mod 5)। 2 × 3 = 6 ≡ 1। शेषफल 1। (जाँच: 2 726 = 5 × 545 + 1)
5. 2¹⁰⁰ को 7 से भाग देने पर शेषफल?
2 ≡ 2, 2² ≡ 4, 2³ = 8 ≡ 1 (mod 7)। चक्र 3 का। 100 = 3 × 33 + 1, तो 2¹⁰⁰ = (2³)³³ × 2 ≡ 2।
6. दिखाइए कि हर पूर्णांक n के लिए n³ − n, 3 से विभाज्य है।
n ≡ 0, 1 या 2 (mod 3)। n³ − n = (n − 1)n(n + 1)। 0 → 0; 1 → 0; 2 → 8 − 2 = 6 ≡ 0। हर स्थिति में ≡ 0, इसलिए 3 से विभाज्य।
आम गलतियाँ
- ऋणात्मक शेषफल देना: शेषफल 0 से n − 1 के बीच होना चाहिए (−7 mod 5 = 3, −2 नहीं)।
- सर्वांगसमता के दोनों पक्षों को ऐसी संख्या से भाग देना जिसका n से उभयनिष्ठ गुणनखंड हो।
- बड़ी घात पूरी गणना करना, बजाय हर कदम पर घटाने और चक्र इस्तेमाल करने के।
- चक्र की लंबाई जाने बिना घातांक का शेषफल लेना (2ᵏ mod 7 का चक्र 3 है, 7 नहीं)।