အွိုင်လာ၏ သီအိုရမ်

ကိန်းသီအိုရီ တွင် အွိုင်လာ၏ သီအိုရမ် (Euler's theorem) ကို ဖဲမ-အွိုင်လာ သီအိုရမ် (Fermat-Euler theorem) သို့မဟုတ် အွိုင်လာ၏ တိုးရှန့် သီအိုရမ် (Euler's totient theorem) ဟုလည်း ခေါ်ဆိုကြသည်။ ၎င်းအမည်မှာ လီယွန်ဟတ် အွိုင်လာ (Leonhard Euler) နှင့် ပီယား ဒေ ဖဲမ (Pierre de Fermat) တို့ကို အစွဲပြု၍ ပေးထားခြင်း ဖြစ်သည်။ ဤသီအိုရမ်သည် ဖဲမ၏ သီအိုရမ်အငယ် (Fermat's little theorem) ကို အလိုရှိသလို ရွေးချယ်ထားသော မော်ဂျူးလပ်စ်များ (moduli) $n\in \mathbb {N}$ အတွက် ယေဘုယျပြုထားခြင်း (generalization) ဖြစ်သည်။ အဆိုပါ $n$ များသည် သုဒ္ဓကိန်းများ (prime numbers) ဖြစ်ရန် မလိုအပ်ပါ။

ဖော်ပြချက် (Statement)

အွိုင်လာ၏ သီအိုရမ်အရ $\gcd(a,n)=1$ ဖြစ်သော $a,n\in \mathbb {N}$ အားလုံးအတွက် အောက်ပါဆက်သွယ်ချက် မှန်ကန်သည်။

• $a^{\varphi (n)}\equiv 1{\pmod {n}}$

ဤနေရာတွင် $\gcd$ သည် သဘာဝကိန်းများဖြစ်သော $a$ နှင့် $n$ တို့၏ အကြီးဆုံး ဘုံဆခွဲကိန်း (greatest common divisor) ဖြစ်သည်။ $\varphi (n)$ သည် အွိုင်လာ၏ တိုးရှန့် ဖန်ရှင် (Euler's totient function) ဖြစ်သည်။ ယင်းဖန်ရှင်သည် မော်ဂျူလို $n$ တွင် $n$ နှင့် နှိုင်းရသုဒ္ဓ (coprime) ဖြစ်သော အကြွင်းအရေအတွက်ကို ဖော်ပြသည်။

မော်ဂျူးလပ်စ်သည် သုဒ္ဓကိန်း $p$ ဖြစ်သောအခါ $\varphi (p)=p-1$ ဖြစ်သည်။ ထို့ကြောင့် ဤအခြေအနေတွင် အွိုင်လာ၏ သီအိုရမ်သည် ဖဲမ၏ သီအိုရမ်အငယ် အဖြစ်သို့ လျော့ကျသွားသည်။

အသုံးချမှုများ (Applications)

ကြီးမားသော ထပ်ကိန်းများ (exponents) ကို မော်ဂျူလို $n$ ဖြင့် တွက်ချက်ရာတွင် လျှော့ချရန်အတွက် အွိုင်လာ၏ သီအိုရမ်ကို အသုံးပြုသည်။ ၎င်းမှတစ်ဆင့် ကိန်းပြည့် (integer) $k$ များအတွက် $a^{x}\equiv a^{x+k\cdot \varphi (n)}{\pmod {n}}$ ဟူသော အချက်ကို ဆင်းသက်ရရှိနိုင်သည်။ ဤဂုဏ်သတ္တိကြောင့် ၎င်းကို ကွန်ပျူတာအခြေခံ ကုဒ်ဝှက်ရေးသားခြင်း (cryptography) တွင် လက်တွေ့အသုံးချကြသည်။ ဥပမာအားဖြင့် RSA လျှို့ဝှက်သင်္ကေတပြောင်း (encryption) အဆင့်ဆင့်တွက်နည်း (algorithm) တွင် အသုံးပြုခြင်းမျိုး ဖြစ်သည်။

ဥပမာ (Example)

ဒသမကိန်းစနစ် (decimal system) တွင် $7^{222}$ ၏ နောက်ဆုံး ဂဏန်းနေရာသည် မည်သည့်ဂဏန်း ဖြစ်မည်ကို ရှာဖွေခြင်းသည် တစ်နည်းအားဖြင့် $7^{222}$ သည် မော်ဂျူလို ၁၀ တွင် မည်သည့် ဒသမဂဏန်းနှင့် ထပ်တူညီ (congruent) မည်နည်းဟု မေးခြင်းပင် ဖြစ်သည်။

ပထမဦးစွာ $\gcd(7,10)=1$ နှင့် $\varphi (10)=4$ ဖြစ်ကြောင်းကို သတိပြုပါ။ ထို့ကြောင့် အွိုင်လာ၏ သီအိုရမ်အရ အောက်ပါအတိုင်း ရရှိသည်။

• $7^{4}\equiv 1{\pmod {10}}$

ထို့နောက် အောက်ပါတွက်ချက်မှုကို ဆက်လက်ရရှိသည်။

• $7^{222}=7^{4\cdot 55+2}=(7^{4})^{55}\cdot 7^{2}\equiv 1^{55}\cdot 7^{2}{\pmod {10}}\equiv 49{\pmod {10}}\equiv 9{\pmod {10}}$

ယေဘုယျအားဖြင့် အောက်ပါဆက်သွယ်ချက် မှန်ကန်သည်။

• $a^{b}\equiv a^{b{\bmod {\varphi }}(n)}{\pmod {n}}\qquad a,b,n\in \mathbb {N} \land \gcd(a,n)=1$

အွိုင်လာ၏ သီအိုရမ်အတွက် သက်သေပြချက် (Proof of Euler's Theorem)

မော်ဂျူလို $n$ တွင် မြှောက်ခြင်းဆိုင်ရာ ပြောင်းပြန်လှန်နိုင်သော (multiplicatively invertible) အစုဝင်များပါဝင်သည့် အစုကို $(\mathbb {Z} /n\mathbb {Z} )^{\times }=\{r_{1},\dots ,r_{\varphi (n)}\}$ ဟု သတ်မှတ်ပါမည်။ $\gcd(a,n)=1$ ဖြစ်သော $a$ တိုင်းအတွက် $x\mapsto ax$ ဟူသော ပုံဖော်မှု (map) သည် $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ ၏ ပါမြူတေးရှင်း (permutation) တစ်ခု ဖြစ်သည်။ အဘယ်ကြောင့်ဆိုသော် $ax\equiv ay{\pmod {n}}$ ဖြစ်လျှင် $x\equiv y{\pmod {n}}$ ဖြစ်သောကြောင့် ဖြစ်သည်။ မြှောက်ခြင်းသည် ဖလှယ်ရဖြစ်သော (commutative) ကြောင့် အောက်ပါအတိုင်း ဆက်လက်ရရှိသည်။

• $r_{1}\cdots r_{\varphi (n)}\equiv (ar_{1})\cdots (ar_{\varphi (n)})\equiv r_{1}\cdots r_{\varphi (n)}a^{\varphi (n)}{\pmod {n}}$

ထို့အပြင် $r_{i}$ များသည် $i$ အားလုံးအတွက် ပြောင်းပြန်လှန်နိုင်သောကြောင့် အောက်ပါရလဒ်ကို ရရှိသည်။

• $1\equiv a^{\varphi (n)}{\pmod {n}}$

အခြားသော သက်သေပြချက် (Alternative Proof)

အွိုင်လာ၏ သီအိုရမ်သည် အုပ်စုသီအိုရီ (group theory) မှ လာဂေါင့်၏ သီအိုရမ် (Lagrange's theorem) ၏ တိုက်ရိုက်ရလဒ် တစ်ခုဖြစ်သည်။ အဆုံးရှိ အစီအစဉ် (finite order) $m$ ရှိသော မည်သည့်အုပ်စု $G$ တွင်မဆို အစုဝင်တိုင်း၏ $m$ ကြိမ်မြောက် ထပ်ကိန်းသည် ထပ်တူရအစုဝင် (identity element) ဖြစ်သည်။ ဤနေရာတွင် $G=\{1\leq a\leq n\mid \gcd(a,n)=1\}=(\mathbb {Z} /n\mathbb {Z} )^{\times }$ ဖြစ်သည်။ ထို့ကြောင့် $|G|=\varphi (n)$ ဖြစ်သည်။ ၎င်းအုပ်စု $G$ ၏ တွက်ချက်မှုမှာ မော်ဂျူလို $n$ မြှောက်ခြင်း ဖြစ်သည်။

ကိုးကား (References)

• Scheid၊ Harald (2003)၊ Zahlentheorie၊ Spektrum Akademischer Verlag၊ ISBN 3-8274-1365-6