पायरी २: युक्लिडचा भागाकार प्रमेय आणि मसावि शोधण्याची पद्धत
संख्यांच्या विभाज्यतेचा मूलभूत पाया समजून घेण्यासाठी युक्लिडचा भागाकार प्रमेय अत्यंत महत्त्वाचा आहे.
? दृश्य संकल्पना आकृती: युक्लिडचा भागाकार प्रमेय ( लांबीचे तुकडे व बाकी )

वरील आकृतीमध्ये $a$ ही एकूण लांबी दर्शवली आहे. जेव्हा तिला $b$ लांबीच्या समान तुकड्यांमध्ये कापले जाते, तेव्हा असे $q$ तुकडे मिळतात आणि शेवटी $r$ इतकी लांबी उरते, जी $b$ पेक्षा लहान असते!
१. युक्लिडचा भागाकार प्रमेय (Euclid's Division Lemma)
दिलेल्या दोन धन पूर्णांक $a$ आणि $b$ साठी, असे अद्वितीय पूर्णांक $q$ आणि $r$ अस्तित्वात असतात की:
- $a$ = भाज्य (Dividend)
- $b$ = भाजक (Divisor)
- $q$ = भागाकार (Quotient)
- $r$ = बाकी (Remainder)
स्मरण ठेवा: बाकी $r$ ही शून्य असू शकते किंवा धन असू शकते, पण ती भाजक $b$ पेक्षा नेहमी लहान असावी लागते ($0 \le r < b$).
२. युक्लिडचा भागाकार अल्गोरिदम (मसावि काढणे)
दोन संख्यांचा महत्तम सामाईक विभाजक (HCF) काढण्यासाठी आपण ही पायरी वारंवार वापरतो जोपर्यंत बाकी $0$ येत नाही.
युक्लिड मसावि शोधण्याची प्रक्रिया
│
c = d · q1 + r1 (0 <= r1 < d)
│
┌──────────────┴──────────────┐
▼ ▼
जर r1 = 0 जर r1 != 0
│ │
'd' हाच मसावि आहे! d = r1 · q2 + r2
(बाकी ० येईपर्यंत क्रिया सुरू ठेवा)
सोडवलेले उदाहरण: ४५५ आणि ४२ चा मसावि काढा
- $455 = (42 \times 10) + 35$ (बाकी $35 \neq 0$)
- $42 = (35 \times 1) + 7$ (बाकी $7 \neq 0$)
- $35 = (7 \times 5) + 0$ (बाकी $0$ आली!)
येथे शेवटचा भाजक ७ आहे. म्हणून:
३. भारतीय गणितीय वारसा: ब्रह्मगुप्तांची 'कुट्टक' पद्धत
७ व्या शतकात थोर भारतीय गणिती ब्रह्मगुप्त यांनी 'ब्राह्मस्फुटसिद्धान्त' या ग्रंथात रेषीय अनिर्धार्य समीकरणे ($ax + by = c$) सोडवण्यासाठी 'कुट्टक' (Kuttaka - Pulverizer) पद्धत विकसित केली. कुट्टक म्हणजे 'तुकडे-तुकडे करून बारीक करणे'. ही पद्धत युक्लिडच्या भागाकार अल्गोरिदमशी तंतोतंत जुळते आणि आधुनिक संगणक शास्त्रातील Cryptography चा पाया मानली जाते!

