विषय

• कदम
• 3 का भाग 1 : सादगी की परीक्षा
• 3 का भाग 2: सरलता परीक्षण कैसे कार्य करते हैं
• भाग ३ का ३: चीनी शेष प्रमेय का उपयोग करना
• टिप्स
• आपको किस चीज़ की जरूरत है

अभाज्य संख्याएँ वे संख्याएँ होती हैं जो केवल स्वयं और 1 से विभाज्य होती हैं। अन्य सभी संख्याएँ भाज्य संख्याएँ कहलाती हैं। यह निर्धारित करने के कई तरीके हैं कि कोई संख्या अभाज्य है, और उन सभी के अपने फायदे और नुकसान हैं। एक ओर, कुछ विधियां बहुत सटीक हैं, लेकिन यदि आप बड़ी संख्या के साथ काम कर रहे हैं तो वे काफी जटिल हैं। दूसरी ओर, बहुत तेज़ तरीके हैं, लेकिन वे गलत परिणाम दे सकते हैं। उपयुक्त विधि का चुनाव इस बात पर निर्भर करता है कि आप कितनी बड़ी संख्याओं के साथ काम कर रहे हैं।

कदम

3 का भाग 1 : सादगी की परीक्षा

ध्यान दें: सभी सूत्रों में एन जाँच की जाने वाली संख्या को दर्शाता है।

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

3 का भाग 2: सरलता परीक्षण कैसे कार्य करते हैं

1. 1 भाजक की गणना। परिभाषा के अनुसार, संख्या एन केवल तभी सरल है जब यह 1 और स्वयं को छोड़कर 2 और अन्य पूर्णांकों से विभाज्य न हो। उपरोक्त सूत्र आपको अनावश्यक चरणों को हटाने और समय बचाने की अनुमति देता है: उदाहरण के लिए, यह जाँचने के बाद कि क्या कोई संख्या 3 से विभाज्य है, यह जाँचने की कोई आवश्यकता नहीं है कि क्या यह 9 से विभाज्य है।
   • तल (x) फ़ंक्शन x को x से कम या उसके बराबर के निकटतम पूर्णांक तक ले जाता है।
2. 2 मॉड्यूलर अंकगणित के बारे में जानें। ऑपरेशन "x mod y" (मॉड लैटिन शब्द "मॉड्यूलो" का संक्षिप्त नाम है, जो कि "मॉड्यूल" है) का अर्थ है "x को y से विभाजित करें और शेष खोजें।" दूसरे शब्दों में, मॉड्यूलर अंकगणित में, एक निश्चित मूल्य तक पहुंचने पर, जिसे कहा जाता है मापांक, संख्याएँ "बारी" फिर से शून्य हो जाती हैं। उदाहरण के लिए, घड़ी मॉड्यूल 12 के साथ उलटी गिनती करती है: यह 10, 11 और 12 घंटे दिखाती है, और फिर 1 पर लौट आती है।
   • कई कैलकुलेटर में एक आधुनिक कुंजी होती है। इस खंड का अंत आपको दिखाता है कि बड़ी संख्या के लिए इस फ़ंक्शन की मैन्युअल रूप से गणना कैसे करें।
3. 3 Fermat's Little Theorem के नुकसान के बारे में जानें। वे सभी संख्याएँ जिनके लिए परीक्षण की शर्तें पूरी नहीं हुई हैं, संयुक्त हैं, लेकिन शेष संख्याएँ केवल हैं संभवत सरल हैं। यदि आप गलत परिणामों से बचना चाहते हैं, तो खोजें एन "कारमाइकल नंबर" (इस परीक्षण को पूरा करने वाली मिश्रित संख्याएं) और "फर्मैट स्यूडोप्राइम नंबर" की सूची में (ये नंबर केवल कुछ मानों के लिए परीक्षण शर्तों को पूरा करते हैं ए).
4. 4 यदि सुविधाजनक हो, तो मिलर-राबिन परीक्षण का उपयोग करें। यद्यपि यह विधि मैन्युअल गणना के लिए काफी बोझिल है, लेकिन इसका उपयोग अक्सर कंप्यूटर प्रोग्राम में किया जाता है। यह फर्मेट की विधि की तुलना में स्वीकार्य गति और कम त्रुटियां प्रदान करता है। यदि गणना से अधिक मानों के लिए की जाती है तो एक समग्र संख्या को एक प्रमुख संख्या के रूप में नहीं लिया जाएगा ए... यदि आप बेतरतीब ढंग से अलग-अलग मान चुनते हैं ए और उन सभी के लिए परीक्षण एक सकारात्मक परिणाम देगा, हम काफी उच्च स्तर के विश्वास के साथ यह मान सकते हैं कि एन एक अभाज्य संख्या है।
5. 5 बड़ी संख्या के लिए, मॉड्यूलर अंकगणित का उपयोग करें। यदि आपके पास मॉड कैलकुलेटर नहीं है, या कैलकुलेटर इतनी बड़ी संख्या को संभालने के लिए डिज़ाइन नहीं किया गया है, तो गणना को आसान बनाने के लिए पावर प्रॉपर्टीज और मॉड्यूलर अंकगणित का उपयोग करें। नीचे एक उदाहरण है ${ डिस्प्लेस्टाइल 3 ^ {50}}$ मॉड 50:
   • अधिक सुविधाजनक रूप में अभिव्यक्ति को फिर से लिखें: ${ डिस्प्लेस्टाइल (3 ^ {25} * 3 ^ {25})}$ मॉड 50. मैनुअल गणना के लिए और सरलीकरण की आवश्यकता हो सकती है।
   • ${ डिस्प्लेस्टाइल (3 ^ {25} * 3 ^ {25})}$ मॉड 50 = ${ डिस्प्लेस्टाइल (3 ^ {25}}$ मॉड 50 ${ डिस्प्लेस्टाइल * 3 ^ {25}}$ मॉड ५०) मॉड ५०। यहाँ हमने मॉड्यूलर गुणन की संपत्ति को ध्यान में रखा।
   • ${ डिस्प्लेस्टाइल 3 ^ {25}}$ मॉड 50 = 43.
   • ${ डिस्प्लेस्टाइल (3 ^ {25}}$ मॉड 50 ${ डिस्प्लेस्टाइल * 3 ^ {25}}$ मॉड ५०) मॉड ५० = ${ डिस्प्लेस्टाइल (43 * 43)}$ मॉड 50.
   • ${ डिस्प्लेस्टाइल = १८४९}$ मॉड 50.
   • ${ डिस्प्लेस्टाइल = 49}$.

भाग ३ का ३: चीनी शेष प्रमेय का उपयोग करना

1. 1 दो नंबर उठाओ। संख्याओं में से एक समग्र होनी चाहिए, और दूसरी बिल्कुल वही होनी चाहिए जिसे आप सरलता के लिए परीक्षण करना चाहते हैं।
   • नंबर 1 = 35
   • संख्या २ = ९७
2. 2 दो मानों का चयन करें जो शून्य से अधिक हैं और, क्रमशः, संख्या 1 और संख्या 2 से कम हैं। ये मान समान नहीं होने चाहिए।
   • मान 1 = 1
   • मान 2 = 2
3. 3 संख्या 1 और संख्या 2 के लिए एमएमआई (गणितीय गुणन प्रतिलोम) की गणना करें।
   • एमएमआई की गणना करें
     • MMI1 = नंबर 2 ^ -1 मॉड नंबर 1
     • MMI2 = नंबर 1 ^ -1 मॉड नंबर 2
   • केवल अभाज्य संख्याओं के लिए (यह मिश्रित संख्याओं के लिए एक संख्या देगा, लेकिन यह उसका MMI नहीं होगा):
     • एमएमआई1 = (नंबर2 ^ (नंबर1-2))% नंबर1
     • MMI2 = (नंबर1 ^ (नंबर2-2))% संख्या2
   • उदाहरण के लिए:
     • एमएमआई1 = (97 ^ 33)% 35
     • एमएमआई२ = ​​(३५ ^ ९५)% ९७
4. 4 प्रत्येक एमएमआई के लिए लॉग 2 मॉड्यूल के लिए एक टेबल बनाएं:
   • MMI1 . के लिए
     • एफ (1) = संख्या 2% संख्या 1 = 97% 35 = 27
     • एफ (2) = एफ (1) * एफ (1)% संख्या 1 = 27 * 27% 35 = 29
     • एफ (4) = एफ (2) * एफ (2)% संख्या 1 = 29 * 29% 35 = 1
     • एफ (8) = एफ (4) * एफ (4)% संख्या 1 = 1 * 1% 35 = 1
     • एफ (16) = एफ (8) * एफ (8)% संख्या 1 = 1 * 1% 35 = 1
     • एफ (32) = एफ (16) * एफ (16)% संख्या 1 = 1 * 1% 35 = 1
   • युग्मित संख्याओं की गणना करें 1 - 2
     • 35 -2 = 33 (10001) आधार 2
     • एमएमआई 1 = एफ (33) = एफ (32) * एफ (1) मॉड 35
     • एमएमआई 1 = एफ (33) = 1 * 27 मॉड 35
     • एमएमआई1 = 27
   • MMI2 . के लिए
     • एफ (१) = संख्या१% संख्या २ = ३५% ९७ = ३५
     • एफ (2) = एफ (1) * एफ (1)% संख्या 2 = 35 * 35 मॉड 97 = 61
     • एफ (4) = एफ (2) * एफ (2)% संख्या 2 = 61 * 61 मॉड 97 = 35
     • एफ (8) = एफ (4) * एफ (4)% संख्या 2 = 35 * 35 मॉड 97 = 61
     • एफ (16) = एफ (8) * एफ (8)% संख्या 2 = 61 * 61 मॉड 97 = 35
     • एफ (32) = एफ (16) * एफ (16)% संख्या 2 = 35 * 35 मॉड 97 = 61
     • एफ (64) = एफ (32) * एफ (32)% संख्या 2 = 61 * 61 मॉड 97 = 35
     • एफ (128) = एफ (64) * एफ (64)% संख्या 2 = 35 * 35 मॉड 97 = 61
   • जोड़ी संख्या 2 - 2 . की गणना करें
     • ९७ - २ = ९५ = (१०१११११) आधार २
     • एमएमआई2 = (((((एफ (64) * एफ (16)% 97) * एफ (8)% 97) * एफ (4)% 97) * एफ (2)% 97) * एफ (१)% ९७)
     • MMI2 = (((((35 * 35)% 97) * 61%)% 97) * 35% 97) * 61% 97) * 35% 97)
     • एमएमआई २ = ६१
5. 5 गणना करें (मान 1 * संख्या 2 * एमएमआई 1 + मूल्य 2 * संख्या 1 * एमएमआई 2)% (संख्या 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 मिलता है:
     • यदि Number1 अभाज्य नहीं है तो भिन्न संख्या1 का प्रयोग करें।
     • अगर नंबर 1 प्राइम है तो दूसरे नंबर 1 का इस्तेमाल करें। इस मामले में, आपको चरण 6 और 7 में 0 प्राप्त करना चाहिए।
     • भिन्न अर्थ1 और अर्थ2 का प्रयोग करें।
   • यदि चरण 7 में आप लगातार 0 प्राप्त करते हैं, तो संख्या 2 के अभाज्य होने की बहुत संभावना है।
   • चरण 1 से 7 में त्रुटि हो सकती है यदि संख्या 1 अभाज्य नहीं है और संख्या 2 संख्या 1 का भाजक है। वर्णित विधि सभी मामलों में काम करती है जब दोनों संख्याएं अभाज्य होती हैं।
   • आपको चरण 1 से 7 तक दोहराने की आवश्यकता है क्योंकि कुछ मामलों में, भले ही नंबर 1 और नंबर 2 अभाज्य न हों, चरण 7 में आपको 0 (एक या दोनों संख्याओं के लिए) मिलेगा। ऐसा कम ही होता है।एक और संख्या 1 (समग्र) चुनें, और यदि संख्या 2 अभाज्य नहीं है, तो चरण 7 में संख्या 2 शून्य के बराबर नहीं होगी (उस स्थिति को छोड़कर जब संख्या 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, 353, 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 , 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853 , 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997।
• हालांकि बड़ी संख्या के साथ काम करते समय पाशविक बल परीक्षण एक कठिन परीक्षा है, यह छोटी संख्याओं के लिए काफी कुशल है। यहां तक ​​​​कि बड़ी संख्या के मामले में, छोटे भाजक का परीक्षण करके शुरू करें, और फिर संख्याओं की सादगी की जांच के लिए अधिक परिष्कृत तरीकों पर आगे बढ़ें (यदि छोटे भाजक नहीं पाए जाते हैं)।

आपको किस चीज़ की जरूरत है

• कागज, कलम या कंप्यूटर