Fungsi phi Euler: Perbedaan antara revisi

← Revisi sebelumnya Revisi selanjutnya →

Konten dihapus Konten ditambahkan

Sebaris

Revisi per 26 Mei 2020 10.55

Fungsi Phi Euler φ(m) atau ⍉(m) menyatakan kardinal himpunan bilangan asli $1\leq n\leq m$ dimana fpb(m,n) = 1.

Dikemukakan oleh Leonhard Euler (L. 15 April 1707, Swiss. w. 18 September 1783, Rusia). Pada kisaran tahun 1750-an. Lalu, Notasi φ(m) atau ⍉(m) ditulis pertama kali oleh Gauss pada tahun

Contoh :

Bilangan bulat positif yang < 9 adalah 1, 2, 3, 4, 5, 6, 7, 8. Diantara bilangan-bilangan tersebut yang saling prima terhadap 9 adalah 1, 2, 4, 5, 7, 8, maka banyaknya bilangan yang saling prima terhadap 9 adalah sebanyak 6 sehingga φ(9) = 6.

Identitas :

φ(1) = 0

φ(2) = 1

φ(P) = P - 1 untuk P prima

φ(mn) = φ(m)φ(n) jika fpb(m,n)=1

φ(Pⁿ) = Pⁿ⁻¹ (P-1)

φ(P₁×P₂×...×Pₙ) = (P₁-1)(P₂-1)(P₃-1)...(Pₙ-1)

$a\mid b\implies \varphi (a)\mid \varphi (b)$
$n\mid \varphi (a^{n}-1)\quad {\text{untuk setiap }}a,n>1$
φ(m,n) = Φ(m).φ(n) .

Note the special cases

$\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)$

Compare this to the formula

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

(See least common multiple.)

$φ (n)$ is even for $n \geq 3$ . Moreover, if $n$ has $r$ distinct odd prime factors, $2 r | φ (n)$
For any $a > 1$ and $n > 6$ such that $4 ∤ n$ there exists an $l \geq 2 n$ such that $l | φ (a n - 1)$ .
${\frac {\varphi (n)}{n}}={\frac {\varphi (\operatorname {rad} (n))}{\operatorname {rad} (n)}}$

where

rad(n)

is the radical of

n

.

$\sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}$ ^[1]
$\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)$ (^[2] cited in^[3])

$\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)$ ^[2]
$\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)$ ^[4]
$\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)$ ^[4]

(where

γ

is the Euler–Mascheroni constant).

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

where

m > 1

is a positive integer and

ω (m)

is the number of distinct prime factors of

m

.^[5]

Pengembangan Fungsi Phi Euler :

^ Dineva (in external refs), prop. 1
^ ^a ^b Walfisz, Arnold (1963). Weylsche Exponentialsummen in der neueren Zahlentheorie. Mathematische Forschungsberichte (dalam bahasa German). 16. Berlin: VEB Deutscher Verlag der Wissenschaften. Zbl 0146.06003.
^ Lomadse, G., "The scientific work of Arnold Walfisz" (PDF), Acta Arithmetica, 10 (3): 227–237
^ ^a ^b Sitaramachandrarao, R. (1985). "On an error term of Landau II". Rocky Mountain J. Math. 15: 579–588.
^ Bordellès in the external links

[1] Dineva (in external refs), prop. 1

[Wal1963-2] Walfisz, Arnold (1963). Weylsche Exponentialsummen in der neueren Zahlentheorie. Mathematische Forschungsberichte (dalam bahasa German). 16. Berlin: VEB Deutscher Verlag der Wissenschaften. Zbl 0146.06003.

[3] Lomadse, G., "The scientific work of Arnold Walfisz" (PDF), Acta Arithmetica, 10 (3): 227–237

[Sita-4] Sitaramachandrarao, R. (1985). "On an error term of Landau II". Rocky Mountain J. Math. 15: 579–588.

[5] Bordellès in the external links

[1]

[2]

[3]

[4]

[5]

@@ Baris 2: / Baris 2: @@
-Dikemukakan oleh '''[[Leonhard Euler]]''' (L. 15 April 1707, [[Konfederasi Swiss Lama|Swiss.]] w. 18 September 1783, [[Kekaisaran Rusia|Rusia]]). Pada kisaran tahun 1750-an. Lalu, Notasi φ(m)  atau ⍉(m) ditulis pertama kali oleh [[Gauss]] pada tahun
+Dikemukakan oleh '''[[Leonhard Euler]]''' (L. 15 April 1707, [[Konfederasi Swiss Lama|Swiss.]] w. 18 September 1783, [[Kekaisaran Rusia|Rusia]]). Pada kisaran tahun 1750-an. Lalu, Notasi φ(m) atau ⍉(m) ditulis pertama kali oleh [[Gauss]] pada tahun
 '''Contoh :'''
@@ Baris 18: / Baris 18: @@
 φ(mn) = φ(m)φ(n) jika fpb(m,n)=1
 φ(Pⁿ) = Pⁿ⁻¹ (P-1)
 φ(P₁×P₂×...×Pₙ) = (P₁-1)(P₂-1)(P₃-1)...(Pₙ-1)
-*<math>a\mid b \implies \varphi(a)\mid\varphi(b)</math>
+* <math>a\mid b \implies \varphi(a)\mid\varphi(b)</math>
-*<math> n \mid \varphi(a^n-1) \quad \text{untuk setiap } a,n > 1</math>
+* <math> n \mid \varphi(a^n-1) \quad \text{untuk setiap } a,n > 1</math>
-*φ(m,n) = Φ(m).φ(n) .
+* φ(m,n) = Φ(m).φ(n) .
 :Note the special cases
-:*<math>\varphi(2m) = \begin{cases}
+:* <math>\varphi(2m) = \begin{cases}
 \varphi(m) &\text{ if } m \text{ is even} \\
 \varphi(m) &\text{ if } m \text{ is odd}
 \end{cases}</math>
-:*<math>\varphi\left(n^m\right) = n^{m-1}\varphi(n)</math>
+:* <math>\varphi\left(n^m\right) = n^{m-1}\varphi(n)</math>
-*<math>\varphi(\operatorname{lcm}(m,n))\cdot\varphi(\operatorname{gcd}(m,n)) = \varphi(m)\cdot\varphi(n)</math>
+* <math>\varphi(\operatorname{lcm}(m,n))\cdot\varphi(\operatorname{gcd}(m,n)) = \varphi(m)\cdot\varphi(n)</math>
 :Compare this to the formula
-:*<math>\operatorname{lcm}(m,n)\cdot \operatorname{gcd}(m,n) = m \cdot n</math>
+:* <math>\operatorname{lcm}(m,n)\cdot \operatorname{gcd}(m,n) = m \cdot n</math>
 :(See [[least common multiple]].)
-*{{math|''φ''(''n'')}} is even for {{math|''n'' ≥ 3}}. Moreover, if {{mvar|n}} has {{mvar|r}} distinct odd prime factors, {{math|2<sup>''r''</sup> {{!}} ''φ''(''n'')}}
+* {{math|''φ''(''n'')}} is even for {{math|''n'' ≥ 3}}. Moreover, if {{mvar|n}} has {{mvar|r}} distinct odd prime factors, {{math|2<sup>''r''</sup> {{!}} ''φ''(''n'')}}
 * For any {{math|''a'' > 1}} and {{math|''n'' > 6}} such that {{math|4 ∤ ''n''}} there exists an {{math|''l'' ≥ 2''n''}} such that {{math|''l'' {{!}} ''φ''(''a<sup>n</sup>'' − 1)}}.
-*<math>\frac{\varphi(n)}{n}=\frac{\varphi(\operatorname{rad}(n))}{\operatorname{rad}(n)}</math>
+* <math>\frac{\varphi(n)}{n}=\frac{\varphi(\operatorname{rad}(n))}{\operatorname{rad}(n)}</math>
 :where {{math|rad(''n'')}} is the [[radical of an integer|radical of {{mvar|n}}]].
-*<math>\sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)}</math>&nbsp;<ref>Dineva (in external refs), prop. 1</ref>
+* <math>\sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)}</math>&nbsp;<ref>Dineva (in external refs), prop. 1</ref>
-*<math>\sum_{1\le k\le n \atop (k,n)=1}\!\!k = \tfrac12 n\varphi(n) \quad \text{for }n>1</math>
+* <math>\sum_{1\le k\le n \atop (k,n)=1}\!\!k = \tfrac12 n\varphi(n) \quad \text{for }n>1</math>
-*<math>\sum_{k=1}^n\varphi(k) = \tfrac12 \left(1+ \sum_{k=1}^n \mu(k)\left\lfloor\frac{n}{k}\right\rfloor^2\right)
+* <math>\sum_{k=1}^n\varphi(k) = \tfrac12 \left(1+ \sum_{k=1}^n \mu(k)\left\lfloor\frac{n}{k}\right\rfloor^2\right)
 =\frac3{\pi^2}n^2+O\left(n(\log n)^\frac23(\log\log n)^\frac43\right)</math>&nbsp;(<ref name=Wal1963>{{cite book | zbl=0146.06003 | last=Walfisz | first=Arnold | authorlink=Arnold Walfisz | title=Weylsche Exponentialsummen in der neueren Zahlentheorie | language=German | series=Mathematische Forschungsberichte | volume=16 | location=Berlin | publisher=[[VEB Deutscher Verlag der Wissenschaften]] | year=1963 }}</ref> cited in<ref>{{citation | last = Lomadse | first = G. | title = The scientific work of Arnold Walfisz | journal = Acta Arithmetica | volume = 10 | issue = 3 | pages = 227–237 | url = http://matwbn.icm.edu.pl/ksiazki/aa/aa10/aa10111.pdf}}</ref>)
-*<math>\sum_{k=1}^n\frac{\varphi(k)}{k} = \sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor=\frac6{\pi^2}n+O\left((\log n)^\frac23(\log\log n)^\frac43\right)</math>&nbsp;<ref name=Wal1963/>
+* <math>\sum_{k=1}^n\frac{\varphi(k)}{k} = \sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor=\frac6{\pi^2}n+O\left((\log n)^\frac23(\log\log n)^\frac43\right)</math>&nbsp;<ref name=Wal1963/>
-*<math>\sum_{k=1}^n\frac{k}{\varphi(k)} = \frac{315\,\zeta(3)}{2\pi^4}n-\frac{\log n}2+O\left((\log n)^\frac23\right)</math>&nbsp;<ref name=Sita>{{cite journal|first=R. |last=Sitaramachandrarao |title=On an error term of Landau II |journal=Rocky Mountain J. Math. |volume=15 |date=1985 |pages=579–588}}</ref>
+* <math>\sum_{k=1}^n\frac{k}{\varphi(k)} = \frac{315\,\zeta(3)}{2\pi^4}n-\frac{\log n}2+O\left((\log n)^\frac23\right)</math>&nbsp;<ref name=Sita>{{cite journal|first=R. |last=Sitaramachandrarao |title=On an error term of Landau II |journal=Rocky Mountain J. Math. |volume=15 |date=1985 |pages=579–588}}</ref>
-*<math>\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)^\frac23}n\right)</math>&nbsp;<ref name=Sita />
+* <math>\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)^\frac23}n\right)</math>&nbsp;<ref name=Sita />
 :(where {{mvar|γ}} is the [[Euler–Mascheroni constant]]).
-*<math>\sum_\stackrel{1\le k\le n}{\operatorname{gcd}(k,m)=1} \!\!\!\! 1 = n \frac {\varphi(m)}{m} + O \left ( 2^{\omega(m)} \right )</math>
+* <math>\sum_\stackrel{1\le k\le n}{\operatorname{gcd}(k,m)=1} \!\!\!\! 1 = n \frac {\varphi(m)}{m} + O \left ( 2^{\omega(m)} \right )</math>
 :where {{math|''m'' > 1}} is a positive integer and {{math|''ω''(''m'')}} is the number of distinct prime factors of {{mvar|m}}.<ref>Bordellès in the [[#Pranala luar|external links]]</ref>