सामग्री

• पावले
• 3 पैकी 1 भाग: साधेपणाच्या चाचण्या
• 3 पैकी 2 भाग: साधेपणा चाचण्या कशा कार्य करतात
• भाग 3 मधील 3: चीनी उर्वरित प्रमेय वापरणे
• टिपा
• आपल्याला काय आवश्यक आहे

अभाज्य संख्या ही अशी संख्या आहे जी केवळ स्वतः आणि 1. द्वारे विभागली जाऊ शकते. इतर सर्व संख्यांना संयुक्त संख्या म्हणतात. संख्या अभाज्य आहे का हे ठरवण्याचे अनेक मार्ग आहेत आणि त्या सर्वांचे स्वतःचे फायदे आणि तोटे आहेत. एकीकडे, काही पद्धती अगदी अचूक आहेत, परंतु जर तुम्ही मोठ्या संख्येने व्यवहार करत असाल तर त्या खूपच जटिल आहेत. दुसरीकडे, बरेच वेगवान मार्ग आहेत, परंतु ते चुकीचे परिणाम देऊ शकतात. योग्य पद्धतीची निवड आपण किती मोठ्या संख्येने काम करत आहात यावर अवलंबून असते.

पावले

3 पैकी 1 भाग: साधेपणाच्या चाचण्या

टीप: सर्व सूत्रांमध्ये n तपासली जाणारी संख्या दर्शवते.

1. 1 विभाजकांची गणना. विभाजन करणे पुरेसे आहे n 2 पासून गोलाकार मूल्यापर्यंत सर्व अभाज्य संख्यांना (${ प्रदर्शन शैली { sqrt {n}}}$).
2. 2 फर्मॅटचे छोटे प्रमेय. चेतावणी: कधीकधी चाचणी संमिश्र संख्यांना प्राइम म्हणून चुकीची ओळखेल, अगदी a च्या सर्व मूल्यांसाठी.
   • चला एक पूर्णांक निवडू अजसे की 2 ≤ a ≤ n - 1.
   • जर a (mod n) = a (mod n) असेल तर संख्या बहुधा अभाज्य असते. जर समानता समाधानी नसेल, तर संख्या n संमिश्र आहे.
   • एकाधिक मूल्यांसाठी दिलेली समानता तपासा अचाचणी केली जाणारी संख्या खरोखर अभाज्य असण्याची शक्यता वाढवण्यासाठी.
3. 3 मिलर-रबिन चाचणी. चेतावणी: कधीकधी, जरी क्वचितच, a च्या एकाधिक मूल्यांसाठी, चाचणी संमिश्र संख्यांना अविभाज्य म्हणून ओळखेल.
   • S आणि d असे प्रमाण शोधा ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • पूर्णांक निवडा अ श्रेणी 2 ≤ a ≤ n - 1 मध्ये.
   • जर a = +1 (mod n) किंवा -1 (mod n), तर n बहुधा प्राइम असेल. या प्रकरणात, चाचणी परिणामावर जा. जर समानता टिकली नाही तर पुढील चरणावर जा.
   • तुमचे उत्तर चौरस करा (${ displaystyle a ^ {2d}}$). जर तुम्हाला -1 (mod n) मिळाले तर कदाचित n ही एक अभाज्य संख्या आहे. या प्रकरणात, चाचणी परिणामावर जा. समानता अयशस्वी झाल्यास, पुन्हा करा (${ displaystyle a ^ {4d}}$ आणि असेच) पर्यंत ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • वगळता इतर पायरीवर असल्यास ${ प्रदर्शन शैली दुपारी 1}$ (mod n), तुम्हाला +1 (mod n) मिळाले, म्हणून n एक संयुक्त संख्या आहे. तर ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), नंतर n प्रधान नाही.
   • चाचणी परिणाम: जर n चाचणी उत्तीर्ण झाली, तर इतर मूल्यांसाठी ती पुन्हा करा अआत्मविश्वास वाढवण्यासाठी.

3 पैकी 2 भाग: साधेपणा चाचण्या कशा कार्य करतात

1. 1 विभाजकांची गणना. व्याख्येनुसार, संख्या n जर ते 2 आणि इतर पूर्णांक 1 आणि स्वतः वगळता विभाजित नसेल तरच सोपे आहे. वरील सूत्र आपल्याला अनावश्यक पायऱ्या काढण्याची आणि वेळ वाचवण्याची परवानगी देते: उदाहरणार्थ, एखादी संख्या 3 ने विभाजित आहे की नाही हे तपासल्यानंतर, 9 द्वारे विभाज्य आहे की नाही हे तपासण्याची गरज नाही.
   • मजला (x) फंक्शन x जवळच्या पूर्णांकाला x पेक्षा कमी किंवा त्याच्या समान पूर्ण करते.
2. 2 मॉड्यूलर अंकगणित बद्दल जाणून घ्या. ऑपरेशन "x mod y" (mod हे लॅटिन शब्द "modulo" चे संक्षेप आहे, म्हणजेच "module") म्हणजे "x ला y ने भागा आणि उर्वरित शोधा." दुसऱ्या शब्दांत, मॉड्यूलर अंकगणित मध्ये, एका विशिष्ट मूल्यापर्यंत पोहोचल्यावर, ज्याला म्हणतात मॉड्यूल, संख्या पुन्हा शून्यावर "वळते". उदाहरणार्थ, घड्याळ मॉड्यूल 12 सह मोजले जाते: ते 10, 11 आणि 12 तास दर्शवते आणि नंतर 1 वर परत येते.
   • अनेक कॅल्क्युलेटरमध्ये मॉड की असते. या विभागाचा शेवट आपल्याला दर्शवितो की मोठ्या संख्येने या फंक्शनची व्यक्तिचलित गणना कशी करावी.
3. 3 फर्मॅटच्या छोट्या प्रमेयातील तोटे जाणून घ्या. सर्व संख्या ज्यासाठी परीक्षेच्या अटी पूर्ण केल्या नाहीत त्या संमिश्र आहेत, परंतु उर्वरित संख्या फक्त आहेत कदाचित साधे आहेत. आपण चुकीचे परिणाम टाळू इच्छित असल्यास, शोधा n "कार्माइकल क्रमांक" (या चाचणीचे समाधान करणारी संमिश्र संख्या) आणि "फर्मेट स्यूडोप्राइम संख्या" च्या यादीमध्ये (हे संख्या केवळ काही मूल्यांसाठी चाचणी अटी पूर्ण करतात अ).
4. 4 सोयीस्कर असल्यास, मिलर-रबिन चाचणी वापरा. जरी ही पद्धत मॅन्युअल गणनासाठी ऐवजी अवजड असली तरी ती बर्याचदा संगणक प्रोग्राममध्ये वापरली जाते. हे स्वीकार्य वेग आणि फर्मॅटच्या पद्धतीपेक्षा कमी त्रुटी प्रदान करते. जर ¼ पेक्षा जास्त मूल्यांसाठी गणना केली गेली तर संमिश्र संख्या मुख्य संख्या म्हणून घेतली जाणार नाही अ... आपण यादृच्छिकपणे भिन्न मूल्ये निवडल्यास अ आणि त्या सर्वांसाठी ही चाचणी सकारात्मक परिणाम देईल, हे आपण बऱ्याच प्रमाणात आत्मविश्वासाने गृहीत धरू शकतो n एक मुख्य संख्या आहे.
5. 5 मोठ्या संख्येसाठी, मॉड्यूलर अंकगणित वापरा. जर तुमच्याकडे मॉड कॅल्क्युलेटर सुलभ नसेल किंवा कॅल्क्युलेटर इतक्या मोठ्या संख्येने हाताळण्यासाठी डिझाइन केलेले नसेल तर गणना सुलभ करण्यासाठी पॉवर प्रॉपर्टीज आणि मॉड्यूलर अंकगणित वापरा. खाली एक उदाहरण आहे ${ प्रदर्शन शैली 3 ^ {50}}$ मोड 50:
   • अधिक सोयीस्कर स्वरूपात अभिव्यक्ती पुन्हा लिहा: ${ प्रदर्शन शैली (3 ^ {25} * 3 ^ {25})}$ mod 50. मॅन्युअल गणनासाठी आणखी सरलीकरणाची आवश्यकता असू शकते.
   • ${ प्रदर्शन शैली (3 ^ {25} * 3 ^ {25})}$ मॉड 50 = ${ प्रदर्शन शैली (3 ^ {25}}$ मॉड 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50. येथे आम्ही मॉड्यूलर गुणाकाराची मालमत्ता विचारात घेतली.
   • ${ प्रदर्शन शैली 3 ^ {25}}$ मॉड 50 = 43.
   • ${ प्रदर्शन शैली (3 ^ {25}}$ मॉड 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50 = ${ प्रदर्शन शैली (43 * 43)}$ मॉड 50.
   • ${ displaystyle = 1849}$ मॉड 50.
   • ${ displaystyle = 49}$.

भाग 3 मधील 3: चीनी उर्वरित प्रमेय वापरणे

1. 1 दोन संख्या निवडा. संख्यांपैकी एक संमिश्र असणे आवश्यक आहे, आणि दुसरा आपण साधेपणासाठी चाचणी करू इच्छित असावा.
   • क्रमांक 1 = 35
   • क्रमांक 2 = 97
2. 2 दोन मूल्ये निवडा जी शून्यापेक्षा मोठी आहेत आणि अनुक्रमे संख्या 1 आणि संख्या 2 पेक्षा कमी आहेत. ही मूल्ये एकसारखी नसावीत.
   • मूल्य 1 = 1
   • मूल्य 2 = 2
3. 3 क्रमांक 1 आणि क्रमांक 2 साठी एमएमआय (गणितीय गुणाकार व्यस्त) ची गणना करा.
   • MMI ची गणना करा
     • MMI1 = Number2 ^ -1 Mod Number1
     • MMI2 = Number1 ^ -1 Mod Number2
   • केवळ मूळ संख्यांसाठी (हे संमिश्र संख्यांसाठी एक संख्या देईल, परंतु तो त्याचा MMI नसेल):
     • MMI1 = (Number2 ^ (Number1-2))% Number1
     • MMI2 = (Number1 ^ (Number2-2))% Number2
   • उदाहरणार्थ:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 लॉग 2 मॉड्यूल पर्यंत प्रत्येक MMI साठी एक टेबल तयार करा:
   • MMI1 साठी
     • F (1) = संख्या 2% संख्या 1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Number1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Number1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Number1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Number1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Number1 = 1 * 1% 35 = 1
   • जोडलेल्या संख्या 1 - 2 ची गणना करा
     • 35 -2 = 33 (10001) बेस 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 mod 35
     • MMI1 = 27
   • MMI2 साठी
     • F (1) = संख्या 1% संख्या 2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Number2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Number2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Number2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Number2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Number2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Number2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Number2 = 35 * 35 mod 97 = 61
   • जोडलेल्या क्रमांक 2 - 2 ची गणना करा
     • 97 - 2 = 95 = (1011111) बेस 2
     • MMI2 = (((((F (64) * F (16)% 97) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F (1)% 97)
     • MMI2 = (((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
     • MMI2 = 61
5. 5 गणना करा (मूल्य 1 * संख्या 2 * MMI1 + मूल्य 2 * संख्या 1 * MMI2)% (संख्या 1 * संख्या 2)
   • उत्तर = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • उत्तर = (2619 + 4270)% 3395
   • उत्तर = 99
6. 6 नंबर 1 अभाज्य नाही हे तपासा
   • गणना करा (उत्तर - मूल्य 1)% क्रमांक 1
   • 99 – 1 % 35 = 28
   • 28 ही 0 पेक्षा मोठी असल्याने, 35 ही मूळ संख्या नाही.
7. 7 संख्या 2 अभाज्य आहे हे तपासा.
   • गणना करा (उत्तर - मूल्य 2)% क्रमांक 2
   • 99 – 2 % 97 = 0
   • 0 0 असल्याने, बहुधा 97 ही एक अभाज्य संख्या आहे.
8. 8 चरण 1 ते 7 किमान दोन वेळा पुन्हा करा.
   • तुम्हाला पायरी 7 मध्ये 0 मिळाल्यास:
     • जर नंबर 1 अभाज्य नसेल तर वेगळा नंबर 1 वापरा.
     • नंबर 1 अभाज्य असल्यास दुसरा नंबर 1 वापरा. या प्रकरणात, आपल्याला चरण 6 आणि 7 मध्ये 0 मिळाले पाहिजे.
     • भिन्न अर्थ 1 आणि अर्थ 2 वापरा.
   • जर पायरी 7 मध्ये तुम्हाला सातत्याने 0 मिळाले, तर क्रमांक 2 हा बहुमोल असण्याची शक्यता आहे.
   • जर क्रमांक 1 अभाज्य नसेल आणि क्रमांक 2 हा संख्या 1 चा विभाजक असेल तर चरण 1 ते 7 मध्ये त्रुटी येऊ शकते. वर्णित पद्धत सर्व प्रकरणांमध्ये कार्य करते जेव्हा दोन्ही संख्या अभाज्य असतात.
   • आपल्याला 1 ते 7 चरणांची पुनरावृत्ती करण्याची आवश्यकता आहे कारण काही प्रकरणांमध्ये, जरी संख्या 1 आणि क्रमांक 2 अभाज्य नसले तरीही, चरण 7 मध्ये आपल्याला 0 (एक किंवा दोन्ही संख्यांसाठी) मिळेल. हे क्वचितच घडते.दुसरा क्रमांक 1 (संमिश्र) निवडा आणि जर क्रमांक 2 अभाज्य नसेल, तर क्रमांक 2 पायरी 7 मध्ये शून्याच्या बरोबरीने नसेल (वगळता जेव्हा नंबर 1 हा नंबर 2 चा विभाजक असेल - येथे प्राइम नेहमी पायरी 7 मध्ये शून्य समान असेल).

टिपा

• 168 ते 1000 मधील मुख्य संख्या: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79 , 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211 , 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 359, 359 , 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509 , 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673 , 7, 3३, 1 1,, 1 1 9 7 7 19 19 72 72 , 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.
• जरी मोठ्या संख्येने काम करताना क्रूर शक्ती चाचणी ही एक कंटाळवाणी चाचणी असली तरी ती लहान संख्येसाठी बरीच कार्यक्षम आहे. जरी मोठ्या संख्येच्या बाबतीत, लहान भागाकारांची चाचणी करून प्रारंभ करा आणि नंतर संख्यांची साधेपणा तपासण्यासाठी अधिक अत्याधुनिक पद्धतींवर जा (जर लहान विभाजक सापडले नाहीत).

आपल्याला काय आवश्यक आहे

• कागद, पेन किंवा संगणक