ဂၞန်ပါ်မဇၞော်အိုတ်

ဂၞန်ပါ်မဇၞော်အိုတ် ဟွံသေင်မ္ဂး ဂၞန်သဇိုင်မပါ်ပြေအိုတ် (အၚ်္ဂလိက်: Greatest Common Divisor (GCD), သီုမကော်စ Highest Common Factor (HCF)) ဟီုမ္ဂးဂှ် ပ္ဍဲကဵု ဘာသာရပ် သင်္ချာ မ္ဂး ဒှ် လၟိဟ် ဂၞန်အလုံ ဓမ္မတာ (Positive integer) မဇၞော်အိုတ် မွဲ မမာန် ပါ်ပြေ (Divides evenly) ဂၞန်အလုံ ၜါ ဟွံသေင်မ္ဂး ဂၠိုင်နူဂှ် နကဵု မဟွံမဲ ကဵု သှ်ေ (Remainder) ရ။

ဥပမာ - သွက် ဂၞန် ၈ ကေုာံ ၁၂ ဂှ်၊ ဂၞန်မမာန် ပါ် ၈ ပြေ တအ်ဂှ် ဒှ် ၁, ၂, ၄, ၈ ရ။ ဂၞန်မမာန် ပါ် ၁၂ ပြေ တအ်ဂှ် ဒှ် ၁, ၂, ၃, ၄, ၆, ၁၂ ရ။ ပ္ဍဲကဵု စရင် ၜါဏအ် ဂၞန်မပါလုပ် တုပ်ရေင်သကအ် (Common divisors) တအ်ဂှ် ဒှ် ၁, ၂, ၄ ရ။ ပ္ဍဲအကြာဂှ် ဂၞန်မဇၞော်အိုတ် ဂှ် ဒှ် ၄ ရ။ ဟိုတ်ဂှ်ရ ဂၞန်ပါ်မဇၞော်အိုတ် သွက် ၈ ကဵု ၁၂ ဂှ် ဒှ် ၄ ရ (GCD(8, 12) = 4)။

ဂၞန်ပါ်မဇၞော်အိုတ် ဝွံ ဒှ် သဇိုင် အဓိက ပ္ဍဲကဵု သဳအိုရဳ ဂၞန် (Number theory) တုဲ စကာ ဗွဲမလှဲလး ပ္ဍဲကဵု ပရေင်ဖ္ဍန် ဂၞန်ကဝက် (Simplifying fractions)၊ ပရေင်ချပ်ဂၞန် အာလ်ဂျဳဗရာ (Algebra)၊ ကေုာံ ကွတ်ဂီုကၠီု ဒဳဂျဳတေဝ် (Cryptography) တအ်ရ။

ဝှာင်:Venn diagram showing LCM and GCF.svg

ဗီုရုပ် ဗေန် (Venn diagram) ထ္ၜးကဵု ပရေင်ဆက်စပ် အကြာ ပရေင်ပါ်ကရေက် ဂၞန်သဇိုင် သွက် ဂၞန် ၄၈ ကေုာံ ၁၈၀။ လဒေါဝ်ဂှ် ဒှ် GCD မတုပ်သၟဟ် ကဵု 2 × 2 × 3 = 12 ရ။

၁။ နိဒါန် ကေုာံ ပွံက်အဓိပ္ပါယ် (Introduction and Definition)

ပ္ဍဲကဵု သင်္ချာ ဂှ် ဂၞန်ပါ်မဇၞော်အိုတ် သွက် ဂၞန်အလုံ ၜါ $a$ ကေုာံ $b$ (ၜါဏအ် သုည ဟွံသေင် မွဲအိုတ်) ဂှ် ညးစၟတ်သမ္တီလဝ် နကဵု သင်္ကေတ $\gcd(a, b)$ ရ။ ဍေဟ်ဝွံ ဒှ် ဂၞန်အလုံ ဓမ္မတာ $d$ မဇၞော်အိုတ် မမာန် ပါ် $a$ ပြေ ($d \mid a$) ကေုာံ မမာန် ပါ် $b$ ပြေ ($d \mid b$) ရ။

ယဝ်ရ $\gcd(a, b) = 1$ မ္ဂး၊ ဂၞန် ၜါဂှ် ညးကော်စ ဂၞန်သဇိုင်ရေင်သကအ် (Coprime ဟွံသေင်မ္ဂး Relatively prime) ရ။ ဥပမာ - ဂၞန် ၉ ကဵု ၂၈ ဂှ် ၜိုန်ရ ဍေဟ်တအ် ဟွံသေင် ဂၞန်သဇိုင် ကီုလေဝ်၊ ဍေဟ်တအ် ဟွံမဲကဵု ဂၞန်ပါ် မတုပ် တၞဟ်ခြာ နူ ၁ တုဲ၊ $\gcd(9, 28) = 1$ ရ။

တင်သမ္တီ အဓိက:

• $\gcd(a, 0) = |a|$ (ဟိုတ်နူ ဇၟာပ်ဂၞန် ပါ် သုည ပြေ)
• $\gcd(a, b) = \gcd(b, a)$ (သဘာဝ ညဳသၟဟ်)
• $\gcd(a, b) = \gcd(|a|, |b|)$

၂။ ဝင် ကေုာံ ပရေင်ဇၞော်မောဝ် (History and Development)

လညာတ် မဆေင်ကဵု ဂၞန်ပါ်မဇၞော်အိုတ် ဝွံ ကတဵုဒှ်လဝ် နူကဵု ခေတ် ဂရိတ် တြေံ (Ancient Greece) တေအ်ရ။ အစာသင်္ချာ မပြာကတ် ယူကလိတ် (Euclid) ဝွံ ပ္ဍဲကဵု ပြကိုဟ် ညး Elements (Book VII) မချူလဝ် ပ္ဍဲ ၜိုတ် ဘဳစဳ ၃၀၀ တေအ်ဂှ်၊ ညးတေအ် ဗၟံက်ထ္ၜး လဝ် "နဲကဲ ယူကလိတ်" (Euclidean Algorithm) မဒှ် နဲကဲ သွက်ဂွံ ဂၠာဲ GCD မာန် နကဵု လၟေင်ကမၠောန် မစှ်ေကဵု သၞောတ်ဝ် ရ။

နဲကဲ ယူကလိတ် ဂှ် ဒှ် အလ်ဂဝ်ရဳသမ် (Algorithm) မတြေံအိုတ် မွဲ မဆက်စကာ ဒၟံင် စဵုကဵု တ္ၚဲဏအ် ရ။ ပါဲနူကဵု ဂရိတ်တအ် တုဲ၊ တၠပညာ သင်္ချာ ဍုင်ကြုက် တြေံ ပ္ဍဲ ပြကိုဟ် Jiu Zhang Suan Shu (The Nine Chapters on the Mathematical Art) ဂှ်လေဝ် စကာလဝ် လညာတ် GCD သွက်ဂွံ ဖ္ဍန် ဂၞန်ကဝက် (Fractions) ရ။ ပ္ဍဲ ခေတ်လဒေါဝ် ဂှ် တၠပညာ အိန္ဒိယ ကေုာံ အာရပ် တအ် ဆက်တုဲ ဇၞော်မောဝ် လဝ် သဳအိုရဳ ဏအ် ဗွဲမလှဲလး ရ။

၃။ သင်္ကေတ ကေုာံ ဝေါဟာရဂမၠိုင် (Notation and Terminology)

ပ္ဍဲကဵု လိက်ပတ် သင်္ချာ အလုံဂၠးတိ၊ ဂၞန်ပါ်မဇၞော်အိုတ် သွက် ဂၞန် $a$ ကဵု $b$ ဂှ် ချူဗၟံက်ထ္ၜး နကဵု ဗီုပြင် နာနာ မာန်ရ-

• $\gcd(a, b)$ - မဒှ် သင်္ကေတ မစကာ ဂၠိုင်အိုတ် ပ္ဍဲ ဂၠးတိ။
• $(a, b)$ - ပ္ဍဲကဵု လိက်ပတ် သဳအိုရဳဂၞန် (Number theory) ကဆံင်သၠုင် မ္ဂး၊ ညးတအ် ချူ ဖ္ဍန်ထောအ် နကဵု ခ္ဍောင်ကၟာတ် သၟးရ။
• $\text{hcf}(a, b)$ - မကၠုင်နူ ဝေါဟာရ Highest Common Factor မစကာ ဂၠိုင် ပ္ဍဲ သၞောတ် ပညာ ဗြိတိန်။

ယဝ်ရ နွံကဵု ဂၞန် ဂၠိုင်နူ ၜါ မ္ဂး၊ ဥပမာ $a, b, c$ မ္ဂး ညးချူ $\gcd(a, b, c)$ တုဲ ဍေဟ် တုပ်သၟဟ် ကဵု $\gcd(a, \gcd(b, c))$ ရ။

၄။ နဲကဲဂၠာဲ နကဵု ပရေင်ပါ်ကရေက် ဂၞန်သဇိုင် (Calculation Method: Prime Factorization)

နဲကဲ သဇိုင်အိုတ် သွက်ဂွံ ဂၠာဲ GCD ဂှ် ဒှ် ပရေင်ပါ်ကရေက် ဂၞန်သဇိုင် (Prime Factorization) မာန် အတိုင် သဳအိုရဳ သဇိုင် ပညာဂၞန် ရ။

လၟေင်ကမၠောန်: ၁။ ပါ်ကရေက် ဂၞန် ဇၟာပ်မ နကဵု ဂၞန်သဇိုင် ဍေဟ်တအ်။ ၂။ ရုဲကေတ် ဂၞန်သဇိုင် မတုပ် (Common prime factors) အကြာ ဂၞန် သီုၜါ။ ၃။ သွက် ဂၞန်သဇိုင် မတုပ် ဇၟာပ်မ ဂှ် ရုဲကေတ် ဒြဟတ်စောမ် (Exponent) မဍောတ်အိုတ်။ ၄။ ပတၟောအ် ကေတ် ဂၞန် မရုဲကေတ် လဝ် တအ် သီုဖအိုတ် ရ။

ဥပမာ: ဂၠာဲ $\gcd(48, 180)$

• $48 = 2^4 \times 3^1$
• $180 = 2^2 \times 3^2 \times 5^1$

ဂၞန်သဇိုင် မတုပ် ဂှ် ဒှ် $2$ ကဵု $3$ ရ။ ($5$ ဟွံပါ)။ သွက် $2$: ဒြဟတ်စောမ် အကြာ $4$ ကဵု $2$ ဂှ် $2$ ဍောတ်အိုတ်ရ ($2^2$)။ သွက် $3$: ဒြဟတ်စောမ် အကြာ $1$ ကဵု $2$ ဂှ် $1$ ဍောတ်အိုတ်ရ ($3^1$)။ ဟိုတ်ဂှ်ရ $\gcd(48, 180) = 2^2 \times 3^1 = 4 \times 3 = 12$ ရ။

၅။ နဲကဲ ယူကလိတ် (The Euclidean Algorithm)

နဲကဲ ပါ်ကရေက် ဂၞန်သဇိုင် ဂှ် ခိုဟ် သွက် ဂၞန် ဍောတ်ဍောတ် တအ် သၟးရ။ ယဝ်ရ ဂၞန် ဇၞော်မ္ဂး ကေတ် အခိင် ဗွဲမလအ်လ ရ။ ဟိုတ်ဂှ်ရ နဲကဲ ယူကလိတ် (Euclidean Algorithm) ဂှ် ဒှ် နဲကဲ မပြဟ်အိုတ် ကေုာံ ဆက်စကာ ဒၟံင် ပ္ဍဲ ကောန်ပျူတာ ရ။

နဲကဲဏအ် ဒုင်သဇိုင် လတူ လညာတ် မဟီုတွံ ဒဒှ်ရ $\gcd(a, b) = \gcd(b, r)$ ဒၞာဲ $r$ ဂှ် ဒှ် လၟိဟ် သှ်ေ (Remainder) ကာလ $a$ ပါ် ကဵု $b$ ($a = bq + r$) ရ။

ဝှာင်:Euclidean algorithm 252 105 animation short.gif

ဗီုရုပ် ချဳဓရာင် (Animation) ထ္ၜးကဵု နဲကဲ ယူကလိတ် သွက်ဂွံ ဂၠာဲ GCD(252, 105) = 21 ရ။ ဍေဟ် ပါ်ကရေက် ဧရိယာ နကဵု စတုရန်း မာန်ရ။

ဥပမာ: ဂၠာဲ $\gcd(252, 105)$

လၟေင်ကမၠောန် နဲကဲ ယူကလိတ် သွက် 252 ကဵု 105

ကဆံင်	ပရေင်ပါ် ($a = b \times q + r$)	ဂၞန် $a$	ဂၞန် $b$	သှ်ေ $r$
၁	$252 = 105 \times 2 + 42$	252	105	42
၂	$105 = 42 \times 2 + 21$	105	42	21
၃	$42 = 21 \times 2 + 0$	42	21	0

ကာလ လၟိဟ်သှ်ေ $r$ ဒှ် သုည မ္ဂး၊ ဂၞန် $b$ မသှ်ေဒၟံင် လက္ကရဴအိုတ် (ဒၞာဲဏအ် ဒှ် 21) ဂှ် ဒှ် GCD ရ။ ဟိုတ်ဂှ်ရ $\gcd(252, 105) = 21$ ရ။

၆။ ပရေင်ဆက်စပ် ကု ဂၞန်ပတၟောအ်မဍောတ်အိုတ် (Relationship with Least Common Multiple - LCM)

ဂၞန်ပါ်မဇၞော်အိုတ် (GCD) ကေုာံ ဂၞန်ပတၟောအ်မဍောတ်အိုတ် (Least Common Multiple - LCM) ဝွံ နွံကဵု ပရေင်ဆက်စပ် သင်္ချာ မခိုင်ကၠိုက် ဗွဲမလောန် ရ။

သွက် ဂၞန်အလုံ ဓမ္မတာ ၜါ $a$ ကဵု $b$ ဂှ် ဖော်မျူလာ အဓိက ဂှ် ဒှ် - $$a \times b = \gcd(a, b) \times \text{lcm}(a, b)$$

ယဝ်ရ ပိုယ် တီလဝ် GCD မ္ဂး၊ ပိုယ် ဂၠာဲ LCM ပြဟ်ပြဟ် မာန် အတိုင် ဗွဲသၟဝ် ဏအ် ရ - $$\text{lcm}(a, b) = \frac{|a \times b|}{\gcd(a, b)}$$ ဥပမာ: $a = 12, b = 18$။ တီလဝ် $\gcd(12, 18) = 6$ မ္ဂး။ $\text{lcm}(12, 18) = \frac{12 \times 18}{6} = \frac{216}{6} = 36$ ရ။

၇။ သဘာဝ ကေုာံ ဂုဏ်သတ္တိ သင်္ချာဂမၠိုင် (Mathematical Properties)

GCD နွံကဵု ဂုဏ်သတ္တိ သဇိုင် (Properties) ဗွဲမဂၠိုင် မကဵု အထံက်အပင် သွက် ပရေင်ချပ်ဂၞန် အာလ်ဂျဳဗရာ ရ -

1. သဘာဝ ဖလှာဲဒၞာဲ (Commutativity): $\gcd(a, b) = \gcd(b, a)$
2. သဘာဝ ပံင်ကောံ (Associativity): $\gcd(a, \gcd(b, c)) = \gcd(\gcd(a, b), c)$
3. အာဲဒေန်တဳတဳ ဗဳဇြောတ် (Bézout's identity): သွက် ဂၞန် ၜါ $a, b$ ယဝ်ရ $\gcd(a, b) = d$ မ္ဂး၊ နွံ ဂၞန်အလုံ $x$ ကဵု $y$ မကဵု သွဟ် လၟေင် $ax + by = d$ ရ။ ဥပမာ သွက် $\gcd(12, 8) = 4$ မ္ဂး $12(1) + 8(-1) = 4$ ရ။
4. ယဝ်ရ $m$ ဒှ် ဂၞန် ဓမ္မတာ မ္ဂး၊ $\gcd(m \cdot a, m \cdot b) = m \cdot \gcd(a, b)$ ရ။

၈။ လွပ် ပ္ဍဲ သင်္ချာ ကေုာံ ဘဝလၟိုန်တ္ၚဲ (Applications in Mathematics and Daily Life)

လွပ် မပြာကတ် အိုတ် သွက် GCD ပ္ဍဲ သင်္ချာ သဇိုင် ဂှ် ဒှ် ပရေင်ဖ္ဍန် ဂၞန်ကဝက် (Simplifying fractions) ရောင်။ ယဝ်ရ ပိုယ် မိက်ဂွံ ဖ္ဍန် ဂၞန်ကဝက် $\frac{a}{b}$ ညံင်ဂွံ ဒှ် ကဆံင် သၟဝ်အိုတ် (Lowest terms) မ္ဂး၊ ပိုယ် ဒးပါ် ကရေက် သီု လပါ်လတူ ($a$) ကေုာံ သၟဝ် ($b$) နကဵု $\gcd(a, b)$ ရ။

ဥပမာ - သွက်ဂွံ ဖ္ဍန် $\frac{42}{56}$

• $\gcd(42, 56) = 14$
• $\frac{42 \div 14}{56 \div 14} = \frac{3}{4}$

ပ္ဍဲကဵု ဘဝလၟိုန်တ္ၚဲ မ္ဂး GCD ဝွံ စကာ သွက်ဂွံ ပါ်ကရေက် ကပေါတ် ဟွံသေင်မ္ဂး အရှာံ ညံင်ဂွံ တုပ်သၟဟ် ညဳသာ ရ။ ဥပမာ - ဌာန်တိ မွဲ နွံ ဇမၠိင် ၂၅၂ မဳတာ ကေုာံ အနာံ ၁၀၅ မဳတာ၊ မိက်ဂွံ ခေတ် စတုရန်း တုပ်တုပ် ဇၞော်အိုတ် မ္ဂး၊ ဇမၠိင် ဇၟာပ် စတုရန်း ဂှ် ဒးဒှ် $\gcd(252, 105) = 21$ မဳတာ ရ။

၉။ လွပ် ပ္ဍဲ ကွတ်ကောန်ပျူတာ ကေုာံ ဂီုကၠီု (Applications in Computer Science and Cryptography)

ပ္ဍဲကဵု ခေတ် ကောန်ပျူတာ၊ လညာတ် GCD ကေုာံ ယူကလိတ် အလ်ဂဝ်ရဳသမ် (Extended Euclidean Algorithm) ဂှ် ဒှ် နှောတ် သွက် ကွတ်ဂီုကၠီု (Cryptography) ဗွဲတၟေင် ပ္ဍဲ သၞောတ် RSA Encryption ရ။

သွက်ဂွံ ဒက်ပတန် ကောတ် (Keys) ပ္ဍဲ RSA ဂှ်၊ ပရေင်ရုဲစှ် ဂၞန် $e$ မဒှ် ဂၞန်သဇိုင်ရေင်သကအ် (Coprime) ကဵု ဂၞန် $\phi(n)$ ဂှ် ကိစ္စဇၞော် ဗွဲမလောန် ရ။ ညးတအ် သ္ဒးစၟတ်သမ္တီ ဒဒှ်ရ $\gcd(e, \phi(n)) = 1$ သွက် သၞောတ်ဂီုကၠီု ဂွံ တန်ကြန် ရ။ လၟေင်ကမၠောန် ယူကလိတ် မဇၞော်မောဝ်လဝ် ဂှ် စကာ သွက်ဂွံ ဂၠာဲ ကောတ် ပၞုက် (Private key $d$) မာန် ဗွဲမပြဟ် ရ။ အရာဏအ် ထ္ၜးကဵု ဒဒှ်ရ သဳအိုရဳ သဇိုင် တမၠာ တအ်ဂှ် ဆက် မင်မဲ ဒၟံင် ပရေင်ဂီုကၠီု အင်တာနက် အလုံဂၠးတိ စဵုကဵု တ္ၚဲဏအ် ရ။

၁၀။ အနာဂတ် လဒက်ပတန် သင်္ချာ (Future of Mathematical Structures involving GCD)

ၜိုန်ရ လညာတ် GCD ဂှ် ဍာံပြ သွက် ဂၞန်အလုံ (Integers) ကီုလေဝ်၊ ပ္ဍဲကဵု သင်္ချာ အာဗ်သတြက် (Abstract Algebra) မ္ဂး ညးတအ် လ္ၚတ် ဆက်အာ သွက် လဒက်ပတန် တၞဟ်ခြာ မပ္တံကဵု ပဝ်လဳနဝ်မဳယာယ် (Polynomials) ကေုာံ ရิง (Rings) ရ။

ပ္ဍဲ လဒက်ပတန် မကော်စ Unique Factorization Domains (UFDs) ကေုာံ Principal Ideal Domains (PIDs) တအ်ဂှ် လညာတ် GCD ဆက်တန်တဴ ဒၟံင် ရ။ ပရေင်သုတေသန ပ္ဍဲ သင်္ချာ ခေတ်တၟိ တအ်ဂှ် ဆက်တုဲ လ္ၚတ်ဒၟံင် ဂုဏ်သတ္တိ GCD ပ္ဍဲကဵု လဒက်ပတန် မလှဲလး အာ တအ် သွက်ဂွံ သောင်ကလး ပြသၞာ သဳအိုရဳဂၞန် မဇြိုင်သန် တအ် ရောင်။

ဆက်ဗှ်လ္ၚတ်

• ဂၞန်ပတၟောအ်မဍောတ်အိုတ် (Least Common Multiple)
• သဳအိုရဳ သဇိုင် ပညာဂၞန် (Fundamental theorem of arithmetic)
• နဲကဲ ယူကလိတ် (Euclidean algorithm)
• ဂၞန်သဇိုင်ရေင်သကအ် (Coprime integers)