Funkcje numeryczne

W teorii liczb istnieje wiele funkcji numerycznych zależnych od liczb naturalnych. Rozważymy niektóre z tych funkcji, które są szeroko stosowane zarówno w algorytmach kryptograficznych, jak i w kryptoanalizie.

Istnieje dodatnia liczba całkowita m. Może być złożony lub prosty.

Funkcja Eulera jest zwykle oznaczana w prawie wszystkich podręcznikach jako:

Funkcja Cel:

Powiedzmy, że mamy liczbę m - liczbę naturalną. Przyjrzyjmy się wszystkim liczbom na osi.

1,2,3,4…. m-1 m

Ile liczb z zakresu od 1 do m-1 (m) jest względnie pierwszych? (mają z m NWD=1)

(a,m)=1 – musi być liczbą względnie pierwszą. (musi być liczbą względnie pierwszą do m)

Jeśli m=p, to p-1 będzie liczbą względnie pierwszą. Ponieważ jeśli liczba jest m-pierwsza, to wszystkie liczby są dla niej względnie pierwsze, z wyjątkiem samej liczby m.

A co jeśli m jest liczbą złożoną?

Euler ustalił taki wzór, że istnieje pewien wzór, za pomocą którego można obliczyć liczbę liczb względnie pierwszych. (najłatwiej jest użyć brutalnej siły).

Wzór ten wyznacza się na podstawie rozwinięcia liczby m.

Rozkładamy to na proste czynniki.

Teraz musimy użyć tylko różnych czynników. Przykład:

m= 60 = 2*2*3*5; w formie kanonicznej - 2 2 *3*5: p 1 =2; p2 =3; p3 = 5;

Pomoc: Każdą liczbę złożoną można rozłożyć w sposób jednoznaczny.

Istnieje wzór, który uwzględnia wiele czynników, ale niektóre nie.

Jeżeli wszystkie czynniki są różne, to jest to jedna formuła, a jeśli jest kanoniczna, to można ją wyrazić za pomocą wykładników.

Rozważymy te dwie formuły.

Niech rozwinięcie będzie takie, że wszystkie czynniki będą różne.

I) W grę wchodzi sama liczba m, po której następuje powtarzające się wyrażenie:

W naszym przypadku:

Oznacza to, że od 1 do 60 jest 16 liczb względnie pierwszych z 60.

W naszym przypadku:

Zwróćmy uwagę na zastosowanie w kryptografii.

W kryptografii często konieczne jest obliczanie i szyfrowanie według pewnego modułu. Moduł może być złożony lub prosty. Gdy moduł jest liczbą złożoną, wówczas do jednoznacznego szyfrowania używana jest funkcja Eulera. Tam praca jest wykonywana ze zbiorem liczb, które są względnie pierwsze w zakresie określonym przez moduł.

Klasycznym (najważniejszym) zastosowaniem tej funkcji jest:

Mając daną liczbę naturalną a i daną liczbę m, niech będzie to m-złożona, naturalna, dodatnia. Jeśli te dwie liczby są względnie pierwsze, wówczas dla tej pary liczb obowiązuje następujące twierdzenie ( Twierdzenie Eulera) :

Bierzemy liczbę a, podnosimy ją do , pobieramy moduł

te. reszta będzie zawsze równa jeden.

Rozważaliśmy to, znajdując elementy odwrotne. Do tego twierdzenia powrócimy później.

Przypadek szczególny: m jest liczbą pierwszą (p), wówczas:

To jest małe twierdzenie Fermata, które Euler wzmocnił i rozszerzył na wszystkie funkcje Eulera.

Ten szczególny przypadek ma mniej ograniczeń niż twierdzenie Eulera. ponieważ tutaj automatycznie m i p są względnie pierwsze.

Powiedzmy, że jeśli a jest poza zakresem (a>m),

jeśli a i m są względnie pierwsze, to będzie to prawdą również w tym przypadku.

A jeśli m jest liczbą pierwszą (p), to a nie powinno być podzielne przez p. Te. jeśli a jest podzielne przez p, to nie odpowiada to już definicji liczb względnie pierwszych.

Stan

Znany w teorii liczb Funkcja Eulera$latex \varphi(n)$ to liczba liczb mniejszych niż $latex n$ i względnie pierwszych. Przypomnijmy, że dwie liczby są względnie pierwsze, jeśli nie mają wspólnych dzielników innych niż jeden.

Rozszerzmy koncepcję funkcji Eulera na ciągi znaków. Niech $lateks s$ będzie niepustym ciągiem znaków nad alfabetem ($lateks a$ .. $lateks z$), a $lateks k$ będzie dodatnią liczbą całkowitą. Wtedy $latex s \cdot k$ z definicji jest ciągiem $latex t = \underbrace(s \circ s \circ \ldots \circ s)_(\text(k))$ (połączenie $latex s$ z sam $ lateks k$ razy). W tym przypadku powiemy, że ciąg $latex s$ to rozdzielacz stringi $lateks t$. Na przykład „ab” jest dzielnikiem ciągu „ababab”.

Nazwiemy dwa niepuste ciągi $latex s$ i $latex t$ wzajemnie pierwsze, jeśli nie ma ciągu $latex u$ takiego, który byłby dzielnikiem zarówno $latex s$, jak i $latex t$. Wtedy funkcja Eulera $latex \varphi(s)$ dla łańcucha $latex s$ z definicji jest liczbą niepustych ciągów znaków w tym samym alfabecie ($latex a$ .. $latex z$), mniejszą niż $latex s $ długości i wzajemnie się z nią łatwo.

Dane wejściowe

Plik wejściowy zawiera ciąg znaków $latex s$ o długości od $latex 1$ do $latex 10^5$ włącznie, składający się z małych liter łacińskich.

Wyjście

Oblicz wartość $latex \varphi(s)$ i wypisz pojedynczą liczbę - resztę jej dzielenia przez $latex 1000000007 (10^9 + 7)$.

Rozwiązanie

Oczywiście, gdy ciąg $latex s$ o długości $latex n$ nie ma innych dzielników niż on sam, każdy ciąg o długości mniejszej niż $latex n$ będzie względnie pierwszy do $latex s$. Następnie wystarczy policzyć liczbę wszystkich możliwych ciągów o długości od $latex 1$ do $latex n-1$ włącznie. Dla niektórych $latex k$ liczba linii o tej długości będzie równa $latex 26^k$. Następnie liczba $latex m$ wszystkich możliwych ciągów o długości od $latex 1$ do $latex n-1$ zostanie obliczona przy użyciu następującego wzoru: $latex m=\sum\limits_(k=1)^(n -1) 26^ tys. $.

Rozważmy teraz przypadek, gdy ciąg ma dzielniki. Ponieważ ciąg $lateks s $ w tym przypadku jest konkatenacją pewnej liczby identycznych ciągów o mniejszej długości, znajdziemy właśnie ten podciąg, który jest minimalnym (najkrótszym) dzielnikiem ciągu $lateks s $. W tym celu użyjemy funkcji prefiksu. Zwraca wektor wartości $latex pi$ dla wszystkich podciągów ciągu $latex s$, które są przedrostkami $latex s$, gdzie wartość jest maksymalną długością przedrostka ciągu pasującego do jego sufiksu. Wtedy $latex n-1$-te miejsce wektora $latex pi$ będzie zawierać długość największego przedrostka ciągu $latex s$, a pozostały „kawałek” ciągu $latex s$ będzie reprezentował minimum dzielnik.

Pozostaje obliczyć liczbę linii, które nie są względnie pierwsze do $latex s$. Niech k będzie długością minimalnego dzielnika $latex s$. Wtedy wszystkie ciągi będące konkatenacjami tego dzielnika nie będą względnie pierwsze do $latex s$. Aby obliczyć ich liczbę, wystarczy podzielić długość pierwotnego ciągu przez k, ale wynik będzie o jeden mniejszy, ponieważ formuła ta uwzględnia również sam ciąg $latex s$ jako swój własny dzielnik.

Aby uzyskać ostateczną odpowiedź na problem, pozostaje odjąć od całkowitej liczby linii liczbę linii, które nie są względnie pierwsze z $latex s$.

Testy

№	Dane wejściowe	Wyjście
1	aa	25
2	abab	18277
3	abcdefgh	353082526
4	aaaaaa	321272406
5	aaaaaa	321272406

Kod programu

#włączać #włączać używając przestrzeni nazw std ; stała int MOD = 1e9 + 7 ; wektor< int >funkcja_przedrostka (string s) ( int n = s . długość(); wektor< int >szpilka); pi[0] = 0; for (int i = 1 ; tj< n ; i ++ ) { int j = pi [ i - 1 ] ; podczas gdy (j > 0 && s [ ja ] != s [ jot ] ) jot = pi [ jot - 1 ] ; jeśli (s [ ja ] == s [ jot ] ) j++; pi[i] = j; zwróć pi; int główna()( ciąg znaków ; cin >> s; int n = s . długość(); długi długi mul = 26, ans = 0; for (int i = 1 ; tj< n ; i ++ , mul *= 26 , mul %= MOD )

Funkcja zeta Riemanna jest jednym z najsłynniejszych wzorów w czystej matematyce i jest powiązana ze słynnym nierozwiązanym problemem matematycznym, czyli hipotezą Riemanna. Kalkulator funkcji zeta umożliwia obliczenie jej wartości dla argumentów z zakresu od zera do 1.

Odniesienie historyczne

Historia funkcji zeta Riemanna rozpoczyna się od odkrytego przez pitagorejczyków szeregu harmonicznego, który wygląda następująco:

1 + 1/2 + 1/3 + 1/4 + 1/5 ... 1/n

Seria wzięła swoją nazwę od stwierdzenia, że ​​struna podzielona na dwie, trzy lub więcej produkuje dźwięki sugerujące matematyczną harmonię. Im większa liczba członków szeregu harmonicznego, tym większa jest jego wartość. W ścisłym języku matematycznym oznacza to, że szereg jest rozbieżny i dąży do nieskończoności.

Słynny matematyk Leonhard Euler pracował z szeregami harmonicznymi i wyprowadził wzór na określenie sumy danej liczby wyrazów ciągu. W trakcie swojej pracy zainteresował się inną serią, znaną od czasów starożytnych, a dziś noszącą imię Eulera. Ułamki szeregu Eulera w mianownikach zawierają kwadraty, a pierwsze wyrazy ciągu wyglądają następująco:

1 + 1/4 + 1/9 + 1/16 + 1/25... 1/n 2

Jednak zaskakujące jest to, że wraz ze wzrostem liczby wyrazów w szeregu suma wyrażenia asymptotycznie zbliża się do pewnej wartości. W rezultacie szereg jest zbieżny, a jego wartość dąży do stałej równej (Pi 2)/6 lub 1,64488. Jeśli wstawimy kostki do mianowników:

1 + 1/8 + 1/27 + 1/64 + 1/125... 1/n 3

następnie szereg ponownie jest zbieżny, ale do wartości 1,20205. Ogólnie rzecz biorąc, szereg potęgowy możemy przedstawić jako funkcję zeta postaci:

Z(s) = 1 + 1/2 s + 1/3 s + 1/4 s + 1/5 s

Wraz ze wzrostem stopnia i liczby wyrazów szeregu wartość funkcji będzie dążyć do jedności i dla stopni powyżej 30 wyrażenie Z(s) = 1 zatem taki szereg jest zbieżny. Obliczenie wartości szeregu dla 0>s>1 pokazuje, że we wszystkich tych przypadkach funkcja ma różne wartości, a suma wyrazów szeregu stale rośnie w miarę zbliżania się do nieskończoności, zatem szereg jest rozbieżny.

W szeregu harmonicznym wykładnik jest równy jeden i szereg jest również rozbieżny. Jednakże, gdy tylko s przyjmie wartość większą niż jeden, szereg jest zbieżny. Jeśli jest mniejsza, to jest rozbieżna. Wynika z tego, że szereg harmoniczny leży ściśle na granicy zbieżności.

Funkcja zeta Riemanna

Euler pracował z potęgami całkowitymi, ale Bernhard Riemann rozszerzył swoje rozumienie funkcji na liczby rzeczywiste i zespolone. Złożona analiza pokazuje, że funkcja zeta ma nieskończoną liczbę zer, czyli nieskończoną liczbę wartości s, dla których Z(s) = 0. Wszystkie nietrywialne zera są liczbami zespolonymi postaci a + bi, gdzie i jest jednostką urojoną. Nasz kalkulator online pozwala operować wyłącznie rzeczywistymi argumentami, zatem wartość Z(s) będzie zawsze większa od zera.

Przykładowo Z(2) = (Pi 2)/6 i wynik ten obliczył sam Euler. Wszystkie wartości funkcji dla argumentów parzystych zawierają Pi, jednak obliczenia dla liczb nieparzystych są zbyt skomplikowane, aby przedstawić wynik w postaci zamkniętej.

Hipoteza Riemanna

Leonhard Euler użył funkcji Z(s) podczas pracy z twierdzeniem o rozkładzie liczb pierwszych. Riemann wprowadził tę funkcję również w swojej pracy doktorskiej. W pracy zaproponowano metodę pozwalającą policzyć liczbę liczb pierwszych (podzielnych tylko przez siebie i przez jeden), które występują w szeregu do pewnej granicy. Podczas pracy Riemann zauważył, że wszystkie nietrywialne (to znaczy zespolone) zera funkcji zeta mają część rzeczywistą równą 1/2. Naukowcowi nigdy nie udało się wyprowadzić rygorystycznego dowodu na to twierdzenie, które z czasem stało się Świętym Graalem czystej matematyki.

Dokładny dowód hipotezy Riemanna może rzucić światło na rozkład liczb pierwszych, z którym społeczność matematyczna zmaga się od czasów starożytnych. Do chwili obecnej obliczono ponad półtora miliarda nietrywialnych zer funkcji zeta, które rzeczywiście znajdują się na prostej x = 1/2. Jednak ani teoria rozkładu liczb niepodzielnych, ani hipoteza Riemanna nie są obecnie rozwiązane.

Nasz kalkulator pozwala obliczyć wartość Z(s) dla dowolnego rzeczywistego s. Można używać wartości argumentów całkowitych i ułamkowych, dodatnich i ujemnych. W tym przypadku dodatnie liczby całkowite zawsze dadzą wynik bliski lub równy jedności. Wartości 0>s>1 zawsze powodują, że funkcja zeta przyjmuje różne wartości. Ujemne wartości s zamieniają szereg w:

1 + 1 s + 2 s + 3 s + 4 s ...

Oczywiste jest, że dla dowolnego negatywu szereg jest rozbieżny i gwałtownie pędzi do nieskończoności. Rozważmy przykłady liczbowe wartości Z(s).

Przykłady obliczeń

Sprawdźmy nasze obliczenia. W obliczeniach program wykorzystuje 20 tysięcy wyrazów szeregu. Za pomocą kalkulatora wyznaczamy wartości Z(s) dla argumentów dodatnich większych niż jeden:

• dla s = 1 wyrażenie Z(s) = 10,48;
• przy s = 1,5 wyrażenie Z(s) = 2,59;
• przy s = 5 wyrażeniem jest Z(s) = 1,03.

Obliczmy wartości funkcji zeta dla 0>s>1:

• przy s = 0,9 wyrażeniem jest Z(s) = 17,49.
• przy s = 0,5 wyrażenie Z(s) = 281,37;
• dla s = 0,1 wyrażeniem jest Z(s) = 8253,59.

Obliczmy wartości Z(s) dla s<0:

• przy s = -0,5 wyrażenie to Z(s) = 1 885 547.
• dla s = -1 wyrażenie Z(s) = 199 999 000;
• dla s = -3 wyrażenie Z(s) = 39 996 000 100 000 010;

Jest oczywiste, że przy niewielkiej zmianie s od jedności w górę funkcja rozpoczyna powolny, ale stały ruch w kierunku Z(s) = 1. Kiedy argument zmienia się z jedności w dół, funkcja przyjmuje coraz większe wartości i pędzi do nieskończoności.

Wniosek

Funkcja zeta Riemanna i związana z nią hipoteza to jeden z najpopularniejszych otwartych problemów współczesnej matematyki, z rozwiązaniem którego naukowcy zmagają się od ponad 150 lat. Udowodnienie Hipotezy Riemanna umożliwi matematykom dokonanie znaczących przełomów w teorii liczb, co niewątpliwie doprowadzi społeczność naukową do jeszcze większych odkryć.

A jego wartości leżą w zbiorze liczb naturalnych.

Jak wynika z definicji, aby policzyć należy przejść przez wszystkie liczby od do i dla każdej sprawdzić, czy ma ona wspólne dzielniki z, a następnie policzyć, ile liczb okazało się względnie pierwszych z Ta procedura jest bardzo pracochłonna dlatego do obliczeń stosuje się inne metody, które opierają się na określonych właściwościach funkcji Eulera.

Tabela po prawej stronie pokazuje pierwsze 99 wartości funkcji Eulera. Analizując te dane widać, że wartość nie przekracza, a jeśli jest to proste, jest dokładnie jej równa. Zatem, jeśli narysujesz linię prostą we współrzędnych, wartości będą leżeć albo na tej linii prostej, albo pod nią. Również patrząc na wykres podany na początku artykułu i na wartości w tabeli, możemy założyć, że istnieje linia prosta przechodząca przez zero, która ogranicza wartości od dołu. Okazuje się jednak, że taka linia prosta nie istnieje. Oznacza to, że niezależnie od tego, jak płaską narysujemy linię prostą, zawsze znajdzie się liczba naturalna leżąca poniżej tej prostej. Kolejną interesującą cechą wykresu jest obecność linii prostych, wzdłuż których skupiają się wartości funkcji Eulera. Na przykład oprócz linii, na której leżą wartości gdzie - liczba pierwsza, identyfikowana jest linia prosta, w przybliżeniu odpowiadająca wartościom, gdzie - liczba pierwsza.

Zachowanie funkcji Eulera omówiono bardziej szczegółowo w tej sekcji.

Pierwsze 99 wartości funkcji Eulera (sekwencja A000010 w OEIS)

	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
0+		1	1	2	2	4	2	6	4	6
10+	4	10	4	12	6	8	8	16	6	18
20+	8	12	10	22	8	20	12	18	12	28
30+	8	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

Multiplikatywność funkcji Eulera

Jedną z głównych właściwości funkcji Eulera jest jej multiplikatywność. Własność ta została ustalona przez Eulera i jest sformułowana następująco: dla dowolnych liczb względnie pierwszych i

Dowód multiplikatywności

Aby udowodnić multiplikatywność funkcji Eulera, wymagane jest następujące twierdzenie pomocnicze.

Twierdzenie 1. Pozwól i przeprowadź przez zredukowany układ reszt modulo, przechodząc przez zredukowany układ reszt modulo Następnie przeprowadź przez zredukowany układ reszt modulo Dowód. Jeśli zatem podobnie Dlatego istnieją nieporównywalne liczby modulo, które tworzą zredukowany układ reszt modulo

Teraz możemy udowodnić główne stwierdzenie.

Twierdzenie 2. Funkcja Eulera jest multiplikatywna. Dowód. Jeżeli wówczas, zgodnie z Twierdzeniem 1, przebiega przez zredukowany układ reszt modulo gdy i przebiega przez zredukowane układy reszt modulo i odpowiednio. Ponadto: Dlatego liczby, które są mniejsze od liczby i są z nią względnie pierwsze, są najmniejszymi dodatnimi resztami spośród wartości, dla których są względnie pierwsze i względnie pierwsze. Wynika z tego

Funkcja Eulera liczby pierwszej

co wynika z definicji. Rzeczywiście, jeśli jest liczbą pierwszą, to wszystkie liczby mniejsze niż , są z nią względnie pierwsze i jest ich dokładnie kilka.

Aby obliczyć funkcję Eulera liczby pierwszej, użyj następującego wzoru:

Równość tę uzasadnia się następująco. Policzmy liczbę liczb od do, które nie są względnie pierwsze do . Wszystkie są oczywiście wielokrotnościami, to znaczy mają postać: Suma takich liczb Dlatego liczba liczb względnie pierwszych jest równa

Funkcja Eulera liczby naturalnej

Obliczenia dowolnej liczby naturalnej opierają się na multiplikatywności funkcji Eulera, wyrażeniu i podstawowym twierdzeniu arytmetyki. Dla dowolnej liczby naturalnej wartość jest reprezentowana jako:

gdzie jest liczbą pierwszą i przebiega przez wszystkie wartości biorące udział w rozkładzie na czynniki pierwsze.

Dowód

gdzie jest największym wspólnym dzielnikiem i Ta właściwość jest naturalnym uogólnieniem multiplikatywności.

Dowód uogólnionej multiplikatywności

Niech wtedy i w ogólnym przypadku i Dlatego możemy napisać:

Tutaj pierwsze dzielniki są także dzielnikami, a ostatnie dzielniki są dzielnikami. Zapiszmy to:

Ze względu na multiplikatywność funkcji Eulera, a także uwzględnienie wzoru

gdzie jest liczba pierwsza, otrzymujemy:

Pierwsza linia jest zapisana w drugiej - a trzecia może być przedstawiona jako Dlatego:

Niektóre szczególne przypadki:

Twierdzenie Eulera

Własnością najczęściej wykorzystywaną w praktyce jest własność ustalona przez Eulera:

jeśli i są względnie pierwsze.
Własność ta, zwana twierdzeniem Eulera, wynika z twierdzenia Lagrange'a i faktu, że φ( M) jest równy rządowi grupy elementów odwracalnych reszty pierścienia modulo M.
Jako następstwo twierdzenia Eulera można otrzymać małe twierdzenie Fermata. Aby to zrobić, musisz wziąć nie dowolny, ale prosty. Następnie:

Ten ostatni wzór znajduje zastosowanie w różnych testach pierwszości.

Inne właściwości

Opierając się na reprezentowalności iloczynu Eulera, łatwo jest uzyskać następujące przydatne stwierdzenie:

Każdą liczbę naturalną można przedstawić jako sumę wartości funkcji Eulera z jej dzielników:

Sumę wszystkich liczb mniejszych od danej liczby i względnie pierwszych względem niej wyraża się funkcją Eulera:

Wiele znaczeń

Badanie struktury zbioru wartości funkcji Eulera jest osobnym złożonym zadaniem. Poniżej prezentujemy tylko część wyników uzyskanych w tym obszarze.

Dowód (funkcja Eulera przyjmuje tylko wartości parzyste dla n > 2)

Rzeczywiście, jeśli jest prostym nieparzystym, a potem parzystym. Równość implikuje stwierdzenie.

W rzeczywistej analizie często pojawia się problem znalezienia wartości argumentu, biorąc pod uwagę wartość funkcji, lub innymi słowy problem znalezienia funkcji odwrotnej. Podobny problem można postawić dla funkcji Eulera. Należy jednak o tym pamiętać

W związku z tym potrzebne są specjalne metody analizy. Przydatnym narzędziem do badania przedobrazu jest następujące twierdzenie:

Jeśli następnie

Dowód twierdzenia

Oczywiście, jeśli wtedy Z drugiej strony, jeśli i wtedy Jednakże, jeśli wtedy Zatem Zatem

Twierdzenie to pokazuje, że obrazem wstępnym elementu jest zawsze zbiór skończony. Daje także praktyczny sposób na znalezienie prototypu. Do tego potrzebujesz

Może się okazać, że we wskazanym przedziale nie ma takiej liczby, aby w tym przypadku obraz wstępny był zbiorem pustym.
Warto zaznaczyć, że do obliczeń trzeba znać rozkład na czynniki proste, co w przypadku dużych jest zadaniem trudnym obliczeniowo. Następnie trzeba raz obliczyć funkcję Eulera, co jest również bardzo pracochłonne w przypadku dużych liczb. Dlatego znalezienie obrazu wstępnego jako całości jest zadaniem trudnym obliczeniowo.

Przykład 1 (Obliczanie obrazu wstępnego)

Znajdźmy przedobraz 4. Dzielnikami 4 są liczby 1, 2 i 4. Dodając po jednym do każdej z nich, otrzymamy 2, 3, 5 - liczby pierwsze. Obliczamy

Aby znaleźć zapowiedzi liczby 4, wystarczy wziąć pod uwagę liczby od 5 do 15. Po wykonaniu obliczeń otrzymujemy:

Przykład 2 (Nie wszystkie liczby parzyste są wartościami funkcji Eulera)

Na przykład nie ma takiej liczby, która byłaby:

W rzeczywistości dzielnikami liczby 14 są 1, 2, 7 i 14. Dodając po jednym, otrzymamy 2, 3, 8, 15. Spośród nich tylko dwie pierwsze liczby są liczbami pierwszymi. Dlatego

Po przejrzeniu wszystkich liczb od 15 do 42 łatwo to sprawdzić

Relacje asymptotyczne

Najprostsze nierówności

dla wszystkich oprócz i dla dowolnego związku

Porównanie φ( N) Z N

Kolejna relacja wartości

gęsty w zbiorze liczb rzeczywistych dodatnich. ciasno w przerwie

Asymptotyka sum

Wynika z tego, że średni porządek ( język angielski) funkcji Eulera jest równy Wynik ten jest interesujący, ponieważ pozwala nam obliczyć prawdopodobieństwo zdarzenia, że ​​dwie losowo wybrane liczby naturalne będą względnie pierwsze. Mianowicie, prawdopodobieństwo to jest równe

Rząd funkcji Eulera

gdzie jest stałą Eulera-Mascheroniego. dla wszystkich, z jednym wyjątkiem w tym przypadku, należy zastąpić To jest jedno z najdokładniejszych dolnych szacunków Jak zauważa Paulo Ribenboim ( język angielski) odnośnie dowodu tej nierówności: „Metoda dowodu jest o tyle interesująca, że ​​nierówność ustala się najpierw przy założeniu, że hipoteza Riemanna jest prawdziwa, a następnie przy założeniu, że nie jest ona prawdziwa”.

Połączenie z innymi funkcjami

Funkcja Möbiusa

gdzie jest funkcją Möbiusa.

Seria Dirichleta

Seria Lamberta

Największy wspólny dzielnik

Część rzeczywista: W przeciwieństwie do iloczynu Eulera, obliczenia przy użyciu tych wzorów nie wymagają znajomości dzielników

Zastosowania i przykłady

Funkcja Eulera w RPA

W oparciu o algorytm zaproponowany w 1978 roku przez Ronalda Rivesta, Adi Shamira i Leonarda Adlemana zbudowano pierwszy system szyfrowania klucza publicznego, nazwany od pierwszych liter nazwisk autorów – systemem RSA. O sile kryptograficznej tego systemu decyduje złożoność faktoringu całości N-cyfrowy numer. Kluczową rolę w algorytmie RSA pełni funkcja Eulera, której właściwości umożliwiają zbudowanie systemu kryptograficznego klucza publicznego.

Na etapie tworzenia pary kluczy prywatnych i publicznych jest ona obliczana

gdzie i są pierwsze. Następnie wybierane są tak losowe liczby, że

Wiadomość jest następnie szyfrowana kluczem publicznym odbiorcy:

Następnie tylko właściciel tajnego klucza będzie mógł odszyfrować wiadomość

Poprawność ostatniego stwierdzenia opiera się na twierdzeniu Eulera i chińskim twierdzeniu o resztach.

Dowód prawidłowego odszyfrowania

Ze względu na wybór numerów na etapie tworzenia klucza

Jeżeli zatem, biorąc pod uwagę twierdzenie Eulera,

W ogólnym przypadku mogą mieć wspólne dzielniki, ale deszyfrowanie nadal okazuje się prawidłowe. Niech Zgodnie z chińskim twierdzeniem o resztach:

Podstawiając otrzymujemy tożsamość

Stąd,

Obliczanie elementu odwrotnego

Funkcji Eulera można użyć do obliczenia odwrotności elementu modulo mnożenia w następujący sposób:

Jeśli

Przykład (obliczanie elementu odwrotnego)

Znajdźmy, to znaczy, liczbę taką, że

Oczywiście i nie mają wspólnych dzielników innych niż jeden, a liczba jest pierwsza i

Dlatego wygodnie jest zastosować wzór podany powyżej:

Łatwo sprawdzić, co się naprawdę dzieje

Uwaga 1 (Oszacowanie złożoności obliczeniowej)

Ogólnie rzecz biorąc, do obliczania odwrotności algorytm Euklidesa jest szybszy niż przy użyciu twierdzenia Euklidesa, ponieważ złożoność bitowa obliczeń przy użyciu algorytmu Euklidesa jest rzędu wielkości, podczas gdy obliczenia przy użyciu twierdzenia Eulera wymagają kolejności operacji bitowych, gdzie Jednak , w przypadku, gdy rozkładem liczb pierwszych są znane czynniki, złożoność obliczeniową można zmniejszyć stosując algorytmy szybkiego potęgowania: algorytm Montgomery'ego lub algorytm kwadratu i mnożenia.

Uwaga 2 (Brak rozwiązania w przypadku (a, n) ≠ 1)

Jeśli wtedy nie istnieje odwrotność elementu, czyli inaczej równanie

nie ma rozwiązań na zbiorze liczb naturalnych.
Dowód. W rzeczywistości, powiedzmy

i rozwiązanie istnieje. Następnie z definicji największego wspólnego dzielnika

I

więc możemy napisać:

Gdzie

lub zmieniając warunki,

Po lewej stronie znajduje się liczba całkowita niezerowa, co oznacza, że ​​po prawej stronie musi znajdować się liczba całkowita niezerowa, więc jest to konieczne

co jest sprzeczne z założeniem.

Liniowe rozwiązanie porównawcze

Do rozwiązania porównania można zastosować metodę obliczania elementów odwrotnych

Jeśli

Przykład (rozwiązanie porównania liniowego)

Spójrzmy na porównanie

Możesz więc użyć tej formuły:

Sprawdzamy to przez podstawienie

Uwaga (Niejednoznaczność rozwiązania lub brak rozwiązania w przypadku (a, n) ≠ 1)

Jeżeli , porównanie albo ma więcej niż jedno rozwiązanie, albo nie ma żadnego rozwiązania. Jak łatwo jest zobaczyć porównanie

nie ma rozwiązań na zbiorze liczb naturalnych. Jednocześnie porównanie

ma dwa rozwiązania

Obliczanie reszty z dzielenia

Funkcje Eulera pozwalają obliczyć resztę z dzielenia dużych liczb.

Przykład 1 (ostatnie trzy cyfry w zapisie dziesiętnym)

Znajdźmy trzy ostatnie cyfry w zapisie dziesiętnym liczby. Zauważmy to

dostajemy

Przechodząc teraz z modułu do modułu mamy:

Dlatego zapis dziesiętny liczby kończy się na

Przykład 2 (reszta z dzielenia przez 1001)

Znajdźmy resztę dzielenia przez Łatwo to zobaczyć

Dlatego korzystając z multiplikatywności funkcji Eulera i równości

dla każdego prostego

dostajemy

Znalezienie rzędu grupy multiplikatywnej pierścienia resztowego

Grupa multiplikatywna pierścienia reszt modulo składa się z klas reszt.
Przykład. Dany układ reszt modulo 14 składa się z klas reszt:

Zastosowania w teorii grup

Liczba elementów generujących w skończonej grupie cyklicznej jest równa . W szczególności, jeśli grupa multiplikatywna pierścienia reszt modulo jest grupą cykliczną - co jest możliwe tylko wtedy, gdy , gdzie jest liczbą pierwszą nieparzystą i liczbą naturalną - wówczas istnieją generatory grup (pierwiastki pierwotne modulo).
Przykład. Grupa rozważana w powyższym przykładzie ma generator: i

Nie rozwiązane problemy

Problem Lehmera

Jak wiadomo, jeśli jest liczbą pierwszą, to w 1932 r. Lemaire ( język angielski) zastanawiał się, czy istnieje taka liczba złożona, która jest dzielnikiem rozważanym przez Lemera równaniem

gdzie jest liczbą całkowitą. Udało mu się udowodnić, że jeśli jest rozwiązaniem równania, to albo jest liczbą pierwszą, albo jest iloczynem siedmiu lub więcej różnych liczb pierwszych. Później udowodniono inne mocne stwierdzenia. Tak więc w 1980 roku Cohen i Hagis pokazali, że jeśli złożenie i dzieli, to gdzie jest liczba dzielników pierwszych. W 1970 r. Lieuwens ustalił, że jeśli to wtedy, a Wall w 1980 r. udowodnił, że jeśli wtedy

Funkcja Eulera (n) jest zdefiniowana dla wszystkich dodatnich liczb całkowitych n i reprezentuje liczbę liczb w szeregu

0,1,…n-1(2.1.)

względnie pierwsza do n

Twierdzenie 2.1. niech n=…(2.2.)

Kanoniczne rozwinięcie liczby n, to mamy

lub również

(n)n=(-) (-)...(-) (2.4.)

w szczególności będziemy mieli

(p 2)= p 2 - p -1, (p)=p-1 (2.5.)

Rzeczywiście, zastosujmy Twierdzenie 1.8. W tym przypadku definiujemy liczby?, f w następujący sposób: niech x przebiega przez liczby szeregu (2.1); każda wartość x jest powiązana z liczbą? =(x, n) i liczby x=1.

Następnie S / zamieni się w liczbę wartości =(x, n) równą 1, tj. Zajazd). AS re

Zamieni się w liczbę wartości =(x, n) wielokrotności d.

Ale ( x,n) może być wielokrotnością d tylko wtedy, gdy d jest dzielnikiem n. Jeżeli ten warunek jest spełniony, S d stanie się liczbą wartości x będących wielokrotnościami d, tj. V.

Stąd ze względu na (***) wynika wzór (2.3.), a z tego ostatniego ze względu na (2.2.)

Następuje wzór (2.4.).

Multiplikatywność funkcji Eulera i jej związek z innymi funkcjami multiplikatywnymi.

Twierdzenie 2.2. (n) - multiplikatywny, tj.

(n 1 n 2) = (n 1)(n 2), gdzie (n 1, n 2) = 1

Podajmy dwa dowody tego twierdzenia:

1. Niech x przyjmie wartość 1, 2,…, (n2), tworząc zredukowany układ reszt modulo n2, a y przyjmie wartości S1, S2,…, S(n1), tworząc zredukowany układ reszt moduł n1. Skomponujmy wszystkie możliwe liczby postaci n11 +n2sj, odpowiadające umieszczonym parom j sj, liczba takich liczb będzie równa

Z drugiej strony, ponieważ (n 1, n 2) = 1, liczby te tworzą zredukowany układ reszt modulo n 1 n 2, tj. liczba takich liczb musi być równa (n 1 n 2). Iloczyn (n 1) (n 2) i (n 1 n 2) wyrażają tę samą wielkość, tj.

(n 1 n 2) = (n 1) (n 2)

• 2. Zróbmy tabelę:
• 1,2,3,…,

n 2 +1, n 2 +2, n 2 +3,…, 2 n 2

2n 2 +1,2n 2 +2,2n 2 +3,…, 3 n 2 (2.7)

…………………………………………

(n 1 -1) n 2 +1, (n 1 -1) n 2 +2, (n 1 -1) n 2 +3,…, n 1 n 2

i określ liczbę liczb w tej tabeli, które są względnie pierwsze względem n 1 n 2

(kn 2 +, n 2) = 1,

wtedy i tylko wtedy, gdy (, n 2)=1

Zatem liczby względnie pierwsze do n 2, a jeszcze bardziej do n 1 n 2, mogą być tylko liczbami w kolumnach takimi, że (, n 2) = 1, gdzie 1 n 2 liczba takich kolumn jest z definicji równa (n 2).

Każda taka kolumna składa się z liczb:

N 2 +, 2n 2 +,…, (n 1 -1) n 2 + (2.8.)

te. z liczb postaci n 2 x+, przez które przechodzi pełny układ reszt modulo n. Ponieważ (n 1 n 2) = 1, liczby (2.8.) również tworzą kompletny układ reszt modulo n. I dlatego (2.8.) zawiera (n 1) liczby względnie pierwsze do n 2. Mamy zatem w tabeli (2.7.) (n 2) kolumny liczb względnie pierwszych do n 2, a każda taka kolumna zawiera (n 1) liczby względnie pierwsze do n 1. Jeśli liczba jest odwrotna z n 2 i z n 1, to jest odwrotna z n 1 n 2. Zatem tabela (2.7.) zawiera (n ​​1) (n 2) liczby względnie pierwsze do n 1 n 2.

Natomiast w tabeli tej znajdują się wszystkie liczby od 1 do n 1 n 2, a zatem istnieją (n 1 n 2) liczby względnie pierwsze do n 1 n 2, czyli:

(n 1) (n 2) = (n 1 n 2)

Twierdzenie 2.3. Gdy n1 (n)=n

Znak p oznacza tutaj, że czynniki iloczynu są brane pod uwagę przy wszystkich możliwych pierwszych dzielnikach liczby n. Dowód: dowolne n1

można przedstawić w formie kanonicznej