ऑयलर का प्रमेय

ऑयलर का प्रमेय (Euler's theorem) संख्या सिद्धान्त के अन्तर्गत एक प्रमेय है। इसे 'फर्मट-ऑयलर प्रमेय' भी कहते हैं। इसे सर्वप्रथम सन् १७३६ में ऑयलर ने प्रस्तुत एवं सिद्ध किया था।

इस प्रमेय के अनुसार यदि n तथा a दो परस्पर अभाज्य (coprime) धन पूर्णांक हों तो,

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

जहाँ φ(n) ऑयलर का टोशेंट फलन (Euler's totient function) है।

उपयोग

इस प्रमेय का उपयोग large powers modulo n को छोटा या सरल बनाने में किया जा सकता है। मान लीजिए कि 7²²² के मान में इकाई के स्थान पर आने वाली अंक का पता लगाना है, अर्थात् 7²²² (mod 10) का मान निकालना है। ध्यान दीजिए कि 7 और 10 परस्पर अभाज्य हैं तथा φ(10) = 4. इस प्रकार ऑयलर के प्रमेय से 7⁴ ≡ 1 (mod 10) मिलता है और 7²²² ≡ 7^{4×55 + 2} ≡ (7⁴)⁵⁵×7² ≡ 1⁵⁵×7² ≡ 49 ≡ 9 (mod 10).

जब भी मॉड्युलो n के घात का सरलीकरण करना हो, (जहाँ a और n परस्पर अभाज्य हैं), तो a के घात पर modulo φ(n) की गणना करनी पड़ेगी।

यदि x ≡ y (mod φ(n)), तो ax ≡ ay (mod n).

ओयलर का प्रमेय आरएसए कूटन (RSA encryption) का भी आधार है।

इन्हें भी देखें

बाहरी कड़ियाँ

यह लेख एक आधार है। जानकारी जोड़कर इसे बढ़ाने में विकिपीडिया की मदद करें।