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

"φ(n)" redirects here. For other uses, see Phi.

Not to be confused with Euler function.

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

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

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

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

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

लियोनहार्ड यूलर ने 1763 में समारोह की शुरुआत की। हालाँकि, उन्होंने उस समय इसे निरूपित करने के लिए किसी विशिष्ट प्रतीक का चयन नहीं किया। 1784 के एक प्रकाशन में, यूलर ने ग्रीक अक्षर को चुनते हुए, कार्य का और अध्ययन किया π इसे निरूपित करने के लिए: उन्होंने लिखा πD से कम संख्याओं की भीड़ के लिए D, और जिसके साथ कोई उभयनिष्ठ भाजक नहीं है। यह परिभाषा वर्तमान परिभाषा से totient फ़ंक्शन के लिए भिन्न होती है 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}$ विशिष्ट अभाज्य संख्याएँ हैं।

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

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

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

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

अगर 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 ठीक से उत्पन्न होते हैं φ(d) घटक C_n, सूत्र इस प्रकार है। समतुल्य रूप से, सूत्र एकता के मूल पर लागू समान तर्क द्वारा प्राप्त किया जा सकता है#एकता के nवें मूल का समूह|गुणक समूह का एकता nएकता की जड़ और एकता की आदिम जड़|आदिम {{mvar|d}एकता की वें जड़ें।

सूत्र को प्राथमिक अंकगणित से भी प्राप्त किया जा सकता है। उदाहरण के लिए, चलो 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) प्रत्येक के लिए d 20 को विभाजित करना। समान तर्क किसी भी n के लिए लागू होता है।

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

$\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 \prod _{p\mid n}(1-{\frac {1}{p}})}$ पाने के ${\textstyle \sum _{d\mid n}{\frac {\mu (d)}{d}}.}$ एक उदाहरण:

$${\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. निजी कुंजी का स्वामी गुणनखंडन को जानता है, क्योंकि RSA निजी कुंजी को चुनकर बनाया जाता है 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)

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

संख्या होने पर RSA सिस्टम की सुरक्षा से समझौता किया जाएगा 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 Phi Function and the Chinese Remainder Theorem — proof that φ(n) is multiplicative
• Euler's totient 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 Phi Function