ฟังก์ชันโทเทียนต์ของออยเลอร์

Q: การคำนวณฟังก์ชันโทเทียนต์ของออยเลอร์

มีสูตรคำนวณอยู่หลายสูตร φ ( n ) {\displaystyle \varphi (n)} .

Q: Fourier transform

The totient is the discrete Fourier transform of the gcd , evaluated at 1. [ 17 ] Let

บทความนี้ใช้สัญลักษณ์ทางคณิตศาสตร์เชิงเทคนิคสำหรับลอการิทึม ทุกๆ กรณีของ

\log(x)

ฐานที่ไม่มีตัวห้อยควรตีความว่าเป็นลอการิทึมธรรมชาติซึ่งมักเขียนว่า

\ln(x)

หรือ

\log _{e}(x)

.

ค่า $φ (n)$ พันค่าแรก จุดบนเส้นบนสุดแสดงถึง $φ (p)$ เมื่อ $p$ เป็นจำนวนเฉพาะ ซึ่งก็คือ $p - 1$ ^{[ 1 ]}

ในทฤษฎีจำนวนฟังก์ชันโทเทียนต์ของออยเลอร์จะนับจำนวนเต็มบวกจนถึงจำนวนเต็มที่กำหนด $n$ ซึ่งค่อนข้างเหมาะสมที่จะ $n$ เขียนโดยใช้อักษรกรีกฟี (phi ) $\varphi (n)$ หรือ $\phi (n)$ และอาจเรียกว่าฟังก์ชันฟีของออยเลอร์ ก็ได้ กล่าว อีกนัยหนึ่งคือ เป็นจำนวนของจำนวนเต็ม $k$ ในช่วง $1\leq k\leq n$ ซึ่งตัวหารร่วมมากที่สุด $\gcd(n,k)$ เท่ากับ 1 ^{[ 2 ]}^{[ 3 ]}จำนวนเต็ม $k$ รูปแบบนี้บางครั้งเรียกว่าโทเททีฟของ $n$ .

ตัวอย่างเช่น ผลรวมของ $n=9$ ตัวเลขทั้งหกตัวได้แก่ 1, 2, 4, 5, 7 และ 8 ตัวเลขเหล่านี้เป็นจำนวนเฉพาะสัมพัทธ์กับ 9 แต่ตัวเลขอีกสามตัวในช่วงนี้ คือ 3, 6 และ 9 ไม่ใช่จำนวนเฉพาะสัมพัทธ์กับ 9 เนื่องจาก $\gcd(9,3)=\gcd(9,6)=3$ และ $\gcd(9,9)=9$ . ดังนั้น, $\varphi (9)=6$ ตัวอย่างเช่น $\varphi (1)=1$ เนื่องจากสำหรับ $n=1$ จำนวนเต็มเพียงจำนวนเดียวในช่วงตั้งแต่ 1 ถึง $n$ คือ 1 เอง และ $\gcd(1,1)=1$ .

ฟังก์ชันโทเทียนต์ของออยเลอร์เป็นฟังก์ชันการคูณหมายความว่า ถ้าจำนวนสองจำนวน... $m$ และ $n$ ถือว่าเป็นสินค้าที่มีศักยภาพค่อนข้างสูง $\varphi (mn)=\varphi (m)\varphi (n)$ [ ⁴^]^[⁵^] ฟังก์ชันนี้ให้ลำดับของกลุ่มการคูณของจำนวนเต็มโมดูล $n$ ( กลุ่มของหน่วยของวงแหวน⁾ $\mathbb {Z} /n\mathbb {Z}$ ). ^{[ 6 ]}นอกจากนี้ยังใช้สำหรับการกำหนดระบบการเข้ารหัส RSAด้วย

ประวัติ ศัพท์เฉพาะ และสัญลักษณ์

เลออนฮาร์ด ออยเลอร์ได้นำเสนอฟังก์ชันนี้ในปี 1763 ^{[ 7 ]}^{[ 8 ]}^{[ 9 ]}อย่างไรก็ตาม ในเวลานั้นเขายังไม่ได้เลือกสัญลักษณ์เฉพาะใดๆ เพื่อใช้แทนฟังก์ชันนี้ ในสิ่งพิมพ์ปี 1784 ออยเลอร์ได้ศึกษาฟังก์ชันนี้เพิ่มเติมและเลือกใช้อักษรกรีก $\pi$ เพื่อบ่งบอกว่า: เขาเขียน $\pi D$ สำหรับ "จำนวนมากมายที่น้อยกว่า" $D$ และซึ่งไม่มีตัวหารร่วมกับมัน” ^{[ 10 ]}คำจำกัดความนี้แตกต่างจากคำจำกัดความปัจจุบันของฟังก์ชันโทเทียนต์ที่ $D=1$ แต่โดยทั่วไปแล้วเหมือนกัน สัญกรณ์มาตรฐานในปัจจุบัน^{[ 8 ]}^{[ 11 ]} $\varphi (A)$ มาจาก ตำรา Disquisitiones ArithmeticaeของGauss ในปี ค.ศ. 1801 [ ¹²^]^[¹³^{] แม้ว่า Gauss จะไม่}^ได้ใช้วงเล็บรอบอาร์กิวเมนต์และเขียนว่า $\varphi A$ ดังนั้นจึงมักเรียกว่าฟังก์ชันฟีของออยเลอร์หรือเรียกสั้น ๆ ว่าฟังก์ชันฟี

ในปี พ.ศ. 2422 JJ Sylvesterได้บัญญัติศัพท์totientสำหรับฟังก์ชันนี้^{[ 14 ]}^{[ 15 ]}ดังนั้นจึงเรียกอีกอย่างว่าฟังก์ชัน totient ของออยเลอร์ , Euler totientหรือEuler's totient [ ^{16 ] Jordan} 's totientเป็นการวางนัยทั่วไปของ Euler

โคโตเทียนต์ของ $n$ ถูกกำหนดให้เป็น $n-\varphi (n)$ ฟังก์ชันนี้จะนับจำนวนของจำนวนเต็มบวกที่น้อยกว่าหรือเท่ากับ... $n$ ที่มีตัวประกอบ เฉพาะอย่างน้อยหนึ่ง ตัวร่วมกันกับ $n$ .

การคำนวณฟังก์ชันโทเทียนต์ของออยเลอร์

มีสูตรคำนวณอยู่หลายสูตร $\varphi (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$ , แล้ว $\varphi (m)\varphi (n)=\varphi (mn)$ โครงร่างการพิสูจน์ : ให้ $A,B,C$ ให้ เป็นเซตของจำนวนเต็มบวกซึ่งเป็นจำนวนเฉพาะสัมพัทธ์กับ และน้อยกว่า $m$ , $n$ , $mn$ ตามลำดับ โดยที่ $|A|=\varphi (m)$ เป็นต้น จากนั้นจะมีการจับคู่แบบหนึ่งต่อหนึ่งระหว่างกัน $A\times B$ และ $C$ โดยทฤษฎีบทเศษเหลือของจีน

ค่าของฟีสำหรับอาร์กิวเมนต์กำลังเฉพาะ

ถ้า $p$ เป็นจำนวนเฉพาะและ $k\geq 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^{2},\dots ,p^{k}$ และวิธีเดียวที่จะมี $\gcd(p^{k},m)>1$ คือถ้า $m$ เป็นพหุคูณของ $p$ นั่นคือ $m\in \{p,2p,3p,\ldots ,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}},$ where $p < p < ... < p$ are prime numbers and each $k \geq 1$ . (The case $n = 1$ corresponds to the empty product.) Repeatedly using the multiplicative property of $φ$ and the formula for $φ (p k)$ gives

{\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}}\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}}

This gives both versions of Euler's product formula.

An alternative proof that does not require the multiplicative property instead uses the inclusion-exclusion principle applied to the set $\{1,2,\ldots ,n\}$ , excluding the sets of integers divisible by the prime divisors.

Example

\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.

In words: the distinct prime factors of 20 are 2 and 5; half of the twenty integers from 1 to 20 are divisible by 2, leaving ten; a fifth of those are divisible by 5, leaving eight numbers coprime to 20; these are: 1, 3, 7, 9, 11, 13, 17, 19.

The alternative formula uses only integers: $\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.$

Fourier transform

The totient is the discrete Fourier transform of the gcd, evaluated at 1.^[17] Let

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

where $x = gcd(k, n)$ for $k \in {1, ..., n}$ . Then

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

The real part of this formula is

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

For example, using $\cos {\tfrac {\pi }{5}}={\tfrac {{\sqrt {5}}+1}{4}}$ and $\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}}$ Unlike the Euler product and the divisor sum formula, this one does not require knowing the factors of $n$ . However, it does involve the calculation of the greatest common divisor of $n$ and every positive integer less than $n$ , which suffices to provide the factorization anyway.

Divisor sum

The property established by Gauss,^[18] that

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

where the sum is over all positive divisors $d$ of $n$ , can be proven in several ways. (See Arithmetical function for notational conventions.)

หลักฐานหนึ่งคือสังเกตว่า $φ (d)$ ยังเท่ากับจำนวนตัวสร้างที่เป็นไปได้ของ $กลุ่ม$ วัฏจักร $Cd$ $โดย$ เฉพาะอย่างยิ่ง ถ้า $Cd = ⟨g⟩$ โดยที่ $gd = 1$ แล้ว $gk$ เป็นตัวสร้างสำหรับทุก $k ที่เป็นจำนวน$ สัมพัทธ์กับ $d$ เนื่องจากทุกองค์ประกอบของ $Cn$ สร้างกลุ่ม ย่อยวัฏจักร และแต่ละกลุ่มย่อย $Cd$ $\subseteq ถูก$ สร้างขึ้นโดยองค์ประกอบของ Cn เพียง $φ(d)$ ตัว $เท่านั้น$ $สูตร จึง เป็น$ ตามนั้น¹⁹^]^ใน $ทำนองเดียวกัน สูตร นี้ สามารถหาได้จาก$ ใช้อาร์กิวเมนต์เดียวกันกับกลุ่มการคูณของ รากที่ $n$ ของเอกภาพและ รากที่ $d$ ดั้งเดิม ของเอกภาพ

สูตรนี้สามารถหาได้จากเลขคณิตพื้นฐานเช่น กัน ^{[ 20 ]}ตัวอย่างเช่น ให้ $n = 20$ และพิจารณาเศษส่วนบวกถึง 1 ที่มีตัวส่วนเป็น 20:

{\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 ใดๆ

Möbius inversion applied to the divisor sum formula gives

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

where $μ$ is the Möbius function, the multiplicative function defined by $\mu (p)=-1$ and $\mu (p^{k})=0$ for each prime $p$ and $k \geq 2$ . This formula may also be derived from the product formula by multiplying out ${\textstyle \prod _{p\mid n}(1-{\frac {1}{p}})}$ to get ${\textstyle \sum _{d\mid n}{\frac {\mu (d)}{d}}.}$

An example: ${\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}}$

Some values

The first 100 values (sequence A000010 in the OEIS) are shown in the table and graph below:

$φ (n)$ for $1 \leq n \leq 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

In the graph at right the top line $y = n - 1$ is an upper bound valid for all $n$ other than one, and attained if and only if $n$ is a prime number. A simple lower bound is $\varphi (n)\geq {\sqrt {n/2}}$ , which is rather loose: in fact, the lower limit of the graph is proportional to $⁠ n / log log n ⁠$ .^[21]

Euler's theorem

This states that if $a$ and $n$ are relatively prime then

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

The special case where $n$ is prime is known as Fermat's little theorem.

This follows from Lagrange's theorem and the fact that $φ (n)$ is the order of the multiplicative group of integers modulo $n$ .

ระบบการเข้ารหัส RSAอิงตามทฤษฎีบทนี้: มันบ่งชี้ว่าฟังก์ชันผกผัน ของ $a \mapsto a e mod n$ โดยที่ $e$ คือเลขชี้กำลังการเข้ารหัส (สาธารณะ) คือฟังก์ชัน $b \mapsto b d mod n$ โดยที่ $d$ คือเลขชี้กำลังการถอดรหัส (ส่วนตัว) ซึ่งเป็นตัวผกผันการคูณของ $e$ modulo $φ (n)$ ความยากในการคำนวณ $φ (n)$ โดยไม่ทราบการแยกตัวประกอบของ $n$ จึงเท่ากับความยากในการคำนวณ $d$ : นี่คือปัญหา RSAซึ่งสามารถแก้ไขได้โดยการแยกตัวประกอบ ของ $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 (mn)=\varphi (m)\varphi (n)\cdot {\frac {d}{\varphi (d)}}\quad {\text{โดยที่ }}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 \geq 3$ ยิ่งไปกว่านั้น ถ้า $n$ มีตัวประกอบเฉพาะคี่ที่แตกต่างกัน $r ตัว$ $2 r | φ (n)$
สำหรับ $a > 1$ และ $n > 6$ ใดๆ ที่ $4 ∤ n$ จะมี $l \geq 2 n$ อยู่ ซึ่ง $l | φ (a n - 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)}}$ ^{[ 22 ]}
$\sum _{1\leq k\leq n-1 \atop gcd(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)$ ( ^{[ 23 ]}อ้างอิงใน^{[ 24 ]} )
$\sum _{k=1}^{n}\varphi (k)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {1}{3}}\right)$ [หลิว (2016)]
$\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)$ ^{[ 23 ]}
$\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)$ ^{[ 25 ]}
$\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)$ ^{[ 25 ]} (โดยที่ $γ$ คือค่าคงที่ออยเลอร์-มาสเชโรนี)

ตัวตนของเมนอน

ในปี 1965 พี. เกศวา เมนอน ได้พิสูจน์ว่า

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

โดยที่ $d (n) = σ0 (n)$ คือจำนวนตัวหาร $n$

หารลงตัวด้วยจำนวนเต็มบวกคงที่ใดๆ

คุณสมบัติต่อไปนี้ ซึ่งไม่ได้เผยแพร่เป็นผลลัพธ์เฉพาะ แต่เป็นที่รู้จักกันมานานแล้ว^{[ 26 ]}มีผลสำคัญ ตัวอย่างเช่น การตัดความเป็นไปได้ของการกระจายค่าอย่างสม่ำเสมอของ $\varphi (n)$ ในลำดับเลขคณิตโมดูลัส $q$ สำหรับจำนวนเต็มใดๆ $q>1$ .

สำหรับจำนวนเต็มบวกคงที่ทุกจำนวน $q$ ความสัมพันธ์ $q|\varphi (n)$ ใช้ได้กับเกือบทุกอย่าง $n$ หมายความว่าสำหรับทุกคนยกเว้น $o(x)$ ค่าของ $n\leq x$ เช่น $x\rightarrow \infty$ .

นี่เป็นผลลัพธ์พื้นฐานจากข้อเท็จจริงที่ว่า ผลรวมของส่วนกลับของจำนวนเฉพาะที่สอดคล้องกับ 1 มอดูลัส $q$ ลู่เข้า ซึ่งเป็นผลลัพธ์ที่ตามมาจากการพิสูจน์ทฤษฎีบทของดิริชเลต์เกี่ยวกับลำดับเลขคณิต

การสร้างฟังก์ชัน

อนุกรมDirichletสำหรับ $φ (n)$ สามารถเขียนได้ในรูปของฟังก์ชันซีตาของ Riemannดังนี้: ^{[ 27 ]}

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

อัตราการเติบโต

ตามคำกล่าวของ Hardy & Wright ลำดับของ $φ (n)$ คือ "เกือบจะเป็น $n$ เสมอ" ^{[ 29 ]}

แรก^{[ 30 ]}

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

แต่เมื่อnเข้าสู่ค่าอนันต์^{[ 31 ]} $สำหรับ δ$ $> 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$

เรายังมี^{[ 21 ]}

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

โดยที่ $γ$ คือค่าคงที่ของออยเลอร์ γ $= 0.577215665...$ ดังนั้น $e γ = 1.7810724...$ และ $e - γ = 0.56145948$ ...

การพิสูจน์สิ่งนี้ไม่จำเป็นต้องใช้ทฤษฎีบทจำนวนเฉพาะ [ ^{32 ] [}^{33 ] เนื่องจาก} log $log n$ เข้าสู่ค่าอนันต์ สูตรนี้แสดงให้เห็นว่า

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

ในความเป็นจริงแล้วยังมีความจริงอีกมากมาย^{[ 34 ]}^{[ 35 ]}^{[ 36 ]}

\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.

อสมการที่สองแสดงโดยJean-Louis Nicolas Ribenboim กล่าวว่า "วิธีการพิสูจน์นั้นน่าสนใจตรงที่อสมการแสดงขึ้นครั้งแรกภายใต้สมมติฐานที่ว่าสมมติฐานของ Riemannเป็นจริง และครั้งที่สองภายใต้สมมติฐานตรงกันข้าม" ^{[ 36 ]}^{: 173}

สำหรับลำดับเฉลี่ย เรามี^{[ 23 ]}^{[ 37 ]}

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

เนื่องจากArnold Walfiszการพิสูจน์โดยใช้ประโยชน์จากการประมาณค่าผลรวมเลขชี้กำลังโดยIM VinogradovและNM Korobovโดยการผสมผสานวิธีการของ van der Corput และ Vinogradov ทำให้ H.-Q. Liu (On Euler's function.Proc. Roy. Soc. Edinburgh Sect. A 146 (2016), no. 4, 769–775) ปรับปรุงพจน์ความคลาดเคลื่อนให้ดีขึ้น

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

(นี่คือค่าประมาณที่ดีที่สุดที่ทราบในปัจจุบันของประเภทนี้) "บิ๊ก $โอ$ "หมายถึงปริมาณที่ถูกจำกัดด้วยค่าคงที่คูณด้วยฟังก์ชันของ $n$ ภายในวงเล็บ (ซึ่งมีค่าน้อยเมื่อเทียบกับ $n²)$

ผลลัพธ์ นี้สามารถใช้เพื่อพิสูจน์^{[ 38 ]}ว่าความน่าจะเป็นที่จำนวนสองจำนวนที่สุ่มเลือกจะเป็นจำนวนเฉพาะสัมพัทธ์คือ6 / $π$ ²

อัตราส่วนของค่าที่ต่อเนื่องกัน

ในปี พ.ศ. 2493 โซมายาจูลูได้พิสูจน์แล้ว^{[ 39 ]}^{[ 40 ]}

{\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}}

ในปี พ.ศ. 2497 SchinzelและSierpińskiได้เสริมความแข็งแกร่งให้กับสิ่งนี้ โดยพิสูจน์^{[ 39 ]}^{[ 40 ]}ว่าเซต

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

มีความหนาแน่นในจำนวนจริงบวก พวกเขายังพิสูจน์^{[ 39 ]}ว่าเซต

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

มีความหนาแน่นในช่วง (0,1)

หมายเลขโทเทียนต์

จำนวนโทเทียนต์คือค่าของฟังก์ชันโทเทียนต์ของออยเลอร์ กล่าวคือ $m$ ที่มีอย่างน้อยหนึ่ง $n$ ที่ $φ (n) = m$ ค่าความเท่าเทียมหรือความหลากหลายของจำนวนโทเทียนต์ $m$ คือจำนวนคำตอบของสมการนี้^{[ 41 ]}จำนวนนอนโทเทียนต์คือจำนวนธรรมชาติที่ไม่ใช่จำนวนโทเทียนต์ จำนวนเต็มคี่ทุกจำนวนที่มากกว่า 1 นั้นเป็นจำนวนนอนโทเทียนต์โดยปริยาย นอกจากนี้ยังมีจำนวนนอนโทเทียนต์คู่จำนวนอนันต์^{[ 42 ]}และที่จริงแล้วจำนวนเต็มบวกทุกจำนวนมีตัวคูณที่เป็นจำนวนนอนโทเทียนต์คู่^{[ 43 ]}

ตัวเลขโทเทียนแรกๆ คือ $1,2,4,6,8,10,12,16,18,20$ โปรดดูลำดับ A002202

จำนวนของจำนวนโทเทียนต์จนถึงขีดจำกัดที่กำหนด $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 ใดๆ$ ^{[ 46 ]}^{[ 47 ]}

ทฤษฎีของฟอร์ด

ฟอร์ด (1999)พิสูจน์ว่าสำหรับจำนวนเต็ม $k \geq 2$ ทุกตัว จะมีจำนวนโทเทียนต์ $m ที่มีมัลติพลิซิตี้$ $k$ นั่นคือ สำหรับสมการ $φ (n) = m$ จะมี คำตอบ $k$ คำตอบพอดี ผลลัพธ์นี้เคยถูกคาดเดาไว้ก่อนหน้านี้โดยWacław Sierpiński [ ⁴⁸^]และได้มาเป็นผลสืบเนื่องมาจาก สมมติฐาน H ของ Schinzel ^[⁴⁴^{] อันที่จริง มัลติพลิซิตี้แต่ละ}^แบบที่เกิดขึ้น จะเกิดขึ้นเป็นอนันต์ครั้ง^[⁴⁴^]^[⁴⁷^]

อย่างไรก็ตาม ไม่ทราบ จำนวน $m ที่มีมัลติพลิซิตี้$ $k = 1$ ข้อสันนิษฐานฟังก์ชันโทเทียนต์ของคาร์ไมเคิลคือข้อความที่ระบุว่าไม่มี $m$ ดัง กล่าว^{[ 49 ]}

เลขโทเทียนที่สมบูรณ์แบบ

จำนวนโทเทียนสมบูรณ์คือจำนวนเต็มที่เท่ากับผลรวมของค่าโทเทียนที่ได้จากการทำซ้ำ กล่าวคือ เราใช้ฟังก์ชันโทเทียนกับจำนวนnแล้วใช้ฟังก์ชันนั้นอีกครั้งกับค่าโทเทียนที่ได้ และทำเช่นนี้ไปเรื่อยๆ จนกว่าจะถึงจำนวน 1 จากนั้นนำลำดับของจำนวนที่ได้ทั้งหมดมาบวกกัน ถ้าผลรวมเท่ากับnแล้วnก็เป็นจำนวนโทเทียนสมบูรณ์

แอปพลิเคชัน

ไซโคลโทมี

ในส่วนสุดท้ายของDisquisitiones ^{[ 50 ]}^{[ 51 ]}เกาส์พิสูจน์^{[ 52 ]} ว่า สามารถสร้างรูป $n$ เหลี่ยม ปกติ ได้ด้วยไม้บรรทัดและวงเวียน ถ้า $φ (n)$ เป็นกำลังของ 2 ถ้า $n$ เป็นกำลังของจำนวนเฉพาะคี่ สูตรสำหรับโทเทียนต์บอกว่าโทเทียนต์จะเป็นกำลังของ 2 ได้ก็ต่อเมื่อ $n$ เป็นกำลังแรกและ $n - 1$ เป็นกำลังของ 2 จำนวนเฉพาะที่มากกว่ากำลังของ 2 อยู่ 1 เรียกว่าจำนวนเฉพาะของแฟร์มาต์และมีเพียง 5 ตัวเท่านั้นที่ทราบ ได้แก่ 3, 5, 17, 257 และ 65537 แฟร์มาต์และเกาส์รู้จักจำนวนเฉพาะเหล่านี้ ไม่มีใครสามารถพิสูจน์ได้ว่ามีจำนวนเฉพาะมากกว่านี้หรือไม่

ดังนั้น รูป $n$ เหลี่ยมปกติจะมีโครงสร้างแบบไม้บรรทัดและวงเวียนหากn เป็นผลคูณของจำนวนเฉพาะเฟอร์มาต์ที่แตกต่างกันและกำลังใดๆ ของ 2 $n$ แรกๆ ดังกล่าวคือ^{[ 53 ]}

2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40,... ( ลำดับA003401ในOEIS )

ทฤษฎีบทจำนวนเฉพาะสำหรับลำดับเลขคณิต

ระบบการเข้ารหัส RSA

การตั้งค่าระบบ RSA เกี่ยวข้องกับการเลือกจำนวนเฉพาะขนาดใหญ่ $p$ และ $q$ การคำนวณ $n = pq$ และ $k = φ (n)$ และการหาจำนวน $e$ และ $d$ สองจำนวน ที่ทำให้ $ed \equiv 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$

ปัญหาที่ยังแก้ไม่ตก

ข้อสันนิษฐานของเลห์เมอร์

ถ้า $p$ เป็นจำนวนเฉพาะ $φ (p) = p - 1$ ในปี พ.ศ. 2475 DH Lehmerถามว่ามีจำนวนประกอบ $n$ ใดบ้าง ที่ $φ (n)$ หาร $n - 1$ ลงตัว ไม่มีจำนวนประกอบ ใดที่ทราบ^{[ 54 ]}

$ในปี พ.ศ. 2476 เขาพิสูจน์ว่าหาก n$ ดังกล่าวมีอยู่จริง จะต้องเป็นจำนวนคี่ ไม่มีตัวประกอบกำลังสอง และหารลงตัวด้วยจำนวนเฉพาะอย่างน้อยเจ็ดตัว (กล่าวคือ $ω (n) \geq 7$ ) ในปี พ.ศ. 2523 โคเฮนและฮากิสพิสูจน์ว่า $n > 10²⁰$ และ $ω (n) \geq 14$ [ ^{55 ] นอกจาก}นี้ ฮากิสยังแสดงให้เห็นว่าหาก 3 หาร $n$ ลงตัว แล้ว $n > 10¹⁹³⁷⁰⁴²$ และ $ω (n) \geq$ 2⁹⁸⁴⁸ ^{[ 56 ]}^{[ 57 ]}

ข้อสันนิษฐานของคาร์ไมเคิล

ข้อความนี้ระบุว่าไม่มีตัวเลข $n$ โดยมีคุณสมบัติสำหรับตัวเลขอื่นๆ ทั้งหมด $m$ , $m\neq n$ , $\varphi (m)\neq \varphi (n)$ ดูทฤษฎีของฟอร์ดด้านบนประกอบ

หากมีตัวอย่างค้าน เพียงตัวอย่างเดียว สำหรับข้อสันนิษฐานนี้ ก็จะต้องมีตัวอย่างค้านจำนวนอนันต์ และตัวอย่างค้านที่เล็กที่สุดก็มีตัวเลขอย่างน้อยหนึ่งหมื่นล้านหลักในฐาน 10 ^{[ 41 ]}

สมมติฐานของรีมันน์

สมมติฐานของ รีมันน์ เป็นจริงก็ต่อเมื่ออสมการ

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

เป็นความจริงสำหรับทุกคน $n\geq p_{120569}\#$ ที่ไหน $\gamma$ คือค่าคงที่ของออยเลอร์และ $p_{120569}\#$ เป็น ผลคูณของ จำนวนเฉพาะ $120569 ตัว$ แรก^[⁵⁸^]

ดูเพิ่มเติม

หมายเหตุ

↑ "ฟังก์ชันโทเทียนต์ของออยเลอร์" . Khan Academy . สืบค้นเมื่อ2016-02-26 .
↑ลอง (1972 , หน้า85)
↑ Pettofrezzo & Byrkit (1970 , หน้า72)
↑ลอง (1972 , หน้า162)
↑ Pettofrezzo & Byrkit (1970 , หน้า80)
↑ดูทฤษฎีบทของออยเลอร์
↑ L. Euler " Theoremata arithmetica nova methodo demonstrata " (ทฤษฎีบททางคณิตศาสตร์ที่พิสูจน์โดยวิธีใหม่), Novi commentarii academiae scientiarum imperialis Petropolitanae (บันทึกใหม่ของสถาบันวิทยาศาสตร์จักรวรรดิเซนต์ปีเตอร์สเบิร์ก), 8 (1763), 74–104. (ผลงานนี้ได้รับการนำเสนอที่สถาบันเซนต์ปีเตอร์สเบิร์กเมื่อวันที่ 15 ตุลาคม 1759 ผลงานที่มีชื่อเดียวกันนี้ได้รับการนำเสนอที่สถาบันเบอร์ลินเมื่อวันที่ 8 มิถุนายน 1758) สามารถดูได้ทางออนไลน์ใน: Ferdinand Rudio , ed. , Leonhardi Euleri Commentationes Arithmeticae , เล่ม 1, ใน: Leonhardi Euleri Opera Omnia , ชุด 1, เล่ม 2 (ไลป์ซิก, เยอรมนี, BG Teubner, 1915),หน้า 531–555ในหน้า 531 ออยเลอร์ได้ให้คำจำกัดความไว้ว่า $n$ เนื่องจากจำนวนของจำนวนเต็มที่น้อยกว่า $N$ และค่อนข้างพร้อมสำหรับ $N$ (... aequalis นั่ง multitudini numerorum ipso N minorum, qui simul ad eum sint primi, ...) ซึ่งเป็นฟังก์ชัน phi, φ(N)
1 2แซนดิเฟอร์, หน้า 203
↑ Graham et al. หน้า 133 หมายเหตุ 111
↑แอล. ออยเลอร์, Speculationes circa quasdam insignes proprietates numerorum , Acta Academiae Scientarum Imperialis Petropolitinae, vol. 4, (1784), หน้า 18–30 หรือ Opera Omnia, Series 1, เล่ม 4, หน้า 105–115 (งานนี้นำเสนอที่ Saint-Petersburg Academy เมื่อวันที่ 9 ตุลาคม พ.ศ. 2318)
↑ทั้ง $φ (n)$ และ $ϕ (n) ปรากฏอยู่ในเอกสารทางวิชาการ นี่คือรูปแบบสองแบบของอักษรกรีก$ ฟีตัวเล็ก
↑เกาส์, Disquisitiones Arithmeticaeบทความ 38
↑ Cajori, Florian (1929). ประวัติของสัญลักษณ์ทางคณิตศาสตร์ เล่มที่ 2.สำนักพิมพ์ Open Court. §409.
↑ JJ Sylvester (1879) "เกี่ยวกับสมการลูกบาศก์สามตัวแปรบางสมการ" American Journal of Mathematics , 2 : 357-393; Sylvester บัญญัติศัพท์ "totient" ในหน้า 361
↑ "totient". พจนานุกรมภาษาอังกฤษฉบับออกซ์ฟอ ร์ด ( ฉบับที่ 2). สำนักพิมพ์มหาวิทยาลัยออกซ์ฟอร์ด . 1989.
↑ Weisstein, Eric W. "ฟังก์ชันโทเทียนต์" . mathworld.wolfram.com . สืบค้นเมื่อ2025-02-09 .
↑ชแรมม์ (2008)
↑เกาส์, DA, บทความที่ 39
↑เกาส์, ดีเอ อาร์ต. 39 ศิลปะ 52-54
↑เกรแฮมและคณะ หน้า 134-135
1 2 Hardy & Wright 1979 , thm. 328
↑ Dineva (ในเอกสารอ้างอิงภายนอก), ข้อเสนอ 1
1 2 3 วอลฟิสซ์, อาร์โนลด์ (1963) Weylsche Exponentialsummen ใน der neueren Zahlentheorie Mathematische Forschungsberichte (ภาษาเยอรมัน) ฉบับที่16. เบอร์ลิน: VEB Deutscher Verlag der Wissenschaften . สบีแอล0146.06003 .
↑ Lomadse, G. (1964), "ผลงานทางวิทยาศาสตร์ของ Arnold Walfisz" (PDF) , Acta Arithmetica , 10 (3): 227– 237, doi : 10.4064/aa-10-3-227-237
1 2 Sitaramachandrarao, R. (1985). "เกี่ยวกับเทอมความคลาดเคลื่อนของ Landau II" . Rocky Mountain J. Math . 15 (2): 579– 588. doi : 10.1216/RMJ-1985-15-2-579 .
↑ Pollack, P. (2023), "ปัญหาสองข้อเกี่ยวกับการกระจายของฟังก์ชันแลมบ์ดาของคาร์ไมเคิล", Mathematika , 69 (4): 1195– 1220, arXiv : 2303.14043 , doi : 10.1112/mtk.12222
↑ Hardy & Wright 1979 , thm. 288
↑ Hardy & Wright 1979 , thm. 309
↑ Hardy & Wright 1979 บทนำสู่ § 18.4
↑ Hardy & Wright 1979 , thm. 326
↑ Hardy & Wright 1979 , thm. 327
↑อันที่จริง ทฤษฎีบทของเชบิเชฟ ( Hardy & Wright 1979 , thm.7 ) และทฤษฎีบทที่สามของเมอร์เทนส์ก็เพียงพอแล้ว
↑ Hardy & Wright 1979 , thm. 436
↑ทฤษฎีบทที่ 15 ของ Rosser, J. Barkley; Schoenfeld, Lowell (1962). "สูตรโดยประมาณสำหรับฟังก์ชันบางอย่างของจำนวนเฉพาะ" . Illinois J. Math . 6 (1): 64– 94. doi : 10.1215/ijm/1255631807 .
↑บาค & ชาลลิต, thm. 8.8.7
1 2 Ribenboim (1989). "การกระจายตัวของจำนวนเฉพาะเป็นอย่างไร? §IC การกระจายตัวของค่าฟังก์ชันของออยเลอร์" หนังสือบันทึกจำนวนเฉพาะ ( ฉบับที่ 2). นิวยอร์ก: Springer-Verlag. หน้า172–175 . doi : 10.1007/978-1-4684-0507-1_5 . ISBN 978-1-4684-0509-5.
↑ซานดอร์, มิทริโนวิช และเครสติซี (2006) หน้า 24–25
↑ Hardy & Wright 1979 , thm. 332
1 2 3ริเบนบอยม์, หน้า 38
1 2 Sándor, Mitrinović & Crstici (2006) หน้า 16
1 2กาย (2004) หน้า 144
↑ Sándor & Crstici (2004) หน้า 230
↑ Zhang, Mingzhi (1993). "เกี่ยวกับสิ่งที่ไม่ใช่โทเทียน" . วารสารทฤษฎีจำนวน . 43 (2): 168– 172. doi : 10.1006/jnth.1993.1014 . ISSN 0022-314X . Zbl 0772.11001 .
1 2 3 Ford, Kevin (1998). "การกระจายตัวของ totients". Ramanujan J . 2 ( 1– 2): 67– 151. doi : 10.1023/A:1009761909132 . ISSN 1382-4090 . Zbl 0914.11053 . ตีพิมพ์ซ้ำในAnalytic and Elementary Number Theory: A Tribute to Mathematical Legend Paul Erdos , Developments in Mathematics, vol. 1, 1998, doi : 10.1007/978-1-4757-4507-8_8 , ISBN 978-1-4419-5058-1ปรับปรุงและแก้ไขในarXiv : 1104.3264 , 2011.
↑ Sándor et al (2006) หน้า 22
↑ Sándor et al (2006) หน้า 21
1 2กาย (2004) หน้า 145
↑ซานดอร์ แอนด์ เครสติซี (2004) หน้า 229
↑ Sándor & Crstici (2004) หน้า 228
↑ Gauss, DA. มาตราที่ 7 คือ มาตรา 336–366
↑เกาส์พิสูจน์ว่าถ้า $n$ ตรงตามเงื่อนไขบางประการ รูป $n$ ด้านก็สามารถสร้างได้ ในปี ค.ศ. 1837ปิแอร์ วอนต์เซลพิสูจน์สิ่งที่ตรงกันข้าม คือ ถ้าสร้าง $รูป n ด้านได้$ $n$ ด้าน ก็ ต้องตรงตามเงื่อนไขของเกาส์ด้วย
↑เกาส์, DA, บทความ 366
↑ Gauss, DA, art. 366. รายการนี้เป็นประโยคสุดท้ายใน Disquisitiones
↑ Ribenboim, หน้า 36–37.
↑โคเฮน, แกรม แอล.; ฮากิส, ปีเตอร์ จูเนียร์ (1980) "เกี่ยวกับจำนวนตัวประกอบเฉพาะของ $n$ ถ้า $φ$ $($ $n$ $)$ หาร $n$ $- 1$ " นิวอาร์ค. วิสค์ . ซีรี่ส์ที่สาม28 : 177– 185. ISSN 0028-9825 . สบีแอล0436.10002 .
↑ฮากิส, ปีเตอร์ จูเนียร์ (1988) "บนสมการ $M$ $\cdotφ($ $n$ $) =$ $n$ $- 1$ " นิวอาร์ค. วิสค์ . ซีรี่ส์ IV 6 (3): 255– 261. ISSN 0028-9825 . สบีแอล0668.10006 .
↑กาย (2004) หน้า 142
↑ Broughan, Kevin (2017). ค่าเทียบเท่าของสมมติฐานรีมันน์ เล่มหนึ่ง: ค่าเทียบเท่าทางเลขคณิต ( ฉบับพิมพ์ครั้งแรก). สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. ISBN 978-1-107-19704-6.บทสรุป 5.35

ลิงก์ภายนอก

"ฟังก์ชันโทเทียนต์" , สารานุกรมคณิตศาสตร์ , EMS Press , 2001 [1994]
ฟังก์ชันฟีของออยเลอร์และทฤษฎีบทเศษเหลือของจีน — การพิสูจน์ว่า $φ (n)$ เป็นฟังก์ชันทวีคูณเก็บ ถาวร เมื่อ 2021-02-28 ที่Wayback Machine
เครื่องคำนวณฟังก์ชันโทเทียนต์ของออยเลอร์ใน JavaScript — สูงสุด 20 หลัก
Dineva, Rosica, The Euler Totient, the Möbius, and the Divisor Functions Archived 2021-01-16 at the Wayback Machine
Plytage, Loomis, Polhill สรุปฟังก์ชัน Phi ของออยเลอร์

[1] "ฟังก์ชันโทเทียนต์ของออยเลอร์" . Khan Academy . สืบค้นเมื่อ2016-02-26 .

[2] ลอง (1972 , หน้า85)

[3] Pettofrezzo & Byrkit (1970 , หน้า72)

[4] ลอง (1972 , หน้า162)

[5] Pettofrezzo & Byrkit (1970 , หน้า80)

[6] ดูทฤษฎีบทของออยเลอร์

[7] L. Euler " Theoremata arithmetica nova methodo demonstrata " (ทฤษฎีบททางคณิตศาสตร์ที่พิสูจน์โดยวิธีใหม่), Novi commentarii academiae scientiarum imperialis Petropolitanae (บันทึกใหม่ของสถาบันวิทยาศาสตร์จักรวรรดิเซนต์ปีเตอร์สเบิร์ก), 8 (1763), 74–104. (ผลงานนี้ได้รับการนำเสนอที่สถาบันเซนต์ปีเตอร์สเบิร์กเมื่อวันที่ 15 ตุลาคม 1759 ผลงานที่มีชื่อเดียวกันนี้ได้รับการนำเสนอที่สถาบันเบอร์ลินเมื่อวันที่ 8 มิถุนายน 1758) สามารถดูได้ทางออนไลน์ใน: Ferdinand Rudio , ed. , Leonhardi Euleri Commentationes Arithmeticae , เล่ม 1, ใน: Leonhardi Euleri Opera Omnia , ชุด 1, เล่ม 2 (ไลป์ซิก, เยอรมนี, BG Teubner, 1915),หน้า 531–555ในหน้า 531 ออยเลอร์ได้ให้คำจำกัดความไว้ว่า $n$ เนื่องจากจำนวนของจำนวนเต็มที่น้อยกว่า $N$ และค่อนข้างพร้อมสำหรับ $N$ (... aequalis นั่ง multitudini numerorum ipso N minorum, qui simul ad eum sint primi, ...) ซึ่งเป็นฟังก์ชัน phi, φ(N)

[Sandifer,_p._203-8] 1 2แซนดิเฟอร์, หน้า 203

[9] Graham et al. หน้า 133 หมายเหตุ 111

[10] แอล. ออยเลอร์, Speculationes circa quasdam insignes proprietates numerorum , Acta Academiae Scientarum Imperialis Petropolitinae, vol. 4, (1784), หน้า 18–30 หรือ Opera Omnia, Series 1, เล่ม 4, หน้า 105–115 (งานนี้นำเสนอที่ Saint-Petersburg Academy เมื่อวันที่ 9 ตุลาคม พ.ศ. 2318)

[11] ทั้ง $φ (n)$ และ $ϕ (n) ปรากฏอยู่ในเอกสารทางวิชาการ นี่คือรูปแบบสองแบบของอักษรกรีก$ ฟีตัวเล็ก

[12] เกาส์, Disquisitiones Arithmeticaeบทความ 38

[13] Cajori, Florian (1929). ประวัติของสัญลักษณ์ทางคณิตศาสตร์ เล่มที่ 2.สำนักพิมพ์ Open Court. §409.

[14] JJ Sylvester (1879) "เกี่ยวกับสมการลูกบาศก์สามตัวแปรบางสมการ" American Journal of Mathematics , 2 : 357-393; Sylvester บัญญัติศัพท์ "totient" ในหน้า 361

[15] "totient". พจนานุกรมภาษาอังกฤษฉบับออกซ์ฟอ ร์ด ( ฉบับที่ 2). สำนักพิมพ์มหาวิทยาลัยออกซ์ฟอร์ด . 1989.

[16] Weisstein, Eric W. "ฟังก์ชันโทเทียนต์" . mathworld.wolfram.com . สืบค้นเมื่อ2025-02-09 .

[17] ชแรมม์ (2008)

[18] เกาส์, DA, บทความที่ 39

[19] เกาส์, ดีเอ อาร์ต. 39 ศิลปะ 52-54

[20] เกรแฮมและคณะ หน้า 134-135

[hw328-21] 1 2 Hardy & Wright 1979 , thm. 328

[22] Dineva (ในเอกสารอ้างอิงภายนอก), ข้อเสนอ 1

[Wal1963-23] 1 2 3 วอลฟิสซ์, อาร์โนลด์ (1963) Weylsche Exponentialsummen ใน der neueren Zahlentheorie Mathematische Forschungsberichte (ภาษาเยอรมัน) ฉบับที่16. เบอร์ลิน: VEB Deutscher Verlag der Wissenschaften . สบีแอล0146.06003 .

[24] Lomadse, G. (1964), "ผลงานทางวิทยาศาสตร์ของ Arnold Walfisz" (PDF) , Acta Arithmetica , 10 (3): 227– 237, doi : 10.4064/aa-10-3-227-237

[Sita-25] 1 2 Sitaramachandrarao, R. (1985). "เกี่ยวกับเทอมความคลาดเคลื่อนของ Landau II" . Rocky Mountain J. Math . 15 (2): 579– 588. doi : 10.1216/RMJ-1985-15-2-579 .

[26] Pollack, P. (2023), "ปัญหาสองข้อเกี่ยวกับการกระจายของฟังก์ชันแลมบ์ดาของคาร์ไมเคิล", Mathematika , 69 (4): 1195– 1220, arXiv : 2303.14043 , doi : 10.1112/mtk.12222

[27] Hardy & Wright 1979 , thm. 288

[28] Hardy & Wright 1979 , thm. 309

[29] Hardy & Wright 1979 บทนำสู่ § 18.4

[30] Hardy & Wright 1979 , thm. 326

[31] Hardy & Wright 1979 , thm. 327

[32] อันที่จริง ทฤษฎีบทของเชบิเชฟ ( Hardy & Wright 1979 , thm.7 ) และทฤษฎีบทที่สามของเมอร์เทนส์ก็เพียงพอแล้ว

[33] Hardy & Wright 1979 , thm. 436

[34] ทฤษฎีบทที่ 15 ของ Rosser, J. Barkley; Schoenfeld, Lowell (1962). "สูตรโดยประมาณสำหรับฟังก์ชันบางอย่างของจำนวนเฉพาะ" . Illinois J. Math . 6 (1): 64– 94. doi : 10.1215/ijm/1255631807 .

[35] บาค & ชาลลิต, thm. 8.8.7

[Rib320-36] 1 2 Ribenboim (1989). "การกระจายตัวของจำนวนเฉพาะเป็นอย่างไร? §IC การกระจายตัวของค่าฟังก์ชันของออยเลอร์" หนังสือบันทึกจำนวนเฉพาะ ( ฉบับที่ 2). นิวยอร์ก: Springer-Verlag. หน้า172–175 . doi : 10.1007/978-1-4684-0507-1_5 . ISBN 978-1-4684-0509-5.

[SMC2425-37] ซานดอร์, มิทริโนวิช และเครสติซี (2006) หน้า 24–25

[38] Hardy & Wright 1979 , thm. 332

[Rib38-39] 1 2 3ริเบนบอยม์, หน้า 38

[SMC16-40] 1 2 Sándor, Mitrinović & Crstici (2006) หน้า 16

[Guy144-41] 1 2กาย (2004) หน้า 144

[SC230-42] Sándor & Crstici (2004) หน้า 230

[Zha1993-43] Zhang, Mingzhi (1993). "เกี่ยวกับสิ่งที่ไม่ใช่โทเทียน" . วารสารทฤษฎีจำนวน . 43 (2): 168– 172. doi : 10.1006/jnth.1993.1014 . ISSN 0022-314X . Zbl 0772.11001 .

[Ford1998-44] 1 2 3 Ford, Kevin (1998). "การกระจายตัวของ totients". Ramanujan J . 2 ( 1– 2): 67– 151. doi : 10.1023/A:1009761909132 . ISSN 1382-4090 . Zbl 0914.11053 . ตีพิมพ์ซ้ำในAnalytic and Elementary Number Theory: A Tribute to Mathematical Legend Paul Erdos , Developments in Mathematics, vol. 1, 1998, doi : 10.1007/978-1-4757-4507-8_8 , ISBN 978-1-4419-5058-1ปรับปรุงและแก้ไขในarXiv : 1104.3264 , 2011.

[SMC22-45] Sándor et al (2006) หน้า 22

[SMC21-46] Sándor et al (2006) หน้า 21

[Guy145-47] 1 2กาย (2004) หน้า 145

[SC229-48] ซานดอร์ แอนด์ เครสติซี (2004) หน้า 229

[SC228-49] Sándor & Crstici (2004) หน้า 228

[50] Gauss, DA. มาตราที่ 7 คือ มาตรา 336–366

[51] เกาส์พิสูจน์ว่าถ้า $n$ ตรงตามเงื่อนไขบางประการ รูป $n$ ด้านก็สามารถสร้างได้ ในปี ค.ศ. 1837ปิแอร์ วอนต์เซลพิสูจน์สิ่งที่ตรงกันข้าม คือ ถ้าสร้าง $รูป n ด้านได้$ $n$ ด้าน ก็ ต้องตรงตามเงื่อนไขของเกาส์ด้วย

[52] เกาส์, DA, บทความ 366

[53] Gauss, DA, art. 366. รายการนี้เป็นประโยคสุดท้ายใน Disquisitiones

[54] Ribenboim, หน้า 36–37.

[55] โคเฮน, แกรม แอล.; ฮากิส, ปีเตอร์ จูเนียร์ (1980) "เกี่ยวกับจำนวนตัวประกอบเฉพาะของ $n$ ถ้า $φ$ $($ $n$ $)$ หาร $n$ $- 1$ " นิวอาร์ค. วิสค์ . ซีรี่ส์ที่สาม28 : 177– 185. ISSN 0028-9825 . สบีแอล0436.10002 .

[56] ฮากิส, ปีเตอร์ จูเนียร์ (1988) "บนสมการ $M$ $\cdotφ($ $n$ $) =$ $n$ $- 1$ " นิวอาร์ค. วิสค์ . ซีรี่ส์ IV 6 (3): 255– 261. ISSN 0028-9825 . สบีแอล0668.10006 .

[Guy142-57] กาย (2004) หน้า 142

[58] Broughan, Kevin (2017). ค่าเทียบเท่าของสมมติฐานรีมันน์ เล่มหนึ่ง: ค่าเทียบเท่าทางเลขคณิต ( ฉบับพิมพ์ครั้งแรก). สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. ISBN 978-1-107-19704-6.บทสรุป 5.35

[ 1 ]

[ 2 ]

[ 3 ]

4

[

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

12

[

[ 14 ]

[ 15 ]

16 ] Jordan

[17]

[18]

19

[ 20 ]

[21]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[

[ 29 ]

[ 30 ]

[ 31 ]

32 ] [

33 ] เนื่องจาก

[ 34 ]

[ 35 ]

[ 36 ]

[ 37 ]

[ 38 ]

[ 39 ]

[ 40 ]

[ 41 ]

[ 42 ]

[ 43 ]

...

[

[ 46 ]

[ 47 ]

48

[ 49 ]

[ 50 ]

[ 51 ]

[ 52 ]

[ 53 ]

[ 54 ]

55 ] นอกจาก

[ 56 ]

[ 57 ]

[

+	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

+	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