Funkcja φ

Wygląd przypnij ukryj

Funkcja φ (Eulera) lub tocjent – funkcja przypisująca każdej liczbie naturalnej liczbę liczb względnie pierwszych z nią i nie większych od niej. Nazwa pochodzi od nazwiska Leonharda Eulera.

Kilka początkowych wartości funkcji φ ( n ) : {\displaystyle \varphi (n){:}}

+	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

Funkcja Eulera odgrywa dużą rolę w teorii liczb. Ma też istotne zastosowania w kryptografii w badaniach nad złożonością szyfrów.

Własności

• Dla każdej liczby naturalnej n > 1 : {\displaystyle n>1{:}}

φ ( n ) ⩽ n − 1. {\displaystyle \varphi (n)\leqslant n-1.}

• Jeżeli p {\displaystyle p} jest pierwsza, to każda z liczb 1 , 2 , … , p − 1 {\displaystyle 1,2,\dots ,p-1} jest względnie pierwsza z p , {\displaystyle p,} więc

φ ( p ) = p − 1 {\displaystyle \varphi (p)=p-1} .

• Jeżeli liczby całkowite m , n {\displaystyle m,n} są względnie pierwsze, to

φ ( m n ) = φ ( m ) φ ( n ) . {\displaystyle \varphi (mn)=\varphi (m)\varphi (n).}

• Jeżeli p {\displaystyle p} jest liczbą pierwszą, to

φ ( p k ) = p k − 1 ⋅ ( p − 1 ) . {\displaystyle \varphi (p^{k})=p^{k-1}\cdot (p-1).}

• Jeżeli p 1 , p 2 , … , p k {\displaystyle p_{1},p_{2},\dots ,p_{k}} są wszystkimi czynnikami pierwszymi liczby n {\displaystyle n} liczonymi bez powtórzeń, to

φ ( n ) = n ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) … ( 1 − 1 p k ) . {\displaystyle \varphi (n)=n\left(1-{\tfrac {1}{p_{1}}}\right)\left(1-{\tfrac {1}{p_{2}}}\right)\dots \left(1-{\tfrac {1}{p_{k}}}\right).}

• Jeżeli n {\displaystyle n} nie ma wielokrotnych dzielników pierwszych, tj.

n = p 1 p 2 … p k , {\displaystyle n=p_{1}p_{2}\dots p_{k},} gdzie liczby p i {\displaystyle p_{i}} są pierwsze i parami różne ( i = 1 , … , k ) , {\displaystyle (i=1,\dots ,k),} to φ ( n ) = ( p 1 − 1 ) ( p 2 − 1 ) … ( p k − 1 ) . {\displaystyle \varphi (n)=(p_{1}-1)(p_{2}-1)\dots (p_{k}-1).}

• Dla dowolnej liczby całkowitej n {\displaystyle n} zachodzi

∑ m | n φ ( m ) = n {\displaystyle \sum _{m|n}\varphi (m)=n} (sumowanie obejmuje wszystkie dzielniki liczby n {\displaystyle n} ).

• Jeżeli

n = ∏ i = 1 k p i k i {\displaystyle n=\prod _{i=1}^{k}p_{i}^{k_{i}}} jest rozkładem liczby n {\displaystyle n} na czynniki pierwsze, to φ ( n ) = ∏ i = 1 k φ ( p i k i ) , {\displaystyle \varphi (n)=\prod _{i=1}^{k}\varphi \left(p_{i}^{k_{i}}\right),} co wynika z multiplikatywności tej funkcji.

Zobacz też

• chińskie twierdzenie o resztach
• funkcja Carmichaela
• funkcja π
• małe twierdzenie Fermata
• RSA
• twierdzenie Eulera

Uwagi

1. ↑ W Arytmetyce teoretycznej Sierpińskiego funkcja ta nosi nazwę funkcja Gaussa.

Przypisy

1. ↑ Funkcje Eulera, Encyklopedia PWN  .
2. ↑ a b Funkcja φ Eulera , www.math.edu.pl  .
3. ↑ Twierdzenie Eulera | Informatyka MIMUW , smurf.mimuw.edu.pl   (pol.).
4. ↑ https://web.archive.org/web/20171014183751/https://cs.pwr.edu.pl/ralowski/dydaktyka/algebra_abstrakcyjna/pomoce/euler.pdf
5. ↑ Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Matematyka konkretna. PWN, 2001, s. 158-171. ISBN 83-01-12124-6.
6. ↑ a b Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Matematyka konkretna. PWN, 2001, s. 159. ISBN 83-01-12124-6.
7. ↑ a b Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Matematyka konkretna. PWN, 2001, s. 160. ISBN 83-01-12124-6.
8. ↑ Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Matematyka konkretna. PWN, 2001, s. 161. ISBN 83-01-12124-6.
9. ↑ AdamA. Neugebauer AdamA., Matematyka olimpijska. 1, Algebra i teoria liczb, wyd. I, Kraków: Wydawnictwo Szkolne OMEGA, 2018, s. 146-147, ISBN 978-83-7267-710-5, OCLC 1055646686  .

Bibliografia

• Wacław Sierpiński: Arytmetyka Teoretyczna. Warszawa: Państwowe Wydawnictwo Naukowe, 1969, s. 133–135, seria: Biblioteka Matematyczna t. 7.
• Władysław Narkiewicz: Teoria Liczb. Warszawa: Państwowe Wydawnictwo Naukowe, 1977, s. 33, 68, 71–72, seria: Biblioteka Matematyczna t. 50.

Linki zewnętrzne

• Witold Bednarek: Funkcja Eulera. „Delta”, październik 2019. . (pol.).

Ciągi liczbowe

pojęcia definiujące	ciągi ogólne funkcja dziedzina liczby naturalne podzbiór ciągi liczbowe przeciwdziedzina liczba
typy ciągów	ogólne skończone para uporządkowana krotka lista nieskończone różnowartościowe permutacje ograniczone okresowe monotoniczne niemalejące nierosnące rosnące superrosnące malejące stałe arytmetyczne geometryczne ułamki dziesiętne nieskończone nieograniczone Cauchy’ego zbieżne i rozbieżne rozbieżne do nieskończoności sumowalne metodą Cesàro szeregi liczbowe geometryczne harmoniczne naprzemienne Dirichleta ułamki dziesiętne nieskończone nieskończone iloczyny liczbowe ułamki łańcuchowe funkcje arytmetyczne addytywne multyplikatywne
przykłady ciągów liczb naturalnych	niemalejące ciąg Eulera ciąg Fibonacciego funkcja pi ( π {\displaystyle \pi } – licząca liczby pierwsze) funkcja Liouville’a liczby Armstronga liczby autobiograficzne liczby automorficzne liczby bezkwadratowe liczby Carmichaela liczby Cullena liczby czworościenne liczby deficytowe liczby doskonałe liczby Fermata liczby gładkie liczby kwadratowe liczby Mersenne’a liczby nadmiarowe liczby Nivena liczby palindromiczne liczby Pella liczby pierwsze liczby piramidalne liczby półpierwsze liczby pseudopierwsze liczby Smitha liczby sfeniczne liczby Sierpińskiego liczby taksówkowe liczby trójkątne liczby wesołe liczby złożone silnia inne funkcja Collatza funkcja τ {\displaystyle \tau } (tau) funkcja σ {\displaystyle \sigma } (sigma) funkcja Möbiusa funkcja Mertensa tocjent Eulera funkcja lambda Carmichaela ω {\displaystyle \omega } (funkcja pierwsza omega) Ω {\displaystyle \Omega } (funkcja druga omega) funkcja Kempnera podsilnia suma alikwotowa szereg Grandiego
inne przykłady ciągów liczb	charakter Dirichleta ciąg Fareya funkcja von Mangoldta liczby Bernoulliego problem bazylejski ciąg harmoniczny ułamki egipskie wzór Stirlinga
twierdzenia	o granicach Bolzana-Weierstrassa o dwóch ciągach o trzech ciągach o zbieżności ciągu monotonicznego o zbieżności średnich Stolza inne o ciągach jednomonotonicznych nierówność Czebyszewa
powiązane pojęcia	podciąg ciąg uogólniony splot Dirichleta symbole nieoznaczone

Encyklopedia internetowa (funkcja):

• Britannica: topic/Euler-phi-function