📌 1. परिभाषा (Definition)
यूक्लिड विभाजन एल्गोरिद्म एक गणितीय विधि है जिसका उपयोग दो संख्याओं का महत्तम समापवर्तक (HCF / GCD) निकालने के लिए किया जाता है।
इसे महान यूनानी गणितज्ञ Euclid ने प्रस्तुत किया था।
📌 2. मूल सिद्धांत (Euclid Division Lemma)
यह एल्गोरिद्म एक महत्वपूर्ण नियम पर आधारित है:
a=bq+ra = bq + ra=bq+r
जहाँ –
- a = भाज्य (Dividend)
- b = भाजक (Divisor)
- q = भागफल (Quotient)
- r = शेष (Remainder), जहाँ 0≤r
📌 3. एल्गोरिद्म की प्रक्रिया (Step-by-Step Process)
- बड़ी संख्या को a और छोटी को b मानें
- a=bq+ra = bq + ra=bq+r लागू करें
- यदि r = 0, तो b ही HCF है
- यदि r ≠ 0, तो
- अब a = b और b = r रखें
- प्रक्रिया दोहराएँ
- जब शेष 0 हो जाए, वही अंतिम भाजक = HCF
📌 4. उदाहरण (Example)
मान लीजिए HCF निकालना है: 36 और 24
Step 1:
36 = 24 × 1 + 12
Step 2:
24 = 12 × 2 + 0
👉 शेष 0 आ गया → HCF = 12
📌 5. एल्गोरिद्म का महत्व (Importance)
- बड़ी संख्याओं का HCF आसानी से निकालता है
- गणना को सरल और तेज बनाता है
- कंप्यूटर प्रोग्रामिंग और क्रिप्टोग्राफी में उपयोगी
- यह संख्या सिद्धांत (Number Theory) का आधार है
📌 6. विशेष तथ्य (Important Facts)
✔ यह बार-बार भाग करने की प्रक्रिया है
✔ हर स्टेप में संख्या छोटी होती जाती है
✔ यह हमेशा समाप्त होता है (finite steps)
✔ HCF हमेशा अंतिम non-zero remainder का divisor होता है
📌 7. उपयोग (Applications)
- HCF / GCD निकालना
- भिन्न (Fractions) को सरल बनाना
- RSA Encryption (Cryptography)
- कंप्यूटर एल्गोरिद्म डिजाइन
📌 8. शॉर्ट ट्रिक (Shortcut Understanding)
👉 “बार-बार भाग करो जब तक remainder 0 न हो जाए”
👉 “अंतिम भाजक = HCF”