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

"φ(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: Euler's theorem

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

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

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

यह Lagrange के प्रमेय (समूह सिद्धांत) | Lagrange के प्रमेय और इस तथ्य से आता है φ(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: Menon's identity

}

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 ,$

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

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

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

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

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

Main article: Perfect totient number

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

अनुप्रयोग

साइक्लोटॉमी

Main article: Constructible polygon

डिसक्विजिशन अरिथमेटिका के अंतिम खंड में गॉस साबित करता है कि नियमित 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: Prime number theorem § Prime number theorem for arithmetic progressions

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

Main article: RSA (algorithm)

आरएसए प्रणाली की स्थापना में बड़ी अभाज्य संख्याओं को चुनना सम्मिलित है 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