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

ऑयलर का प्रमेय (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) का भी आधार है।

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

• मॉड्युलर गणित (modular arithmetic)
• ऑयलर का सूत्र
• ऑयलर समीकरण

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

• एरिक डब्ल्यू वेइसटीन, मैथवर्ल्ड पर Euler's Totient Theorem
• Euler's Theorem at PlanetMath