संख्या पद्धति: विभाज्यता, गुणनखंड, शेषफल व आधार

CAT जिस संख्या-रेखा पर काम करता है: प्राकृत संख्याएँ N = {1, 2, 3, …} ⊂ पूर्ण संख्याएँ W = {0, 1, 2, …} ⊂ पूर्णांक Z ⊂ परिमेय Q (प्रत्येक p/q, जिनके दशमलव सांत या आवर्ती होते हैं) ⊂ वास्तविक R, जहाँ Q व R के बीच का अंतर अपरिमेय (√2, π) भरते हैं। N के भीतर अभाज्य के ठीक दो गुणनखंड होते हैं; 1 न अभाज्य है न भाज्य, 2 एकमात्र सम अभाज्य है, और 100 से नीचे ठीक 25 अभाज्य हैं। 3 से बड़ा प्रत्येक अभाज्य 6k ± 1 रूप का है (विलोम असत्य: 25 = 6·4 + 1)। n अभाज्य है या नहीं, इसके लिए केवल √n तक के अभाज्यों से भाग परखें: 221 हेतु √221 ≈ 14.9, अतः 2, 3, 5, 7, 11, 13 परखें — और 221 = 13 × 17 भाज्य है। 199 हेतु वही छह परीक्षण विफल रहते हैं, अतः 199 अभाज्य है।

• कोई तीन-अंकीय खंड दोहराया जाए तो वह 7, 11 व 13 से विभाज्य है। abcabc = abc × 1001, और 1001 = 7 × 11 × 13। अतः 481,481 ÷ 13 का शेषफल बिना एक भी भाग किए 0; इसी तरह abab = ab × 101 और abcdabcd = abcd × 10001 = abcd × 73 × 137।
• अंक पलटना। दो-अंकीय संख्या 10a + b का उल्टा 10b + a है। उनका योग 11(a + b) और अंतर 9(a − b) होता है। अतः "एक दो-अंकीय संख्या अपने उल्टे से 27 अधिक है" का अर्थ एक पंक्ति में a − b = 3, और दोनों संख्याओं का योग सदा 11 का गुणज। किसी भी लंबाई पर यह सत्य है: संख्या घटा उसका अंक-उल्टा सदा 9 से विभाज्य।
• अज्ञात अंकों वाला हल उदाहरण। यदि 4a3 + 984 = 13b7 और 13b7, 11 से विभाज्य है, तो a व b ज्ञात करें। इकाई: 3 + 4 = 7 ✓। सैकड़ा: 4 + 9 = 13 ठीक, अर्थात दहाई स्तंभ से कोई हासिल नहीं आया, अतः a + 8 = b तथा a + 8 ≤ 9, जिससे (a, b) = (0, 8) या (1, 9)। अब 13b7 पर 11-परीक्षण: (1 + b) − (3 + 7) = b − 9 शून्य या ±11 होना चाहिए, अतः b = 9, a = 1। जाँच: 413 + 984 = 1,397 = 11 × 127 ✓।

N = p^a · q^b · r^c (भिन्न अभाज्य) लिखें। तब गुणनखंडों की संख्या (a + 1)(b + 1)(c + 1), गुणनखंडों का योग (1 + p + … + p^a)(1 + q + … + q^b)(1 + r + … + r^c), तथा सभी गुणनखंडों का गुणनफल N^(d/2) जहाँ d गुणनखंडों की संख्या है — क्योंकि गुणनखंड (f, N/f) के जोड़ों में बँटते हैं जिनका गुणनफल N है। 360 = 2³ × 3² × 5 पर पूर्ण हल: गुणनखंडों की संख्या = 4 × 3 × 2 = 24; योग = (1 + 2 + 4 + 8)(1 + 3 + 9)(1 + 5) = 15 × 13 × 6 = 1,170; गुणनफल = 360¹²। विषम गुणनखंड 2 की घात छोड़ देते हैं: 3 × 2 = 6, अतः सम गुणनखंड 24 − 6 = 18। पूर्ण वर्ग गुणनखंड केवल सम घातांक लेते हैं: 2⁰ या 2², 3⁰ या 3², 5⁰ → 2 × 2 × 1 = 4 (अर्थात 1, 4, 9, 36)।

• गुणनखंडन से म.स. व ल.स.। म.स. प्रत्येक साझा अभाज्य की न्यूनतम घात लेता है; ल.स. उपस्थित प्रत्येक अभाज्य की उच्चतम घात। 360 = 2³·3²·5 व 84 = 2²·3·7 हेतु: म.स. = 2²·3 = 12, ल.स. = 2³·3²·5·7 = 2,520। दो संख्याओं हेतु म.स. × ल.स. = गुणनफल: 12 × 2,520 = 30,240 = 360 × 84 ✓। तीन या अधिक संख्याओं पर यह सर्वसमिका विफल है — एक सामान्य जाल।
• भिन्नें। भिन्नों का म.स. = अंशों का म.स. ÷ हरों का ल.स.; भिन्नों का ल.स. = अंशों का ल.स. ÷ हरों का म.स.। 2/3, 4/9, 8/15 हेतु: म.स. = म.स.(2, 4, 8)/ल.स.(3, 9, 15) = 2/45; ल.स. = ल.स.(2, 4, 8)/म.स.(3, 9, 15) = 8/3।
• घंटियाँ (ल.स.)। तीन घंटियाँ प्रत्येक 6, 8 व 12 सेकंड पर बजती हैं और साथ आरंभ करती हैं। वे प्रत्येक ल.स.(6, 8, 12) = 24 s पर साथ बजती हैं। 30 मिनट = 1,800 s में यह 1,800/24 = 75 और बार, अतः आरंभ सहित 76 बार — "आरंभ के लिए +1" यहीं अंक खोए जाते हैं।
• टाइलें (म.स.)। 4.5 m × 3.6 m फर्श को ठीक-ठीक ढकने वाली सबसे बड़ी वर्गाकार टाइल की भुजा म.स.(450, 360) = 90 cm, और टाइलों की संख्या (450/90) × (360/90) = 5 × 4 = 20।
• समान शेषफल (अंतरों का म.स.)। 62, 132 व 237 को विभाजित कर हर बार समान शेषफल छोड़ने वाली सबसे बड़ी संख्या उनके अंतरों 70, 105 व 175 को विभाजित करती है, अतः वह म.स.(70, 105, 175) = 35 है (साझा शेषफल 27)। यदि शेषफल भाजकों की कमी हों — N को 3, 4, 5 से भाग देने पर 1, 2, 3 शेष — तो N + 2 ल.स. = 60 का गुणज है, अतः न्यूनतम N = 58।

मूल शेषफल प्रमेय: गुणनफल का शेषफल शेषफलों का गुणनफल (पुनः घटाया हुआ) है, और योग का शेषफल शेषफलों का योग। अतः 17 × 23 × 31 को 7 से भाग देने पर 3 × 2 × 3 = 18 → 4 (जाँच: 12,121 = 7 × 1,731 + 4 ✓)। शेषफल को ऋणात्मक भी लिखा जा सकता है: 15 ≡ −1 (mod 16), अतः 15^20 ≡ (−1)^20 = 1 (mod 16)। और 2⁴ = 16 ≡ −1 (mod 17), अतः 2^32 = (2⁴)⁸ ≡ (−1)⁸ = 1 (mod 17)। जब भी आधार की कोई घात भाजक से एक कम या एक अधिक हो, ऋणात्मक-शेषफल मार्ग सबसे तेज़ है।

• फ़र्मा, हल। 7^100 को 11 से भाग देने पर शेषफल: 11 अभाज्य है और 7 को विभाजित नहीं करता, अतः 7^10 ≡ 1 (mod 11)। तब 7^100 = (7^10)^10 ≡ 1^10 = 1। पुनः: 2^100 ÷ 13। यहाँ 2^12 ≡ 1, और 100 = 12 × 8 + 4, अतः 2^100 ≡ 2⁴ = 16 ≡ 3 (mod 13)। पूरी विधि है "घातांक को p − 1 से घटाएँ"।
• ऑयलर, हल। 2^100 को 9 से भाग देने पर शेषफल: म.स.(2, 9) = 1 और φ(9) = 9(1 − 1/3) = 6, अतः 2⁶ ≡ 1 (mod 9)। 100 = 6 × 16 + 4, अतः 2^100 ≡ 2⁴ = 16 ≡ 7 (mod 9)। ऋणात्मक मार्ग से जाँच: 2³ = 8 ≡ −1, अतः 2^100 = (2³)^33 × 2 ≡ (−1)^33 × 2 = −2 ≡ 7 ✓। उपयोगी मान: φ(100) = 100 × ½ × ⅘ = 40, φ(20) = 8, φ(36) = 12, φ(p) = p − 1।
• निरीक्षण द्वारा चीनी शेषफल। न्यूनतम N ज्ञात करें जिसके लिए N ≡ 2 (mod 3), N ≡ 3 (mod 5), N ≡ 2 (mod 7)। सबसे बड़े मापांक से आरंभ करें: प्रत्याशी 2, 9, 16, 23, 30, …; 5 से भाग देने पर 3 शेष छोड़ने वाला पहला 23 है; और 23 ÷ 3 का शेष 2 ✓। अतः N = 23, और व्यापक हल 23 + 105k। जब सभी शेषफल समान हों, तो सीधे N = ल.स.·k + r: 4, 5, 6 से भाग देने पर 3 शेष → N = 60k + 3।
• भाजक नए भाजक का गुणज है। एक संख्या 899 = 29 × 31 से भाग देने पर 63 शेष छोड़ती है। 29 से भाग देने पर वह 63 mod 29 = 5 छोड़ती है, क्योंकि N = 899q + 63 और 899q पहले से 29 का गुणज है। यह केवल तब काम करता है जब नया भाजक पुराने को विभाजित करे; अन्यथा शेषफल निर्धारित नहीं किया जा सकता।
• क्रमगुणित योग। 1! + 2! + 3! + … + 100! को 24 से भाग देने पर शेषफल: 4! = 24 से आगे प्रत्येक पद 24 का गुणज है, अतः केवल 1 + 2 + 6 = 9 बचता है। यही विचार 1! + 2! + … + 50! mod 5 → 1 + 2 + 6 + 24 = 33 → 3 देता है।

a^n का अंतिम अंक केवल a के अंतिम अंक और चक्र-लंबाई से n के शेषफल पर निर्भर है। अंक 0, 1, 5, 6 स्थिर बिंदु हैं; 4 व 9 आवर्त 2 से बदलते हैं; और 2, 3, 7, 8 का आवर्त 4 का चक्र है। अतः 3^47 का इकाई अंक 47 ≡ 3 (mod 4) से मिलता है: 3, 9, 7, 1 की तीसरी प्रविष्टि 7। 2^50 हेतु: 50 ≡ 2 (mod 4), 2, 4, 8, 6 की दूसरी प्रविष्टि 4। जब n, 4 का गुणज हो, तो चौथी प्रविष्टि लें, "शून्यवीं" नहीं — 3^100 का अंत 1 से होता है, 3 से नहीं।

• अंतिम दो अंक, आधार का अंत 1 से। (…a1)^n हेतु इकाई अंक 1 और दहाई अंक a × n का इकाई अंक। अतः 21^37 → दहाई = 2 × 37 = 74 का इकाई = 4, जिससे 41। और 31^40 → 3 × 40 = 120 का इकाई = 0, जिससे 01।
• अंतिम दो अंक, आधार का अंत 3, 7 या 9 से। पहले ऐसी घात तक ले जाएँ जो 1 पर समाप्त हो: 3⁴ = 81, 7⁴ = 2,401, 9² = 81। अतः 3^80 = (3⁴)^20 = 81^20 → दहाई = 8 × 20 = 160 का इकाई = 0, जिससे 01। 13^25 हेतु: 13⁴ = 28,561 → 61 मानें; 13^25 = (13⁴)⁶ × 13 → 61⁶ का अंत (6 × 6 = 36 → 6)1 = 61, और 61 × 13 = 793 → 93।
• अंतिम दो अंक, सम आधार। 2^10 = 1,024 → 24 प्रयोग करें, और 24^विषम → 24, 24^सम → 76। अतः 2^100 = (2^10)^10 → 24^10 → 76। 25 पर समाप्त होने वाली कोई संख्या 25 पर ही समाप्त होती रहती है; 76 भी 76 पर; यही दो "स्थिर" अंत हैं।
• लजांड्र सूत्र। n! में अभाज्य p की उच्चतम घात ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + … है। 100! में: 5 की घात = 20 + 4 = 24; 2 की घात = 50 + 25 + 12 + 6 + 3 + 1 = 97; 3 की घात = 33 + 11 + 3 + 1 = 48। n! के अंतिम शून्य = 5 की घात (2 सदा अधिक होते हैं), अतः 100! का अंत 24 शून्यों से और 125! का 25 + 5 + 1 = 31 से। 6 = 2 × 3 जैसे भाज्य हेतु अभाज्यों पर न्यूनतम लें: 100! में 6 की घात min(97, 48) = 48। 12 = 2² × 3 हेतु: min(⌊97/2⌋, 48) = min(48, 48) = 48।
• अंतिम शून्य मान छोड़ते हैं। 24! के 4 अंतिम शून्य हैं और 25! के सीधे 6, अतः कोई क्रमगुणित ठीक 5 शून्यों पर समाप्त नहीं होता — इसी तरह कोई ठीक 11, 17, 23, 29 या 30 पर नहीं। "n ज्ञात करें जिसके लिए n! में ठीक 30 शून्य हों" का उत्तर कोई नहीं; 124! → 28, 125! → 31 की छलाँग 29 व 30 छोड़ देती है। अन्य आधार में शून्य भी इसी विचार से: आधार 12 = 2² × 3 में 10! के min(⌊8/2⌋, 4) = 4 अंतिम शून्य, क्योंकि 10! में 2⁸ व 3⁴ हैं।

आधार b में अंक 0 से b − 1 तक चलते हैं और स्थानीय मान 1, b, b², b³, … हैं। आधार b में बदलने हेतु बार-बार भाग दें और शेषफल नीचे से ऊपर पढ़ें। 2,021 को आधार 8 में: 2,021 ÷ 8 = 252 शेष 5; 252 ÷ 8 = 31 शेष 4; 31 ÷ 8 = 3 शेष 7; 3 ÷ 8 = 0 शेष 3। ऊपर की ओर पढ़ने पर: (3745)₈। विस्तार से जाँच: 3 × 512 + 7 × 64 + 4 × 8 + 5 = 1,536 + 448 + 32 + 5 = 2,021 ✓। आधार b से बदलने हेतु स्थानीय मान विस्तारित करें: (1011)₂ = 8 + 0 + 2 + 1 = 11, और (2A5)₁₆ = 2 × 256 + 10 × 16 + 5 = 677।

• आधार b में अंकगणित: हासिल b पर, 10 पर नहीं। (27)₈ + (15)₈: इकाई 7 + 5 = 12 = 1 × 8 + 4, 4 लिखें हासिल 1; फिर 2 + 1 + 1 = 4। उत्तर (44)₈। दशमलव में जाँच: 23 + 13 = 36 = 4 × 8 + 4 ✓। घटाने में b उधार लें: (52)₈ − (27)₈ → इकाई 2 − 7 हेतु 8 उधार: 10 − 7 = 3; फिर 4 − 2 = 2 → (23)₈ (42 − 23 = 19 = 2 × 8 + 3 ✓)।
• आधार ज्ञात करें। "किसी आधार में 34 = 2 × 15" → 3b + 4 = 2(b + 5) = 2b + 10 → b = 6। जाँच: (34)₆ = 22, (15)₆ = 11 ✓। आधार प्रयुक्त प्रत्येक अंक से बड़ा होना चाहिए, अतः अंक 5 की उपस्थिति में उत्तर b = 4 अमान्य है — CAT इससे एक विकल्प काटता है।
• विभाज्यता परीक्षण किसी भी आधार में चलते हैं। आधार b में संख्या b − 1 से ठीक तब विभाज्य है जब उसका अंक-योग हो (आधार-10 का "9 का नियम"), और b + 1 से जब उसका एकांतर अंक-योग हो ("11 का नियम")। अतः आधार 8 में (3745)₈ का अंक-योग 19 → 19 mod 7 = 5, और वास्तव में 2,021 = 7 × 288 + 5 ✓। आधार b में N के अंकों की संख्या ⌊log_b N⌋ + 1: 2,021, 8³ = 512 व 8⁴ = 4,096 के बीच है, अतः इसके 4 अष्टाधारी अंक हैं।

अंक-योग व अंकीय मूल। क्योंकि 10 ≡ 1 (mod 9), प्रत्येक संख्या 9 के — और 3 के — मापांक में अपने अंक-योग के सर्वांगसम है। एक अंक बचने तक अंक-योग दोहराने से अंकीय मूल मिलता है, जो N mod 9 के बराबर है (9 का अर्थ 0)। CAT तीन परिणाम प्रयोग करता है: (i) संख्या घटा उसका अंक-योग सदा 9 से विभाज्य; (ii) पूर्ण वर्ग का अंकीय मूल सदा 1, 4, 7 या 9 होता है, अतः जिस संख्या का अंकीय मूल 2, 3, 5, 6 या 8 हो (जैसे 4,325 → 14 → 5) वह वर्ग नहीं हो सकती; (iii) 2^100 का अंकीय मूल उसका mod 9 शेषफल है, जो ऊपर 7 निकला। अंक गिनना: 1 से 999 लिखने में तीनों स्थानों में प्रत्येक अंक 0–9 ठीक 100 बार आता है, अतः सभी अंकों का योग 3 × 100 × 45 = 13,500; और 1 से 100 लिखने में 9 + 90 × 2 + 3 = 192 अंक लगते हैं।