ဂဏန်းသီအိုရီ၏ အခြေခံများ

ဂဏန်းသီအိုရီ၏ အခြေခံများ

ဂဏန်းသီအိုရီသည် ကိန်းပြည့်များ၏ ဂုဏ်သတ္တိများကို လေ့လာသော သင်္ချာ၏ ဌာနခွဲတစ်ခုဖြစ်သည်။ ရိုးရှင်းပုံရသော်လည်း—ကိန်းပြည့်များတွင် …၊ -၂၊ -၁၊ ၀၊ ၁၊ ၂၊ … တို့သာ ပါဝင်သောကြောင့်—ကိန်းသီအိုရီတွင် အလွန်ကြွယ်ဝသော ဖွဲ့စည်းပုံရှိသည်။ ခေတ်သစ်သင်္ချာ၊ ကုဒ်ဝှက်ခြင်းနှင့် ကွန်ပျူတာသိပ္ပံတွင် အရေးကြီးသော အယူအဆများစွာသည် စားနိုင်ခြင်း၊ မူလကိန်းနှင့် ကိုက်ညီခြင်းကဲ့သို့သော ကိန်းသီအိုရီ၏ အခြေခံအယူအဆများတွင် အခြေခံထားသည် ။ ဤဆောင်းပါးသည် ကိန်းသီအိုရီ၏ အဓိကအုတ်မြစ်များ- စားနိုင်ခြင်းနှင့် Euclid ၏ အယ်လဂိုရီသမ်၊ မူလကိန်းများနှင့် ဆခွဲကိန်းခွဲခြင်း ၊ မော်ဒူလို ဂဏန်းသင်္ချာနှင့် အဆင့်မြင့်အသုံးချမှုများနှင့် လမ်းညွှန်ချက်အချို့ကို ပြန်လည်သုံးသပ်သည်။

၁။ ကိန်းပြည့်များနှင့် အခြေခံလုပ်ဆောင်ချက်များ

ဂဏန်းသီအိုရီသည် ယေဘုယျအားဖြင့် ℤ ဖြင့် ဖော်ပြထားသော ကိန်းပြည့်များအစုပေါ်တွင် လုပ်ဆောင်သည်။ အသုံးပြုသော အခြေခံလုပ်ဆောင်ချက်များမှာ ပေါင်းခြင်း၊ နုတ်ခြင်းနှင့် မြှောက်ခြင်းတို့ဖြစ်သည်။ ယုတ္တိတန်သော သို့မဟုတ် ကိန်းစစ်များနှင့်မတူဘဲ၊ ကိန်းပြည့်များဖြင့် စားခြင်းသည် ကိန်းပြည့်ကို အမြဲတမ်း မရရှိစေပါ။ ဤနေရာတွင် အကြွင်းဖြင့် စားခြင်းဆိုင်ရာ သဘောတရားသည် အဓိကကျလာပါသည်။

ဂဏန်းသီအိုရီတွင် အရေးကြီးသော ဆက်နွယ်မှုတစ်ခုမှာ စားနိုင်စွမ်းဖြစ်သည်။ ကိန်းပြည့်များ \(a\) နှင့် \(b\) အတွက်၊ \(b = ak\) ရှိသော ကိန်းပြည့် \(k\) ရှိပါက \(a \mid b\) ဟု ရေးသားပါသည်။ ဥပမာ၊ \(12 = 3 \times 4\) ဖြစ်သောကြောင့် \(3 \mid 12\) ဖြစ်သော်လည်း \(12 = 5k\ ဖြစ်သောကြောင့် \(5 \nmid 12\) မှာ ကိန်းပြည့် \(k\) မရှိသောကြောင့် ဖြစ်သည်။

ပိုင်းခြားနိုင်စွမ်းတွင် အောက်ပါအခြေခံဂုဏ်သတ္တိများရှိသည်-
– \(a \mid b\) နှင့် \(a \mid c\) ဖြစ်ပါက \(a \mid (b+c)\) နှင့် \(a \mid (bc)\)။
– \(a \mid b\) ဖြစ်ပါက၊ \(k\) ကိန်းပြည့်တိုင်းအတွက် \(a \mid (bk)\) ဖြစ်ရမည်။
– \(a \mid b\) နှင့် \(b \mid c\) ဖြစ်ပါက \(a \mid c\)။

ဤရိုးရှင်းသောဂုဏ်သတ္တိများသည် ကိန်းပြည့်များအကြောင်း ဖော်ပြချက်များစွာကို သက်သေပြရန်အတွက် ကိရိယာများအဖြစ် ဆောင်ရွက်ပေးသည်။

၂။ ပိုင်းခြားခြင်း အယ်လဂိုရီသမ်

စားခြင်းသီအိုရမ်က ဤသို့ဆိုသည်- ကိန်းပြည့် (a\) နှင့် အပေါင်းကိန်းပြည့် (b\) တိုင်းအတွက်၊ ထူးခြားသော ကိန်းပြည့် (q\) နှင့် (r\) များ ရှိပြီး အောက်ပါအတိုင်းဖြစ်သည်-
\[
a = bq + r, \quad 0 \le r < b \] ဤနေရာတွင် \(q\) ကို စားလဒ်ဟုခေါ်ပြီး \(r\) ကို အကြွင်းဟုခေါ်သည်။ ဥပမာ- \(a=29\) နှင့် \(b=5\) ဖြစ်ပါက \(29 = 5\cdot 5 + 4\)၊ ထို့ကြောင့် \(q=5\) နှင့် \(r=4\) ဖြစ်သည်။ ဒီသဘောတရားက အရေးကြီးပါတယ်၊ ဘာလို့လဲဆိုတော့ အခြေခံအုတ်မြစ်ဖြစ်လို့ပါ။ GCD ကိုရှာဖွေရန် မော်ဒူလိုလုပ်ဆောင်ချက်နှင့် Euclid ၏ အယ်လဂိုရီသမ်။ ၃။ အကြီးမားဆုံးဘုံစားကိန်း (GCD) နှင့် Euclid ၏ အယ်လဂိုရီသမ် ကိန်းပြည့်နှစ်ခု \(a\) နှင့် \(b\) အတွက် (နှစ်ခုစလုံး သုညမဟုတ်ပါ)၊ အကြီးမားဆုံးဘုံစားကိန်း သို့မဟုတ် GCD—\(\gcd(a,b)\) ဟုသတ်မှတ်သည်—သည် ၎င်းတို့နှစ်ခုလုံးကို ပိုင်းခြားသော အကြီးဆုံးအပေါင်းကိန်းပြည့်ဖြစ်သည်။ GCD ကိုတွက်ချက်ရန် အထိရောက်ဆုံးနည်းလမ်းမှာ Euclid ၏ အယ်လဂိုရီသမ်ဖြစ်သည်။ စားကိန်းသီအိုရမ်အရ၊ \[ a = bq + r \] ဖြစ်လျှင်- \[ \gcd(a,b) = \gcd(b,r) \] ဤလုပ်ငန်းစဉ်ကို အကြွင်း \(r\) သည် 0 ဖြစ်သည်အထိ ထပ်ခါတလဲလဲလုပ်ဆောင်သည်။ နောက်ဆုံးအဆင့်တွင် GCD သည် နောက်ဆုံး သုညမဟုတ်သော စားကိန်းဖြစ်သည်။ အမြန်ဥပမာ- \(\gcd(48,18)\) ကိုရှာပါ။ – \(၄၈ = 18\cdot 2 + 12\) – \(၁၈ = 12\cdot 1 + 6\) – \(၁၂ = 6\cdot 2 + 0\) ထို့နောက် \(\gcd(48,18)=6\)။ Euclid ၏ အယ်လဂိုရီသမ်သည် အလွန်အရေးကြီးပါသည်၊ အဘယ်ကြောင့်ဆိုသော် ၎င်းသည် ကြီးမားသော ဂဏန်းများအတွက်ပင် မြန်ဆန်သောကြောင့်ဖြစ်ပြီး တွက်ချက်မှုတွင် အလွန်အသုံးဝင်ပါသည်။ ၄။ မျဉ်းဖြောင့်ပေါင်းစပ်မှုများနှင့် Bézout ၏ အမှတ်အသား အခြေခံရလဒ်တစ်ခုမှာ Bézout ၏ အမှတ်အသားဖြစ်သည်- သုညမဟုတ်သော ကိန်းပြည့် \(a\) နှင့် \(b\) များအတွက်၊ \(x\) နှင့် \(y\) ကိန်းပြည့်များ ရှိပြီး- \[ \gcd(a,b) = ax + by \] ဆိုလိုသည်မှာ GCD ကို \(a\) နှင့် \(b\) ၏ မျဉ်းဖြောင့်ပေါင်းစပ်မှုအဖြစ် ရေးသားနိုင်သည်။ \(x\) နှင့် \(y\) ၏ တန်ဖိုးများကို တိုးချဲ့ထားသော Euclid ၏ အယ်လဂိုရီသမ်ဖြင့် ရှာဖွေနိုင်သည်။ Bézout ရဲ့ identity ဟာ အောက်ပါတို့ကို ဖြေရှင်းရာမှာ အဓိကကျပါတယ်- – linear Diophantine equation \(ax+by=c\)၊ – သူ့ရဲ့ modulo inverse ကို ရှာဖွေခြင်း (cryptography မှာ အရေးကြီးပါတယ်)။ ၅။ prime numbers များနှင့် factorization prime number ဆိုသည်မှာ 1 ထက်ကြီးသော positive divisor နှစ်ခုသာရှိသော အပေါင်း integer တစ်ခုဖြစ်ပြီး 1 နှင့် ၎င်းကိုယ်တိုင်ဖြစ်သည်။ ၂၊ ၃၊ ၅၊ ၇၊ ၁၁ ကဲ့သို့သော နံပါတ်များသည် prime ဖြစ်သည်။ 1 ထက်ကြီးသော်လည်း prime မဟုတ်သော နံပါတ်များကို composite ဟုခေါ်သည်၊ ဥပမာ ၁၂၊ ၂၁၊ ၃၅။ အကျော်ကြားဆုံး အယူအဆမှာ Fundamental Theorem of Arithmetic ဖြစ်သည်- integer တိုင်း \(n>1\) ကို prime numbers များ၏ မြှောက်လဒ်အဖြစ် ထူးခြားစွာ (အစီအစဉ်အတိုင်း) ရေးသားနိုင်သည်။
\[
n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}
\]
Misalnya-
\[
၃၆၀ = ၂^၃ \cdot ၃^၂ \cdot ၅
\]
ဤ factorization ၏ ထူးခြားမှုသည် ကြီးမားသော ဂဏန်းများကို factor လုပ်ခြင်း၏ အခက်အခဲအပေါ် မူတည်သည့် RSA cryptography အပါအဝင် အဆင့်မြင့် အကြောင်းအရာများစွာ၏ အခြေခံအုတ်မြစ်ဖြစ်သည်။

၆။ ကိုက်ညီမှုနှင့် မော်ဒူလို ဂဏန်းသင်္ချာ

မော်ဒူလို ဂဏန်းသင်္ချာသည် စားခြင်း၏ အကြွင်းကို အခြေခံ၍ ဂဏန်းများကို လေ့လာသည်။ ကျွန်ုပ်တို့ ဤသို့ပြောသည်-
\[
a \equiv b \pmod{m}
\]
\(m \mid (ab)\) ဖြစ်ပါက၊ \(a\) နှင့် \(b\) တို့ကို \(m\) ဖြင့်စားသောအခါ တူညီသော အကြွင်းရှိသည်ဟု ဆိုလိုသည်။

ဥပမာ- \(17 \equiv 5 \pmod{12}\) သည် ၁၂ ဖြင့်စားနိုင်သောကြောင့်ဖြစ်သည်။ မော်ဂျူလို ၁၂၊ ၁၇ နှင့် ၅ တို့ကို ညီမျှသည်ဟု ယူဆသည်။

Congruence သည် ordinary operations များနှင့် ဂုဏ်သတ္တိများ အတူတူပင်ဖြစ်သည်-
– \(a \equiv b \pmod{m}\) နှင့် \(c \equiv d \pmod{m}\) ဖြစ်ပါက၊
\(a+c \equiv b+d \pmod{m}\) နှင့် \(ac \equiv bd \pmod{m}\)။

မော်ဒူလို ဂဏန်းသင်္ချာသည် အောက်ပါတို့အတွက် အလွန်အသုံးဝင်ပါသည်-
- ကာလအပိုင်းအခြားအလိုက် ပုံစံများကို ဆုံးဖြတ်ခြင်း၊
- များပြားသောဒေတာများကို စစ်ဆေးပါ၊
– ထိရောက်သော တွက်ချက်မှု အယ်လဂိုရစ်သမ်များ ဒီဇိုင်းဆွဲခြင်း၊
- နှင့် ခေတ်သစ် ကုဒ်ဝှက်စနစ်။

၇။ မော်ဒူလို ပြောင်းပြန်နှင့် ကိုက်ညီမှုညီမျှခြင်း

နံပါတ် \(a\) တွင် နံပါတ် \(x\) ရှိပါက အောက်ပါအတိုင်း inverse modulo \(m\) ရှိသည်။
\[
ax \equiv 1 \pmod{m}
\]
\(\gcd(a,m)=1\) ဖြစ်မှသာ ဤပြောင်းပြန်တည်ရှိသည်။ ဥပမာအားဖြင့်၊ \(3\cdot 5=15\equiv 1 \pmod{7}\) 3 တွင် ပြောင်းပြန် modulo 7 ရှိသည်၊ ထို့ကြောင့် ၎င်း၏ပြောင်းပြန်သည် 5 ဖြစ်သည်။

modulo inverse သဘောတရားက အောက်ပါညီမျှခြင်းတွေကို ဖြေရှင်းဖို့ ပိုမိုလွယ်ကူစေပါတယ်-
\[
ax \equiv b \pmod{m}
\]
\(a^{-1}\) ၏ ပြောင်းပြန်တည်ရှိနေပါက၊ နှစ်ဖက်စလုံးကို မြှောက်ခြင်းဖြင့် အဖြေကို ရရှိနိုင်ပါသည်။
\[
x \equiv a^{-1} b \pmod{m}
\]

၈။ ဖာမတ်၏ သေးငယ်သော သီအိုရမ်နှင့် အွိုင်လာ၏ သီအိုရမ်

အခြေခံဂဏန်းသီအိုရီတွင် ထင်ရှားသော ရလဒ်နှစ်ခုမှာ-

၁။ ဖာမတ်၏ သေးငယ်သော သီအိုရမ်- \(p\) သည် မူလကိန်းဖြစ်ပြီး \(a\) ကို \(p\) ဖြင့် စား၍မရပါက-
\[
a^{p-1} \equiv 1 \pmod{p}
\]
၂။ Euler's theorem (ယေဘုယျပြုလုပ်ခြင်း): \(\gcd(a,m)=1\), ဖြစ်လျှင်:
\[
a^{\varphi(m)} \equiv 1 \pmod{m}
\]
ဤတွင် \(\varphi(m)\) သည် Euler ၏ totien function (1 နှင့် \(m\) အကြားရှိ ဂဏန်းအရေအတွက်) ဖြစ်ပြီး \(m\) အတွက် နှိုင်းယှဉ်လျှင် prime ဖြစ်သော ဂဏန်းများ အရေအတွက် ဖြစ်သည်။

ဤသီအိုရမ်များသည် ကွဲပြားသော ကုဒ်ဝှက်စနစ်များနှင့် မြန်ဆန်သော မော်ဒူလို တွက်ချက်မှုနည်းပညာများ၏ အခြေခံဖြစ်သည်။

၉။ အဆင့်မြင့်အသုံးချမှုများနှင့် လမ်းညွှန်ချက်များ

၎င်းသည် ကိန်းပြည့်များအကြောင်း ရိုးရှင်းသောမေးခွန်းတစ်ခုအဖြစ် စတင်ခဲ့သော်လည်း၊ ယခုအခါ ဂဏန်းသီအိုရီသည် ကျယ်ပြန့်သောနယ်ပယ်တစ်ခု ဖြစ်လာခဲ့သည်။ ၎င်း၏အသုံးချမှုများတွင် အောက်ပါတို့ပါဝင်သည်-
– လျှို့ဝှက်ကုဒ်ပညာ- RSA၊ Diffie–Hellman နှင့် elliptic curves များသည် prime၊ congruence နှင့် modulo inverse ဂုဏ်သတ္တိများကို အသုံးပြုသည်။
– ကွန်ပျူတာသိပ္ပံ- hashing၊ ကျပန်းနံပါတ်ထုတ်လုပ်သည့်စက်များနှင့် ကြီးမားသောနံပါတ်ကွန်ပျူတာအယ်လဂိုရစ်သမ်များ။
– ပေါင်းစပ်နည်းပညာများနှင့် ကုဒ်ရေးသားခြင်းသီအိုရီ- အမှားပြင်ဆင်သည့် ကုဒ်များနှင့် သီးခြားဖွဲ့စည်းပုံများ တည်ဆောက်ခြင်း။

ဤအခြေခံများပြီးနောက် မကြာခဏ လေ့လာလေ့ရှိသော အဆင့်မြင့်အကြောင်းအရာများတွင် non-linear Diophantine equations၊ quadratic residues၊ algebraic number theory နှင့် distribution of prime numbers များ ပါဝင်သည်။

ပိတ်

ဂဏန်းသီအိုရီ၏ အခြေခံများသည် စားနိုင်စွမ်းအား၊ GCF၊ မူလကိန်းများနှင့် ကိုက်ညီမှုဆိုင်ရာ သဘောတရားများအပေါ် အခြေခံထားသည်။ Euclid ၏ အယ်လဂိုရီသမ်မှ မော်ဒူလို ဂဏန်းသင်္ချာအထိ၊ အတွေးအခေါ်တစ်ခုစီသည် ကိန်းပြည့်များ၏ဖွဲ့စည်းပုံကို နားလည်ရန် အခြေခံအုတ်မြစ်ကို ဖွဲ့စည်းပေးပြီး အထူးသဖြင့် ဒစ်ဂျစ်တယ်ခေတ်တွင် လက်တွေ့ကမ္ဘာအသုံးချမှုများအတွက် လမ်းခင်းပေးသည်။ ဤအခြေခံသဘောတရားများကို ကျွမ်းကျင်စွာ ကျွမ်းကျင်ခြင်းသည် ခွဲခြားသင်္ချာပြဿနာများကို ခွဲခြမ်းစိတ်ဖြာရန်နှင့် ခေတ်သစ်ဂဏန်းသီအိုရီတွင် ပိုမိုနက်ရှိုင်းသော အကြောင်းအရာများကို စူးစမ်းလေ့လာရန်အတွက် အစွမ်းထက်သောကိရိယာများကို ပေးစွမ်းသည်။