यूलर की प्रमेय फर्मेट के छोटे प्रमेय का एक सामान्यीकरण है जो पूर्णांक मॉड्यूलो सकारात्मक पूर्णांक की शक्तियों के साथ है। यह आरएसए क्रिप्टोसिस्टम के लिए सैद्धांतिक सहायक संरचना जैसे प्राथमिक संख्या सिद्धांत के अनुप्रयोगों में वृद्धि करता है।
यह प्रमेय कहता है कि प्रत्येक a और n के लिए जो अपेक्षाकृत अभाज्य हैं -
$$\mathrm{a^{\phi \left ( n \right )}\, \equiv\, 1\left (mod \, n \right) }$$
जहां ф(n) यूलर का टोटिएंट फ़ंक्शन है, जो n से कम धनात्मक पूर्णांकों की संख्या की गणना करता है जो n से अपेक्षाकृत अभाज्य हैं।
ऐसे पूर्णांकों के समुच्चय पर विचार करें -
आर ={x<उप>1 , x2 , ... x<उप>ф(एन) }, अर्थात्, R का प्रत्येक अवयव xi अद्वितीय धनात्मक पूर्णांक है जो n से कम है और ged(xi, n) =1 है। फिर प्रत्येक अवयव को a और modulo n से गुणा करें -
एस ={(कुल्हाड़ी<उप>1 मॉड एन), (कुल्हाड़ी<उप>2 मॉड एन), ... (कुल्हाड़ी<उप>ф(एन) मॉड एन)}
क्योंकि a, n और xi . के लिए अपेक्षाकृत अभाज्य है n, axi . के लिए अपेक्षाकृत अभाज्य है n से भी अपेक्षाकृत अभाज्य होना चाहिए। इसलिए, S के सभी सदस्य पूर्णांक हैं जो n से कम हैं और जो n से अपेक्षाकृत अभाज्य हैं।
एस में कोई डुप्लीकेट नहीं हैं।
अगर कुल्हाड़ी<उप>मैं मॉड एन और एन =कुल्हाड़ी<उप>जे mod n फिर xi =एक्स<उप>जे
$$\mathrm{इसलिए,\, \Pi _{i=1}^{\phi \left ( n \right )}\बाएं ( ax_{i}\, mod\, n \right )=\Pi _{ i=1}^{\phi \left ( n \right )}\, x_{i}}$$
$$\mathrm{\Pi _{i=1}^{\phi \left ( n \right )}\, ax_{i}\equiv \Pi _{i=1}^{\phi \left ( n \ दाएं)}\, x_{i}\बाएं (mod\, n \right)}$$
$$\mathrm{a^{\phi \left ( n \right )}\, x\left [ \Pi _{i=1}^{\phi \left ( n \right )}\, x_{i} \right ]=\Pi _{i=1}^{\phi \left ( n \right )}\, x_{i}\बाएं (mod\, n \right)}$$
$$\mathrm{a^{\phi \left ( n \right )}\equiv 1\left (mod\, n \right)}$$
यूलर टोटिएंट फंक्शन
Euler's Totient फ़ंक्शन गणितीय गुणक फलन है जो दिए गए पूर्णांक तक धनात्मक पूर्णांकों की गणना करता है, जिन्हें आमतौर पर 'n' के रूप में जाना जाता है, जो कि 'n' के लिए एक अभाज्य संख्या है और फ़ंक्शन का उपयोग उन अभाज्य संख्याओं की संख्या को समझने के लिए किया जा सकता है जो पूर्वi दिए गए पूर्णांक 'एन' तक।
यूलर के टोटिएंट फंक्शन को यूलर का फी फंक्शन भी कहा जाता है। यह क्रिप्टोग्राफी में एक महत्वपूर्ण भूमिका निभाता है। यह उन पूर्णांकों की संख्या का पता लगा सकता है जो n से छोटे हैं और n से अपेक्षाकृत अभाज्य हैं। संख्याओं का ये सेट $\mathrm{Z_{n}^{*}}$ द्वारा परिभाषित किया गया है (संख्या जो n से छोटी है और n से अपेक्षाकृत अभाज्य है)।
यूलर का टोटिएंट फंक्शन कई तरह से फायदेमंद होता है। इसका उपयोग RSA एन्क्रिप्शन सिस्टम में किया जा सकता है, जिसका उपयोग सुरक्षा लक्ष्यों के लिए किया जा सकता है। फ़ंक्शन अभाज्य संख्या सिद्धांत से संबंधित है, और यह बड़ी गणनाओं की गणना में भी फायदेमंद है। फ़ंक्शन का उपयोग बीजीय गणना और सरल संख्याओं में किया जा सकता है।
फ़ंक्शन को इंगित करने के लिए उपयोग किया जाने वाला प्रतीक ϕ है, और इसे फाई फ़ंक्शन के रूप में भी जाना जाता है। फ़ंक्शन में व्यावहारिक उपयोग के बजाय अधिक सैद्धांतिक उपयोग शामिल है। फ़ंक्शन की समझदार आवश्यकता सीमित है।
फ़ंक्शन को केवल सैद्धांतिक स्पष्टीकरण के बजाय कई व्यावहारिक उदाहरणों के माध्यम से बेहतर ढंग से समझा जा सकता है। यूलर के टोटिएंट फ़ंक्शन की गणना के लिए कई नियम हैं, और विभिन्न संख्याओं के लिए, विभिन्न नियमों का उपयोग किया जाना है।
यूलर टोटिएंट फ़ंक्शन ф(n) निम्नलिखित नियमों की सहायता से $\mathrm{Z_{n}^{*}}$ में तत्वों की संख्या की गणना करता है -
-
(1) =0.
-
ф(P) =P - 1 यदि P एक अभाज्य है।
-
ф(m x n) =ф(m) x ф(n) यदि m और n अपेक्षाकृत अभाज्य हैं।
-
ф(प e ) =पी e - पी e−1 (यदि P एक अभाज्य है।)
(n) का मान प्राप्त करने के लिए निम्नलिखित चार नियमों को जोड़ा जा सकता है, n को इस रूप में गुणित करें
$$\mathrm{n=P_{1}^{e1}\, x\,P_{2}^{e2}x\cdot \cdot \cdot P_{k}^{ek}}$$
$$\mathrm{\phi \left ( n \right )=\left ( P_{1}^{e1}-P_{1}^{e1-1} \right )\left ( P_{2}^{e2 }-P_{2}^{e2-1} \right )x\cdot \cdot \cdot x\left (P_{k}^{ek}-P_{k}^{ek-1} \right )}$ $
(n) खोजने की कठिनाई n का गुणनखंडन ज्ञात करने की कठिनाई पर निर्भर करती है।