सबसे बड़े सामान्य भाजक की गणना कैसे करें?

सबसे बड़े सामान्य भाजक के बारे में अधिक जानकारी (कभी-कभी इसे सबसे बड़ा सामान्य कारक भी कहा जाता है) : दो धनात्मक पूर्णांक संख्याओं \(n_1\) और \(n_2\) के बीच सबसे बड़ा सामान्य भाजक (GCD) सबसे बड़ा पूर्णांक है जो \(n_1\) और \(n_2\) दोनों को विभाजित करता है। यह आमतौर पर निरीक्षण द्वारा खोजना आसान होता है (यह है, बहुत सी संख्याओं को व्यवस्थित तरीके से कोशिश करना, जब तक कि हम इसे न खोज लें), लेकिन यह केवल छोटी संख्याओं के लिए ही सही है। निरीक्षण द्वारा बड़ी संख्या में जीसीडी की गणना करना कठिन या सादा कठिन हो सकता है।

सौभाग्य से, दो संख्याओं के लिए जीसीडी की गणना करने का एक व्यवस्थित, आसान (खांसी, खांसी) तरीका है। विधि इस प्रकार है

• गणना करें प्रधान अपघटन \(n_1\) और \(n_2\) का। प्रतीकात्मक रूप से, हमारे पास कुछ ऐसा होगा: \[n_1 = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_n^{\alpha_n}\] \[n_2 = q_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_m^{\alpha_m}\]
• संबंधित अभाज्य अपघटन में उभयनिष्ठ अभाज्य संख्याओं की सूची ज्ञात कीजिए। यदि कोई सामान्य अभाज्य नहीं हैं, तो रोकें, आपने पाया है कि GCD = 1। अन्यथा, \(\{r_1, ..., r_k \}\) को \(k\) सामान्य अभाज्य संख्याओं की सूची बनने दें और \(l=1,2,..,k\) के लिए \(\alpha_{i_l}, \beta_{i_l}\) को संगत सामान्य के लिए \(n_1\) और \(n_2\) के अभाज्य अपघटन में पाए जाने वाले संगत घातांक दें। अपराध
  
  
• GCD की गणना इस प्रकार की जाती है: \[GCD = r_1^{\min\{\alpha_{i_1}, \beta_{i_1}\}} \cdot r_2^{ \min\{\alpha_{i_2}, \beta_{i_2}\}} \cdots r_k^{\min\{\alpha_{i_k}, \beta_{i_k}\}} \]

उपरोक्त विधि बहुत जटिल लगती है ?? ज़रुरी नहीं। आइए एक उदाहरण देखें: आइए \(n_1 = 165\) और \(n_2 = 1575\) के लिए GCD की गणना करें। आइए हम इनमें से प्रत्येक संख्या का अभाज्य अपघटन ज्ञात करें (आप हमारे अभाज्य अपघटन कैलकुलेटर का उपयोग कर सकते हैं)

\[165 = 3 \cdot 5 \cdot 11\] \[1575 = 3^2 \cdot 5^2 \cdot 7\]

ऊपर से: इन दोनों संख्याओं में कौन से अभाज्य संख्याएँ समान हैं? जैसा कि हम देख सकते हैं, उभयनिष्ठ अभाज्य 3 और 5 हैं। प्रत्येक संख्या में इन उभयनिष्ठ अभाज्यों के घातांक को देखते हुए, हम दोनों के बीच न्यूनतम देखते हैं। इस स्थिति में, 3 के लिए न्यूनतम घातांक 1 है, और 5 के लिए न्यूनतम घातांक भी 1 है। इसलिए

\[GCD = 3^1 \cdot 5^1 = 3 \cdot 5 = 15 \]

जीडीसी कैलकुलेटर के अलावा, आप हमारे चयन में से चुन सकते हैं बीजगणित कैलकुलेटर और सॉल्वर .