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

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

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

के पहले हजार मान φ(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}$) की इकाइयों के समूह का क्रम देता है। इसका उपयोग आरएसए एन्क्रिप्शन प्रणाली को परिभाषित करने के लिए भी किया जाता है।

अर्नोल्ड वाल्फिज़ के कारण, इसका प्रमाण इवान मटेवेविच विनोग्रादोव के कारण घातीय रकम पर अनुमानों का शोषण करता है|I. एम. विनोग्रादोव और एन. एम. कोरोबोव। वैन डेर कॉर्पुट और विनोग्रादोव के विधियों के संयोजन से, H.-Q. लियू

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

लियोनहार्ड यूलर ने 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}\varphi (n)&=&\varphi (p_{1}^{k_{1}})\,\varphi (p_{2}^{k_{2}})\cdots \varphi (p_{r}^{k_{r}})\\[.1em]&=&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)\\[.1em]&=&p_{1}^{k_{1}}\left(1-{\frac {1}{p_{1}}}\right)p_{2}^{k_{2}}\left(1-{\frac {1}{p_{2}}}\right)\cdots p_{r}^{k_{r}}\left(1-{\frac {1}{p_{r}}}\right)\\[.1em]&=&p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right)\\[.1em]&=&n\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right).\end{array}}$

यह यूलर के उत्पाद सूत्र के दोनों संस्करण देता है।

वैकल्पिक प्रमाण जिसके लिए गुणात्मक गुण की आवश्यकता नहीं होती है | किन्तु समुच्चय पर प्रयुक्त समावेशन-बहिष्करण सिद्धांत का उपयोग करता है | प्रधान विभाजकों $\{1,2,\ldots ,n\}$ द्वारा विभाज्य पूर्णांकों के समुच्चय को छोड़कर बहिष्करण सिद्धांत का उपयोग करता है।

उदाहरण

$\varphi (20)=\varphi (2^{2}5)=20\,(1-{\tfrac {1}{2}})\,(1-{\tfrac {1}{5}})=20\cdot {\tfrac {1}{2}}\cdot {\tfrac {4}{5}}=8.$

शब्दों में: 20 के विशिष्ट अभाज्य गुणनखंड 2 और 5 हैं; 1 से 20 तक के बीस पूर्णांकों में से आधे 2 से विभाज्य हैं, दस को छोड़कर; उनमें से पाँचवाँ भाग 5 से विभाज्य है, जिससे आठ संख्याएँ 20 तक सहअभाज्य हो जाती हैं; ये हैं: 1, 3, 7, 9, 11, 13, 17, 19 है।

वैकल्पिक सूत्र केवल पूर्णांकों का उपयोग करता है:

$$\varphi (20)=\varphi (2^{2}5^{1})=2^{2-1}(2{-}1)\,5^{1-1}(5{-}1)=2\cdot 1\cdot 1\cdot 4=8.$$

फूरियर रूपांतरण

टोटिएंट महानतम सामान्य भाजक का असतत फूरियर रूपांतरण है | जिसका मूल्यांकन 1 पर किया जाता है।

माना

${\mathcal {F}}\{\mathbf {x} \}[m]=\sum \limits _{k=1}^{n}x_{k}\cdot e^{{-2\pi i}{\frac {mk}{n}}}$

जहाँ x_k = gcd(k,n) के लिए k ∈ {1, ..., n}. तब

$\varphi (n)={\mathcal {F}}\{\mathbf {x} \}[1]=\sum \limits _{k=1}^{n}\gcd(k,n)e^{-2\pi i{\frac {k}{n}}}.$

इस सूत्र का वास्तविक भाग है |

$\varphi (n)=\sum \limits _{k=1}^{n}\gcd(k,n)\cos {\tfrac {2\pi k}{n}}.$

उदाहरण के लिए, का उपयोग करना $\cos {\tfrac {\pi }{5}}={\tfrac {{\sqrt {5}}+1}{4}}$ और $\cos {\tfrac {2\pi }{5}}={\tfrac {{\sqrt {5}}-1}{4}}$:

$${\begin{array}{rcl}\varphi (10)&=&\gcd(1,10)\cos {\tfrac {2\pi }{10}}+\gcd(2,10)\cos {\tfrac {4\pi }{10}}+\gcd(3,10)\cos {\tfrac {6\pi }{10}}+\cdots +\gcd(10,10)\cos {\tfrac {20\pi }{10}}\\&=&1\cdot ({\tfrac {{\sqrt {5}}+1}{4}})+2\cdot ({\tfrac {{\sqrt {5}}-1}{4}})+1\cdot (-{\tfrac {{\sqrt {5}}-1}{4}})+2\cdot (-{\tfrac {{\sqrt {5}}+1}{4}})+5\cdot (-1)\\&&+\ 2\cdot (-{\tfrac {{\sqrt {5}}+1}{4}})+1\cdot (-{\tfrac {{\sqrt {5}}-1}{4}})+2\cdot ({\tfrac {{\sqrt {5}}-1}{4}})+1\cdot ({\tfrac {{\sqrt {5}}+1}{4}})+10\cdot (1)\\&=&4.\end{array}}$$

यूलर उत्पाद और विभाजक योग सूत्र के विपरीत, इसके कारकों n को जानने की आवश्यकता नहीं है | चूँकि, इसमें सबसे बड़े सामान्य विभाजक की गणना n सम्मिलित है और प्रत्येक धनात्मक पूर्णांक से कम n, जो वैसे भी गुणनखंड प्रदान करने के लिए पर्याप्त है।

भाजक योग

गॉस द्वारा स्थापित गुण , वह

$\sum _{d\mid n}\varphi (d)=n,$

जहां योग सभी सकारात्मक विभाजकों d का n से अधिक है | कई तरह से सिद्ध किया जा सकता है। (अंकगणितीय फलन नोटेशन सम्मेलनों के लिए अंकगणित देखें।)

प्रमाण यह ध्यान रखना है φ(d) चक्रीय समूह C_d के संभावित जनरेटर की संख्या के समान भी है | विशेष रूप से, यदि C_d = ⟨g⟩ साथ g^d = 1, तब g^k प्रत्येक k कोप्राइम से d के लिए जनरेटर है | चूंकि C_n का प्रत्येक तत्व चक्रीय उपसमूह उत्पन्न करता है और सभी उपसमूह C_d ⊆ C_n ठीक C_n से φ(d) उत्पन्न होते हैं | सूत्र इस प्रकार है। समतुल्य रूप से, सूत्र एकता के nवें मूल पर प्रयुक्त समान तर्क द्वारा प्राप्त किया जा सकता है |

सूत्र को प्राथमिक अंकगणित से भी प्राप्त किया जा सकता है। उदाहरण के लिए, माना n = 20 और हर 20 के साथ 1 तक के सकारात्मक अंशों पर विचार करें |

${\tfrac {1}{20}},\,{\tfrac {2}{20}},\,{\tfrac {3}{20}},\,{\tfrac {4}{20}},\,{\tfrac {5}{20}},\,{\tfrac {6}{20}},\,{\tfrac {7}{20}},\,{\tfrac {8}{20}},\,{\tfrac {9}{20}},\,{\tfrac {10}{20}},\,{\tfrac {11}{20}},\,{\tfrac {12}{20}},\,{\tfrac {13}{20}},\,{\tfrac {14}{20}},\,{\tfrac {15}{20}},\,{\tfrac {16}{20}},\,{\tfrac {17}{20}},\,{\tfrac {18}{20}},\,{\tfrac {19}{20}},\,{\tfrac {20}{20}}.$

उन्हें निम्नतम शब्दों में रखें:

${\tfrac {1}{20}},\,{\tfrac {1}{10}},\,{\tfrac {3}{20}},\,{\tfrac {1}{5}},\,{\tfrac {1}{4}},\,{\tfrac {3}{10}},\,{\tfrac {7}{20}},\,{\tfrac {2}{5}},\,{\tfrac {9}{20}},\,{\tfrac {1}{2}},\,{\tfrac {11}{20}},\,{\tfrac {3}{5}},\,{\tfrac {13}{20}},\,{\tfrac {7}{10}},\,{\tfrac {3}{4}},\,{\tfrac {4}{5}},\,{\tfrac {17}{20}},\,{\tfrac {9}{10}},\,{\tfrac {19}{20}},\,{\tfrac {1}{1}}$

ये बीस अंश सभी धनात्मक k/d ≤ 1 हैं | जिसके प्रत्येक भाजक हैं | d = 1, 2, 4, 5, 10, 20. प्रत्येक के रूप में 20 वाले अंश वे हैं जिनके अंश अपेक्षाकृत 20 तक हैं, अर्थात् 1/20, 3/20, 7/20, 9/20, 11/20, 13/20, 17/20, 19/20; परिभाषा के अनुसार φ(20) भिन्न है। इसी प्रकार,प्रत्येक 10 के साथ φ(10) भाजक अंश है और प्रत्येक भाजक 5 के साथ φ(5) अंश है | आदि इस प्रकार बीस अंशों का समुच्चय d 20 के लिए आकार के सबसमुच्चय में विभाजित होता है |

विभाजक योग सूत्र पर प्रयुक्त मोबियस उलटा देता है

$\varphi (n)=\sum _{d\mid n}\mu \left(d\right)\cdot {\frac {n}{d}}=n\sum _{d\mid n}{\frac {\mu (d)}{d}},$

जहाँ μ मोबियस फलन है, जिसके द्वारा परिभाषित गुणक फलन $\mu (p)=-1$ और $\mu (p^{k})=0$ है | प्रत्येक प्रधान के लिए p और k ≥ 2.के लिए परिभाषित है। यह सूत्र ${\textstyle \sum _{d\mid n}{\frac {\mu (d)}{d}}.}$ उत्पाद सूत्र से गुणा करके भी ${\textstyle \prod _{p\mid n}(1-{\frac {1}{p}})}$ प्राप्त किया जा सकता है | उदाहरण:

$${\begin{aligned}\varphi (20)&=\mu (1)\cdot 20+\mu (2)\cdot 10+\mu (4)\cdot 5+\mu (5)\cdot 4+\mu (10)\cdot 2+\mu (20)\cdot 1\\[.5em]&=1\cdot 20-1\cdot 10+0\cdot 5-1\cdot 4+1\cdot 2+0\cdot 1=8.\end{aligned}}$$

कुछ मूल्य

पहले 100 मान (sequence A000010 in the OEIS) को नीचे तालिका और ग्राफ़ में दिखाया गया है:

पहले 100 मानों का ग्राफ़

:{| class="wikitable" style="text-align: right"

|+φ(n) for 1 ≤ n ≤ 100 ! + ! 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 |- ! 0 | 1 || 1 || 2 || 2 || 4 || 2 || 6 || 4 || 6 || 4 |- ! 10 | 10 || 4 || 12 || 6 || 8 || 8 || 16 || 6 || 18 || 8 |- ! 20 | 12 || 10 || 22 || 8 || 20 || 12 || 18 || 12 || 28 || 8 |- ! 30 | 30 || 16 || 20 || 16 || 24 || 12 || 36 || 18 || 24 || 16 |- ! 40 | 40 || 12 || 42 || 20 || 24 || 22 || 46 || 16 || 42 || 20 |- ! 50 | 32 || 24 || 52 || 18 || 40 || 24 || 36 || 28 || 58 || 16 |- ! 60 | 60 || 30 || 36 || 32 || 48 || 20 || 66 || 32 || 44 || 24 |- ! 70 | 70 || 24 || 72 || 36 || 40 || 36 || 60 || 24 || 78 || 32 |- ! 80 | 54 || 40 || 82 || 24 || 64 || 42 || 56 || 40 || 88 || 24 |- ! 90 | 72 || 44 || 60 || 46 || 72 || 32 || 96 || 42 || 60 || 40 |}

शीर्ष रेखा के दाईं ओर ग्राफ़ में y = n − 1 ऊपरी सीमा है जो सभी के लिए मान्य है n के अतिरिक्त, और यदि और केवल यदि प्राप्त किया n अभाज्य संख्या है। साधारण निचली सीमा है $\varphi (n)\geq {\sqrt {n/2}}$, जो ढीला है: वास्तव में, ग्राफ की सीमा श्रेष्ठ और n/log log n सीमा हीन आनुपातिक है |

यूलर प्रमेय

Main article: यूलर प्रमेय

इसमें कहा गया है कि यदि a और n तब अपेक्षाकृत प्रमुख हैं |

$a^{\varphi (n)}\equiv 1\mod n.$

विशेष स्थिति जहां n प्राइम है जिसे फर्मेट की छोटी प्रमेय के रूप में जाना जाता है।

यह लैग्रेंज के प्रमेय (समूह सिद्धांत) और φ(n) इस तथ्य से आता है | पूर्णांक मॉड्यूलो के गुणक समूह का क्रम (समूह सिद्धांत) n है |

आरएसए (एल्गोरिदम) इस प्रमेय पर आधारित है: इसका तात्पर्य है कि फलन का उलटा कार्य a ↦ a^e mod n, जहाँ e (सार्वजनिक) एन्क्रिप्शन प्रतिपादक है, कार्य है b ↦ b^d mod n, जहाँ d, (निजी) डिक्रिप्शन एक्सपोनेंट, का गुणात्मक व्युत्क्रम है | e मापांक φ(n). कंप्यूटिंग की कठिनाई φ(n) के गुणनखंड को जाने बिना n इस प्रकार कंप्यूटिंग की कठिनाई d है | इसे आरएसए समस्या के रूप में जाना जाता है जिसे फैक्टरिंग n द्वारा हल किया जा सकता है | निजी कुंजी का स्वामी गुणनखंडन को जानता है | क्योंकि आरएसए निजी कुंजी को चुनकर बनाया जाता है | n दो (यादृच्छिक रूप से चुने गए) बड़े प्राइम्स के उत्पाद के रूप में p और q. केवल n सार्वजनिक रूप से प्रकट किया गया है, और पूर्णांक गुणनखंडन को देखते हुए हमारे पास गारंटी है कि किसी और को गुणनखंडन के बारे में पता नहीं है।

अन्य सूत्र

$a\mid b\implies \varphi (a)\mid \varphi (b)$

$m\mid \varphi (a^{m}-1)$

$\varphi (mn)=\varphi (m)\varphi (n)\cdot {\frac {d}{\varphi (d)}}\quad {\text{where }}d=\operatorname {gcd} (m,n)$

विशेष रूप से:

• $\varphi (2m)={\begin{cases}2\varphi (m)&{\text{ if }}m{\text{ is even}}\\\varphi (m)&{\text{ if }}m{\text{ is odd}}\end{cases}}$
• $\varphi \left(n^{m}\right)=n^{m-1}\varphi (n)$

$\varphi (\operatorname {lcm} (m,n))\cdot \varphi (\operatorname {gcd} (m,n))=\varphi (m)\cdot \varphi (n)$

इसकी तुलना सूत्र से करें ${\textstyle \operatorname {lcm} (m,n)\cdot \operatorname {gcd} (m,n)=m\cdot n}$ (लघुतम समापवर्त्य देखें)।

φ(n) के लिए भी है n ≥ 3.

इसके अतिरिक्त, यदि n है r विशिष्ट विषम अभाज्य कारक, {{math|2^r | φ(n)}

किसी के लिए a > 1 और n > 6 ऐसा है कि 4 ∤ n वहाँ उपस्थित है l ≥ 2n ऐसा है कि l | φ(aⁿ − 1).

${\frac {\varphi (n)}{n}}={\frac {\varphi (\operatorname {rad} (n))}{\operatorname {rad} (n)}}$

जहाँ rad(n) पूर्णांक का मूलांक है | n (विभाजन करने वाले सभी विशिष्ट अभाज्य संख्याओं का गुणनफल n).

$\sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}$ 

$\sum _{1\leq k\leq n \atop (k,n)=1}\!\!k={\tfrac {1}{2}}n\varphi (n)\quad {\text{for }}n>1$

$\sum _{k=1}^{n}\varphi (k)={\tfrac {1}{2}}\left(1+\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)$ ( में उद्धृत करना)

$\sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor ={\frac {6}{\pi ^{2}}}n+O\left((\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)$ 

$\sum _{k=1}^{n}{\frac {k}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}n-{\frac {\log n}{2}}+O\left((\log n)^{\frac {2}{3}}\right)$ 

$\sum _{k=1}^{n}{\frac {1}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}\left(\log n+\gamma -\sum _{p{\text{ prime}}}{\frac {\log p}{p^{2}-p+1}}\right)+O\left({\frac {(\log n)^{\frac {2}{3}}}{n}}\right)$ 

(जहाँ γ यूलर-माशेरोनी स्थिरांक है)।

$\sum _{\stackrel {1\leq k\leq n}{\operatorname {gcd} (k,m)=1}}\!\!\!\!1=n{\frac {\varphi (m)}{m}}+O\left(2^{\omega (m)}\right)$

जहाँ m > 1 सकारात्मक पूर्णांक है और ω(m) के विशिष्ट प्रमुख कारकों की संख्या m है |

मेनन की पहचान

Main article: मेनन की पहचान

1965 में पी. केसव मेनन ने सिद्ध किया है |

: : : : : : : : : : : : : : : : : : : : : : : :$\sum _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\!\!\!\!\gcd(k-1,n)=\varphi (n)d(n),$

जहाँ d(n) = σ₀(n) के विभाजकों की संख्या n है |

कार्य उत्पन्न करना

डिरिचलेट श्रृंखला के लिए φ(n) को रीमैन जीटा फलन के रूप में लिखा जा सकता है |

$\sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}$

जहां बाईं ओर $\Re (s)>2$ के लिए अभिसरण होता है .

लैम्बर्ट श्रृंखला जनरेटिंग फलन है

$\sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}={\frac {q}{(1-q)^{2}}}$

जो |q| < 1 के लिए अभिसरण करता है .

ये दोनों प्रारंभिक श्रृंखला जोड़तोड़ और φ(n) के लिए सूत्रों द्वारा सिद्ध होते हैं |

विकास दर

हार्डी एंड राइट के शब्दों में,φ(n) का क्रम हमेशा 'लगभग' n होता है | पहला

$\lim \sup {\frac {\varphi (n)}{n}}=1,$

किन्तु जैसे n सभी δ > 0 के लिए अनंत तक जाता है |

${\frac {\varphi (n)}{n^{1-\delta }}}\rightarrow \infty .$

इन दोनों सूत्रों को φ(n) और भाजक फलन σ(n). सूत्र से थोड़ा अधिक प्रयोग करके सिद्ध किया जा सकता है |

वास्तव में, दूसरे सूत्र के प्रमाण के समय, असमानता होती है |

${\frac {6}{\pi ^{2}}}<{\frac {\varphi (n)\sigma (n)}{n^{2}}}<1,$

सही है n > 1,के लिए सिद्ध होता है।

हमारे पास भी है

$\lim \inf {\frac {\varphi (n)}{n}}\log \log n=e^{-\gamma }.$

यहाँ γ यूलर-मास्चेरोनी स्थिरांक है | यूलर स्थिरांक, γ = 0.577215665..., इसलिए e^γ = 1.7810724... और e^−γ = 0.56145948....

इसे सिद्ध करने के लिए अभाज्य संख्या प्रमेय की आवश्यकता नहीं है। तब से log log n अनंत तक जाता है, यह सूत्र बताता है

$\lim \inf {\frac {\varphi (n)}{n}}=0.$

वास्तव में, अधिक सत्य है।

$\varphi (n)>{\frac {n}{e^{\gamma }\;\log \log n+{\frac {3}{\log \log n}}}}\quad {\text{for }}n>2$

और

$\varphi (n)<{\frac {n}{e^{\gamma }\log \log n}}\quad {\text{for infinitely many }}n.$

दूसरी असमानता जीन लुइस निकोलस द्वारा प्रदर्शित की गई थी। रिबेनबोइम कहते हैं कि प्रमाण की विधि रोचक है, इसमें असमानता को पहले इस धारणा के अनुसार दिखाया गया है कि रीमैन परिकल्पना सत्य है, दूसरी विपरीत धारणा के अनुसार ये भी सही है।

औसत आदेश के लिए, हमारे पास है |

$\varphi (1)+\varphi (2)+\cdots +\varphi (n)={\frac {3n^{2}}{\pi ^{2}}}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)\quad {\text{as }}n\rightarrow \infty ,$

अर्नोल्ड वाल्फिज़ के कारण, इसका प्रमाण इवान मटेवेविच विनोग्रादोव के कारण घातीय रकम पर अनुमानों का शोषण करता है | एम. विनोग्रादोव और एन. एम. कोरोबोव है।

वैन डेर कॉर्पुट और विनोग्रादोव के विधियों के संयोजन से, H.-Q. लियू (ऑन यूलर फलन। प्रोक। रॉय। सोक। एडिनबर्ग सेक्ट। ए 146 (2016), नंबर 4, 769-775) त्रुटि शब्द में सुधार किया है |

$O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {1}{3}}\right)$

(यह वर्तमान में इस प्रकार का सबसे अच्छा ज्ञात अनुमान है)। बिग ओ नोटेशन बड़ा O ऐसी मात्रा के लिए खड़ा है जो निरंतर समय के कार्य n से बंधी है कोष्ठक के अंदर (जो की n² तुलना में छोटा है).

इस परिणाम का उपयोग सिद्ध करने के लिए किया जा सकता है | यादृच्छिक रूप से चुनी गई दो संख्याओं के अपेक्षाकृत 6/π² अभाज्य होने की प्रायिकता है |

लगातार मूल्यों का अनुपात

1950 में सोमयाजुलु सिद्ध हुआ |

${\begin{aligned}\lim \inf {\frac {\varphi (n+1)}{\varphi (n)}}&=0\quad {\text{and}}\\[5px]\lim \sup {\frac {\varphi (n+1)}{\varphi (n)}}&=\infty .\end{aligned}}$

1954 में एंड्रयू शिंजेल और वाक्लाव सिएरपिन्स्की ने इसे सिद्ध करते हुए इसे शक्तिशाली किया |

$\left\{{\frac {\varphi (n+1)}{\varphi (n)}},\;\;n=1,2,\ldots \right\}$

वह समुच्चय धनात्मक वास्तविक संख्याओं में सघन समुच्चय है। वे सिद्ध भी हुए है |

$\left\{{\frac {\varphi (n)}{n}},\;\;n=1,2,\ldots \right\}$

वह समुच्चय अंतराल (0,1) में सघन है।

कुल संख्या

टोटिएंट नंबर यूलर के टोटिएंट फलन का मान है | अर्थात, a m जिसके लिए कम से कम n है | जिसके लिए φ(n) = m. कुल संख्या की संयोजकता या बहुलता m इस समीकरण के समाधान की संख्या है। नॉनटोटिएंट प्राकृतिक संख्या है जो टोटिएंट संख्या नहीं है। 1 से अधिक प्रत्येक विषम पूर्णांक तुच्छ रूप से गैर-परमाणु है। यहाँ अपरिमित रूप से बहुत से अचिंतक भी हैं | और वास्तव में प्रत्येक धनात्मक पूर्णांक का गुणज होता है जो सम अचिंतक होता है।

दी गई सीमा तक कुल संख्याओं की संख्या x है |

${\frac {x}{\log x}}e^{{\big (}C+o(1){\big )}(\log \log \log x)^{2}}$

स्थिर के लिए C = 0.8178146.... है |

यदि बहुलता के अनुसार गिना जाता है, तो दी गई सीमा तक कुल संख्याओं की संख्या x है

${\Big \vert }\{n:\varphi (n)\leq x\}{\Big \vert }={\frac {\zeta (2)\zeta (3)}{\zeta (6)}}\cdot x+R(x)$

जहां त्रुटि शब्द R अधिक से अधिक क्रम में x/(log x)^k है | किसी भी सकारात्मक k के लिए . यह ज्ञात है कि की बहुलता m से अधिक है m^δ असीम रूप से अधिकांशतः किसी के लिए δ < 0.55655. है |

फोर्ड की प्रमेय

फोर्ड (1999) ने सिद्ध किया कि प्रत्येक पूर्णांक k ≥ 2 के लिए बहुलता k का एक कुल संख्या m है | अर्थात, जिसके लिए समीकरण φ(n) = m का बिल्कुल k समाधान है | यह परिणाम पहले वैक्लाव सिएरपिन्स्की द्वारा अनुमानित किया गया था,| और इसे शिंजेल की परिकल्पना एच के परिणाम के रूप में प्राप्त किया गया था। वास्तव में, प्रत्येक बहुलता जो घटित होती है, अनंत बार होती है।

चूँकि, कोई संख्या नहीं m बहुलता से जाना जाता है | k = 1. कारमाइकल का संपूर्ण कार्य अनुमान यह कथन है कि ऐसा कोई m नहीं है |.

पूर्ण सम संख्याएं

Main article: पूर्ण सम संख्याएं

पूर्ण कुल संख्या एक पूर्णांक है जो इसके पुनरावृत्त कुलों के योग के समान है। अर्थात्, हम टोटिएंट फलन को संख्या n पर प्रयुक्त करते हैं, इसे परिणामी टोटिएंट पर फिर से प्रयुक्त करते हैं, और इसी तरह, जब तक कि संख्या 1 तक नहीं पहुंच जाती है, और संख्याओं के परिणामी क्रम को साथ जोड़ देते हैं; यदि योग n के समान है, तो n पूर्ण पूर्ण संख्या है।

अनुप्रयोग

साइक्लोटॉमी

Main article: रचनात्मक बहुभुज

डिसक्विजिशन अरिथमेटिका के अंतिम खंड में गॉस सिद्ध करता है | कि नियमित n-गॉन का निर्माण स्ट्रेटेज और कंपास से किया जा सकता है | यदि φ(n) 2 की शक्ति है। यदि n विषम अभाज्य संख्या की शक्ति है,| टोटिएंट के लिए सूत्र कहता है कि इसका टोटिएंट केवल दो की शक्ति हो सकता है | n पहली शक्ति है और n − 1 2 की शक्ति है। वे अभाज्य संख्याएँ जो 2 की शक्ति से अधिक होती हैं,| फर्मेट प्राइम कहलाती हैं, और केवल पाँच ज्ञात हैं: 3, 5, 17, 257, और 65537 है। फर्मेट और गॉस इनके बारे में जानते थे। कोई भी यह सिद्ध करने में सक्षम नहीं है कि क्या और भी हैं।

इस प्रकार, नियमित n-गॉन का स्ट्रेटएज-एंड-कम्पास निर्माण होता है | यदि n विशिष्ट फर्मेट प्राइम्स और 2 की किसी भी शक्ति का उत्पाद है। पहले कुछ ऐसे n हैं |

2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40,... (sequence A003401 in the OEIS).

अंकगणितीय प्रगति के लिए अभाज्य संख्या प्रमेय

Main article: अभाज्य संख्या प्रमेय §  अंकगणितीय प्रगति के लिए अभाज्य संख्या प्रमेय

आरएसए क्रिप्टोप्रणाली

Main article: आरएसए (एल्गोरिदम)

आरएसए प्रणाली की स्थापना में बड़ी अभाज्य संख्याओं को चुनना सम्मिलित है p और q, कंप्यूटिंग n = pq और k = φ(n), और दो संख्याएँ ढूँढना e और d ऐसा है कि ed ≡ 1 (mod k). संख्या n और e (एन्क्रिप्शन कुंजी ) जनता के लिए जारी की जाती हैं, और d (डिक्रिप्शन कुंजी ) को निजी रखा जाता है।

संदेश, पूर्णांक द्वारा दर्शाया गया m, जहाँ 0 < m < n, कंप्यूटिंग द्वारा एन्क्रिप्ट किया गया है S = m^e (mod n).

इसे कंप्यूटिंग द्वारा डिक्रिप्ट किया जाता है t = S^d (mod n). यूलर के प्रमेय का उपयोग यह दिखाने के लिए किया जा सकता है कि यदि 0 < t < n, तब t = m.

संख्या होने पर आरएसए प्रणाली की सुरक्षा से समझौता किया जाएगा n को कुशलता से फैक्टर किया जा सकता है या यदि φ(n) बिना फैक्टरिंग के कुशलता से गणना की जा सकती है n.

अनसुलझी समस्याएं

लेहमर का अनुमान

Main article: Lehmer's totient problem

यदि p प्रधान है, तो φ(p) = p − 1. 1932 में डी. एच. लेहमर ने पूछा कि क्या कोई मिश्रित संख्याएँ हैं n ऐसा है कि φ(n) विभाजित करता है n − 1. कोई नहीं जानता। 1933 में उन्होंने सिद्ध कर दिया कि यदि कोई ऐसा है n उपस्थित है, यह विषम, वर्ग रहित और कम से कम सात अभाज्य संख्याओं से विभाज्य होना चाहिए (अर्थात ω(n) ≥ 7). 1980 में कोहेन और हागिस ने यह सिद्ध कर दिया n > 10²⁰ ओर वो ω(n) ≥ 14. आगे, हैगिस ने दिखाया कि यदि 3 विभाजित होता है n तब n > 10^1937042 और ω(n) ≥ 298848.

कारमाइकल का अनुमान

Main article: Carmichael's totient function conjecture

यह बताता है कि कोई संख्या नहीं है n गुण के साथ कि अन्य सभी नंबरों के लिए m, m ≠ n, φ(m) ≠ φ(n). ऊपर #Ford's theorem|Ford's theorem देखें।

जैसा कि मुख्य लेख में कहा गया है, यदि इस अनुमान के लिए एकल प्रति उदाहरण है, तो असीम रूप से कई प्रति उदाहरण होने चाहिए, और सबसे छोटे वाले के पास आधार 10 में कम से कम दस अरब अंक हैं।

रीमैन परिकल्पना

रीमैन परिकल्पना सच है यदि और केवल यदि असमानता

${\frac {n}{\varphi (n)}}<e^{\gamma }\log \log n+{\frac {e^{\gamma }(4+\gamma -\log 4\pi )}{\sqrt {\log n}}}$

सभी के लिए सत्य है n ≥ p₁₂₀₅₆₉# जहाँ γ यूलर स्थिरांक है और p₁₂₀₅₆₉# प्राथमिक है 120569 प्राइम्स।

यह भी देखें

• कारमाइकल फलन
• डफिन-शेफ़र अनुमान
• Fermat की छोटी प्रमेय#सामान्यीकरण|Fermat की छोटी प्रमेय का सामान्यीकरण
• अत्यधिक समग्र संख्या
• पूर्णांक मॉड्यूलो का गुणक समूह n|पूर्णांक मॉड्यूलो का गुणक समूह n
• मैं रामनुजन शूम
• संपूर्ण सारांश फलन
• डेडेकाइंड का साई फलन

संदर्भ

The Disquisitiones Arithmeticae has been translated from Latin into English and German. The German edition includes all of Gauss' papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.

संदर्भ to the Disquisitiones are of the form Gauss, DA, art. nnn.

• Abramowitz, M.; Stegun, I. A. (1964), Handbook of Mathematical Functions, New York: Dover Publications, ISBN 0-486-61272-4. See paragraph 24.3.2.
• Bach, Eric; Shallit, Jeffrey (1996), Algorithmic Number Theory (Vol I: Efficient Algorithms), MIT Press Series in the Foundations of Computing, Cambridge, MA: The MIT Press, ISBN 0-262-02405-5, Zbl 0873.11070
• Dickson, Leonard Eugene, "History Of The Theory Of Numbers", vol 1, chapter 5 "Euler's Function, Generalizations; Farey Series", Chelsea Publishing 1952
• Ford, Kevin (1999), "The number of solutions of φ(x) = m", Annals of Mathematics, 150 (1): 283–311, doi:10.2307/121103, ISSN 0003-486X, JSTOR 121103, MR 1715326, Zbl 0978.11053.
• Gauss, Carl Friedrich (1986), Disquisitiones Arithmeticae (Second, corrected edition), translated by Clarke, Arthur A., New York: Springer, ISBN 0-387-96254-9
• Gauss, Carl Friedrich (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae & other papers on number theory) (Second edition), translated by Maser, H., New York: Chelsea, ISBN 0-8284-0191-8
• Graham, Ronald; Knuth, Donald; Patashnik, Oren (1994), Concrete Mathematics: a foundation for computer science (2nd ed.), Reading, MA: Addison-Wesley, ISBN 0-201-55802-5, Zbl 0836.00001
• Guy, Richard K. (2004), Unsolved Problems in Number Theory, Problem Books in Mathematics (3rd ed.), New York, NY: Springer-Verlag, ISBN 0-387-20860-7, Zbl 1058.11001
• Hardy, G. H.; Wright, E. M. (1979), An Introduction to the Theory of Numbers (Fifth ed.), Oxford: Oxford University Press, ISBN 978-0-19-853171-5
• Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77-171950
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77-81766
• Ribenboim, Paulo (1996), The New Book of Prime Number Records (3rd ed.), New York: Springer, ISBN 0-387-94457-5, Zbl 0856.11001
• Sandifer, Charles (2007), The early mathematics of Leonhard Euler, MAA, ISBN 978-0-88385-559-1
• Sándor, József; Mitrinović, Dragoslav S.; Crstici, Borislav, eds. (2006), Handbook of number theory I, Dordrecht: Springer-Verlag, pp. 9–36, ISBN 1-4020-4215-9, Zbl 1151.11300
• Sándor, Jozsef; Crstici, Borislav (2004). Handbook of number theory II. Dordrecht: Kluwer Academic. pp. 179–327. ISBN 1-4020-2546-7. Zbl 1079.11001.
• Schramm, Wolfgang (2008), "The Fourier transform of functions of the greatest common divisor", Electronic Journal of Combinatorial Number Theory, A50 (8(1)).

बाहरी संबंध

• "Totient function", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Euler's φ Function and the Chinese Remainder Theorem — proof that φ(n) is multiplicative
• Euler's टोटिएंट function calculator in JavaScript — up to 20 digits
• Dineva, Rosica, The Euler Totient, the Möbius, and the Divisor Functions
• Plytage, Loomis, Polhill Summing Up The Euler φ Function