यूलर का कुल कार्य

"φ(n)" redirects here. For other uses, see फ़ाई.

Not to be confused with यूलर फलन.

File:EulerPhi.svg

के पहले हजार मान φ(n). शीर्ष रेखा पर बिंदु दर्शाते हैं φ(p) कब p अभाज्य संख्या है, जो है p − 1.

संख्या सिद्धांत में, यूलर का कुल फलन किसी दिए गए पूर्णांक तक धनात्मक पूर्णांकों n की गणना करता है | जो n अपेक्षाकृत प्रमुख हैं | इसे ग्रीक अक्षर φ का प्रयोग $\varphi (n)$ या $\phi (n)$के रूप में लिखा गया है, और इसे यूलर का φ फलन भी कहा जा सकता है। दूसरे शब्दों में, यह 1 ≤ k ≤ n पूर्णांकों k की संख्या है | जिसके लिए सबसे बड़ा सामान्य भाजक gcd(n, k) 1 के समान है। इस रूप के पूर्णांक k को कभी-कभी n के योग के रूप में संदर्भित किया जाता है |

उदाहरण के लिए n = 9 के योग छह संख्याएँ 1, 2, 4, 5, 7 और 8 हैं। वे सभी 9 से अपेक्षाकृत अभाज्य हैं | किन्तु इस श्रेणी में अन्य तीन संख्याएँ, 3, 6 और 9 नहीं हैं | क्योंकि gcd(9, 3) = gcd(9, 6) = 3 इसलिए φ(9) = 6. एक अन्य उदाहरण के रूप में φ(1) = 1 क्योंकि n = 1 के लिए केवल पूर्णांक है 1 से n तक की सीमा 1 ही है, और gcd(1, 1) = 1 है।

यूलर का कुल फलन एक गुणक फलन है | जिसका अर्थ है कि यदि दो संख्याएँ m और n अपेक्षाकृत अभाज्य हैं, तो φ(mn) = φ(m)φ(n). यह फलन पूर्णांक मॉड्यूलो n (रिंग $\mathbb {Z} /n\mathbb {Z}$) की इकाइयों के समूह का क्रम देता है। इसका उपयोग आरएसए एन्क्रिप्शन प्रणाली को परिभाषित करने के लिए भी किया जाता है।

इतिहास, शब्दावली और अंकन

लियोनहार्ड यूलर ने 1763 में कार्य का प्रारंभ किया था। चूँकि, उन्होंने उस समय इसे निरूपित करने के लिए किसी विशिष्ट प्रतीक का चयन नहीं किया था। यूलर ने 1784 के प्रकाशन में, ग्रीक अक्षर को चुनते हुए, कार्य का और अध्ययन किया था और π इसे निरूपित करने के लिए: उन्होंने लिखा πD से कम संख्याओं की भीड़ के लिए D, और जिसके साथ कोई उभयनिष्ठ भाजक नहीं है। यह परिभाषा वर्तमान परिभाषा से टोटिएंट फलन D = 1 के लिए भिन्न होती है | किन्तु अन्यथा वही है। अब-मानक संकेतन φ(A) गॉस के 1801 ग्रंथ अरिथमेटिक डिक्विजिशन से आता है | चूँकि गॉस ने तर्क के चारों ओर कोष्ठक का उपयोग नहीं किया और φA लिखा था | इस प्रकार, इसे अधिकांशतः यूलर का φ फलन या केवल φ फलन कहा जाता है।

जेम्स जोसेफ सिल्वेस्टर ने 1879 में, इस कार्य के लिए टोटिएंट शब्द निर्मित किया था |, इसलिए इसे यूलर के टोटिएंट फलन, यूलर टोटिएंट या यूलर के टोटिएंट के रूप में भी जाना जाता है। जॉर्डन का टोटिएंट फलन यूलर का सामान्यीकरण है।

कोटिटेंट n कों n − φ(n) से परिभाषित किया जाता है | यह इससे कम या इसके समान धनात्मक पूर्णांकों की संख्या n की गणना करता है | जिसमें कम से कम अभाज्य संख्या n उभयनिष्ठ हो |

यूलर के टोटिएंट फलन की गणना

φ(n) की गणना के लिए कई सूत्र हैं |

यूलर का उत्पाद सूत्र

य़ह कहता है

$\varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right),$

जहां गुणनफल विभाजित होने वाली अलग-अलग अभाज्य संख्याओं n के ऊपर है | (संकेतन के लिए, अंकगणितीय फलन संकेतन देखें।) |

समतुल्य सूत्रीकरण है |

$$\varphi (n)=p_{1}^{k_{1}-1}(p_{1}{-}1)\,p_{2}^{k_{2}-1}(p_{2}{-}1)\cdots p_{r}^{k_{r}-1}(p_{r}{-}1),$$

जहाँ $n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}$ के लिए $n$ (अर्थात, $p_{1},p_{2},\ldots ,p_{r}$ विशिष्ट अभाज्य संख्याएँ हैं।) का प्रमुख गुणनखंड है

इन सूत्रों का प्रमाण दो महत्वपूर्ण तथ्यों पर निर्भर करता है।

φ एक गुणक फलन है

इसका अर्थ है कि यदि gcd(m, n) = 1, तो φ(m) φ(n) = φ(mn)। उपपत्ति की रूपरेखा है | मान लीजिए A, B, C धनात्मक पूर्णांकों के समुच्चय हैं | जो क्रमशः m, n, mn के सहअभाज्य और उससे कम हैं,| जिससे |A| = φ(m), आदि फिर चीनी शेष प्रमेय द्वारा A × B और C के बीच एक आपत्ति है।

प्रमुख शक्ति तर्क के लिए φ का मान

यदि p अभाज्य है और k ≥ 1 है, तो

$\varphi \left(p^{k}\right)=p^{k}-p^{k-1}=p^{k-1}(p-1)=p^{k}\left(1-{\tfrac {1}{p}}\right).$

उपपत्ति: चूँकि p एक अभाज्य संख्या है | gcd(p^k, m) के केवल संभावित मान 1, p, p², ..., p^k हैं, और gcd(p^k, m) > 1 होने की एकमात्र विधि है | यदि m p का गुणज है जो m ∈ {p, 2p, 3p, ..., p^{k − 1}p = p^k} है और p^{k − 1} ऐसे गुणज हैं | जो p^k से अधिक नहीं हैं। इसलिए अन्य p^k − p^{k − 1} संख्याएँ सभी p^k से अपेक्षाकृत प्रमुख हैं।

यूलर के उत्पाद सूत्र का प्रमाण

अंकगणित का मौलिक प्रमेय कहता है कि यदि n > 1 अनूठी अभिव्यक्ति है | $n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}},$ जहाँ p₁ < p₂ < ... < p_r अभाज्य संख्याएँ हैं और प्रत्येक k_i ≥ 1. (स्थिति n = 1 खाली गुणनफल से मेल खाता है।) के गुणात्मक गुण का बार-बार उपयोग करना φ और के लिए सूत्र φ(p^k) देता है |

$\begin{array}{rcl}\mathrm{\phi <!--\; \phi \; -->}(n)& =& \mathrm{\phi <!--\; \phi \; -->}(p_1^{k_1})\mathrm{\phi <!--\; \phi \; -->}(p_2^{k_2})\cdots <!--\; \cdots \; -->\mathrm{\phi <!--\; \phi \; -->}(p_r^{k_r})\\ & =& p_1^{k_1-<!--\; -\; -->1}(p_1-<!--\; -\; -->1)p_2^{k_{}}\end{array}$