Eulerfunktionen är en multiplikativ aritmetisk funktion vars värde är lika med antalet naturliga tal som är mindre och samprimat med det [1] .
Till exempel, för talet 36 finns det 12 mindre och samprimtal (1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35), så .
Uppkallad efter Euler , som först använde den 1763 i sitt arbete med talteorin för att bevisa Fermats lilla teorem , och sedan för att bevisa ett mer allmänt uttalande - Eulers teorem . Funktionen användes senare av Gauss i hans Arithmetical Investigations , publicerad 1801. Gauss introducerade nu standardnotationen [2] .
Euler-funktionen finner tillämpning i frågor som rör teorin om delbarhet och rester (se modulo-jämförelse ), talteori , kryptografi . Euler-funktionen spelar en nyckelroll i RSA-algoritmen [3] .
+0 | +1 | +2 | +3 | +4 | +5 | +6 | +7 | +8 | +9 | |
---|---|---|---|---|---|---|---|---|---|---|
0+ | ett | ett | 2 | 2 | fyra | 2 | 6 | fyra | 6 | |
10+ | fyra | tio | fyra | 12 | 6 | åtta | åtta | 16 | 6 | arton |
20+ | åtta | 12 | tio | 22 | åtta | tjugo | 12 | arton | 12 | 28 |
30+ | åtta | trettio | 16 | tjugo | 16 | 24 | 12 | 36 | arton | 24 |
40+ | 16 | 40 | 12 | 42 | tjugo | 24 | 22 | 46 | 16 | 42 |
50+ | tjugo | 32 | 24 | 52 | arton | 40 | 24 | 36 | 28 | 58 |
60+ | 16 | 60 | trettio | 36 | 32 | 48 | tjugo | 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 |
Eulerfunktionen visar hur många naturliga tal från intervallet c som bara har en gemensam divisor - en. Euler-funktionen är definierad på mängden naturliga tal , och dess värden ligger i mängden naturliga tal.
Som följer av definitionen måste du för att beräkna , gå igenom alla siffror från till , och för varje kontrollera om den har gemensamma divisorer med , och sedan beräkna hur många tal som visade sig vara coprime med . Denna procedur för stora antal är mycket tidskrävande, därför används andra metoder för beräkning , som är baserade på de specifika egenskaperna hos Euler-funktionen.
Tabellen till höger visar de första 99 värdena av Euler-funktionen. Genom att analysera dessa data kan du se att värdet inte överstiger , och är exakt lika med det if - prime. Således, om en linje ritas i koordinater , kommer värdena att ligga antingen på denna linje eller under den. Om vi också tittar på grafen i början av artikeln och värdena i tabellen kan vi anta att det finns en rät linje som går genom noll, vilket begränsar värdena underifrån. Det visar sig dock att en sådan linje inte finns. Det vill säga, oavsett hur ytlig en rät linje vi drar, kommer det alltid att finnas ett naturligt tal som ligger under denna räta linje. En annan intressant egenskap i grafen är närvaron av några raka linjer längs vilka värdena för Euler-funktionen är koncentrerade. Så, till exempel, förutom linjen som värdena ligger på , där är ett primtal, urskiljs en linje som ungefär motsvarar , på vilken värdena faller , där är ett primtal.
Euler-funktionens beteende diskuteras mer i detalj i avsnittet #Asymptotiska relationer .
En av de viktigaste egenskaperna hos Euler-funktionen är dess multiplikativitet . Denna egenskap etablerades av Euler och är formulerad enligt följande: för alla samprimtal och [5]
Bevis på multiplikativitetFör att bevisa Eulerfunktionens multiplikativitet behöver vi följande hjälpsats [6] .
Sats 1. Låt och kör genom hela systemet av rester modulo , medan det går genom hela systemet av rester modulo . Då bildar siffrorna ett komplett system av rester modulo . Bevis. Om en sedan det är därför likaså Därför finns det ojämförliga modulo- tal som bildar ett komplett system av modulo-rester .Nu kan vi bevisa huvudpåståendet [7] .
Sats 2. Eulerfunktionen är multiplikativ. Bevis. Om , sedan genom sats 1 går genom det reducerade systemet av rester modulo , när och körs genom de reducerade systemen av rester modulo och respektive. Också: Därför är tal som är mindre än ett tal och coprime till det de minsta positiva resterna bland värdena för vilka coprime till och coprime till . Därav följer detFör ett enkelt värde på Euler-funktionen ges av en explicit formel [8] :
som följer av definitionen. Faktum är att om är ett primtal, då är alla tal mindre än samprimtal till det, och det finns exakt ett av dem.
För att beräkna Euler-funktionen av potensen av ett primtal, använd följande formel [8] :
Denna jämlikhet motiveras enligt följande. Låt oss räkna antalet tal från till som inte är coprime till . Alla av dem är uppenbarligen multiplar , det vill säga de ser ut som: Totalt sådana tal . Därför är antalet siffror som primeras med lika med .
Beräkningen för en godtycklig naturlig baseras på multiplikativiteten av Euler-funktionen, uttrycket för , och även på aritmetikens grundläggande sats . För ett godtyckligt naturligt tal representeras värdet som [8] :
där är ett primtal och går igenom alla värden som är involverade i nedbrytningen till primtalsfaktorer.
BevisSom följer av aritmetikens grundläggande sats är alla naturliga tal unikt representerade i formen:
var är primtal och är naturliga tal.
Genom att använda Euler-funktionens multiplikativitet och uttrycket för får vi:
Applikationsexempel:
Euler-funktionen är en multiplikativ aritmetisk funktion , det vill säga
Det är viktigt här att den största gemensamma delaren och är lika med en. Det visar sig att det finns en generalisering av denna formel till fallet när och har andra gemensamma delare än enhet. Nämligen för alla naturliga och [9] :
var är den största gemensamma delaren och Denna egenskap är en naturlig generalisering av multiplikativitet.
Bevis på generaliserad multiplikativitetLåt då och i det allmänna fallet och Därför kan vi skriva:
Här är de första divisorerna också divisorer och de sista divisorerna är divisorer Låt oss skriva:
På grund av Euler-funktionens multiplikativitet, och även med hänsyn till formeln
var är ett primtal får vi:
Den första raden skrivs i den andra - och den tredje kan representeras som Därför:
Några speciella fall:
Egenskapen etablerad av Euler används oftast i praktiken :
om och är relativt prime .
Denna egenskap, som kallas Eulers sats , följer av Lagranges sats och det faktum att den är lika med ordningen för den multiplikativa gruppen av inverterbara element i restringen modulo .
Som en konsekvens av Eulers sats kan man få Fermats lilla sats . För att göra detta måste du ta inte godtyckligt utan enkelt. Sedan:
Den senare formeln finner användning i olika primatitetstester .
Baserat på hur Euler-produkten är representativ, är det lätt att få följande användbara uttalande:
Följande likhet [10] [11] är en konsekvens av Zsigmondys sats :
Vilket naturligt tal som helst kan representeras som summan av värdena för Euler-funktionen från dess naturliga delare [12] :
Summan av alla tal mindre än ett givet tal och relativt primtal till det uttrycks i termer av Euler-funktionen:
Studiet av strukturen för uppsättningen värden för Euler-funktionen är en separat svår uppgift. Endast några av de resultat som erhållits inom detta område presenteras här [13] .
I verklig analys uppstår ofta problemet med att hitta värdet av ett argument givet värdet av en funktion, eller, med andra ord, problemet med att hitta den inversa funktionen . Ett liknande problem kan uppstå för Euler-funktionen. Följande måste dock hållas i åtanke.
I detta avseende behövs speciella analysmetoder. Ett användbart verktyg för att studera förbilden är följande sats [14] .
Detta teorem visar att den omvända bilden av ett element alltid är en finit mängd. Det ger också följande praktiska sätt att hitta förbilden:
1) beräkna ; 2) beräkna för alla från halvintervallet ; 3) alla tal som bildar elementets omvända bild .Det kan visa sig att det inte finns något sådant nummer i det angivna intervallet att förbilden i detta fall är den tomma uppsättningen .
Det är värt att notera att för beräkningen måste du känna till nedbrytningen i primfaktorer, vilket för stora är en beräkningsmässigt svår uppgift. Sedan behöver du beräkna Euler-funktionen en gång, vilket också är väldigt tidskrävande för stora tal. Att hitta förbilden som helhet är därför ett beräkningsmässigt svårt problem.
Låt oss hitta förbilden av 4. Divisorerna för 4 är talen 1, 2 och 4. Lägger vi en till var och en av dem får vi 2, 3, 5 - primtal. Beräkna
För att hitta förbilden av 4 räcker det att överväga siffrorna från 5 till 15. Efter att ha gjort beräkningarna får vi:
Exempel 2 (Inte alla jämna tal är värden för Euler-funktionen)Det finns till exempel inget sådant nummer som det vill säga:
Delarna för 14 är faktiskt 1, 2, 7 och 14. Lägger vi till en vardera får vi 2, 3, 8, 15. Av dessa är endast de två första talen primtal. Det är därför
Efter att ha sorterat igenom alla siffror från 15 till 42 är det lätt att verifiera det
Baserat på den algoritm som föreslogs 1978 av Ronald Rivest , Adi Shamir och Leonard Adleman byggdes det första krypteringssystemet för offentliga nyckel, uppkallat efter de första bokstäverna i författarnas efternamn - RSA -systemet . Den kryptografiska styrkan hos detta system bestäms av komplexiteten i faktoriseringen av ett heltals -bittal. Nyckelrollen i RSA-algoritmen spelas av Euler-funktionen, vars egenskaper gör det möjligt att konstruera ett kryptografiskt system med publik nyckel [35] .
I stadiet för att skapa ett par hemliga och offentliga nycklar,
var och är enkla. Sedan väljs slumpmässiga tal så att
Meddelandet krypteras sedan med mottagarens publika nyckel:
Efter det kan bara ägaren av den hemliga nyckeln dekryptera meddelandet :
Riktigheten av det sista påståendet är baserat på Eulers sats och den kinesiska restsatsen .
DekrypteringsbevisPå grund av valet av nummer vid skapandet av nycklar
Om då, med hänsyn till Eulersatsen,
I det allmänna fallet, och kan ha gemensamma delare, men dekrypteringen visar sig fortfarande vara korrekt. Låt Enligt den kinesiska restsatsen:
Genom att ersätta får vi identiteten
Följaktligen,
Euler-funktionen kan användas för att beräkna inversen av ett element modulo , nämligen [36] :
omDenna formel följer av Eulers teorem :
Exempel (beräkning av omvänd element)Hitta , det vill säga ett antal sådant att
Uppenbarligen, och har inte gemensamma delare förutom en, , medan talet är primtal och
Därför är det bekvämt att använda formeln ovan:
Det är lätt att kontrollera vad som verkligen är
Anmärkning 1 (Uppskattning av beräkningskomplexitet)Generellt sett är den euklidiska algoritmen snabbare för beräkning av reciproka än att använda Eulers sats [37] , eftersom bitkomplexiteten för beräkningen med den euklidiska algoritmen är av ordning , medan beräkningen av Eulers sats kräver en ordning av bitoperationer, där dock , i fallet när det är känd faktorisering , kan beräkningskomplexiteten reduceras med hjälp av snabba exponentieringsalgoritmer : Montgomerys algoritm eller "kvadrat- och multiplicera" -algoritmen [38] .
Anmärkning 2 (Ingen lösning i fall ( a , n ) ≠ 1)Om då det inversa elementet inte existerar, eller med andra ord, ekvationen
har ingen lösning på mängden naturliga tal [39] .
Bevis. Sannerligen, antar
och lösningen finns. Då enligt definitionen av den största gemensamma divisorn
ochså du kan skriva:
vareller, ordna om villkoren,
Till vänster finns ett heltal som inte är noll, vilket betyder att det till höger måste finnas ett heltal som inte är noll, därför med behovet
vilket strider mot antagandet.
Metoden för att beräkna det inversa elementet kan användas för att lösa jämförelsen
Lösningen ges av formeln [37] :
om Exempel (Linjär jämförelselösning)Tänk på jämförelsen
Hur kan du använda denna formel:
Genom substitution ser vi till det
Anmärkning (Icke-unikhet hos en lösning eller frånvaro av en lösning i fallet med ( a , n ) ≠ 1)Om , jämförelsen har antingen en icke-unik lösning eller har ingen lösning. Det är lätt att verifiera att jämförelsen
har ingen lösning på mängden naturliga tal. Samtidigt, jämförelse
har två lösningar
Euler-funktionen låter dig beräkna resten av divisionen av stora tal [40] .
Exempel 1 (de tre sista siffrorna i decimalrepresentationen av ett tal)Hitta de tre sista siffrorna i decimalnotationen för ett tal
vi får
När vi nu går från modul till modul har vi:
Därför slutar decimalrepresentationen av ett tal på
Exempel 2 (återstoden av division med 1001)Låt oss hitta resten efter att ha dividerat med Det är lätt att se det
Därför använder multiplikativiteten av Euler-funktionen och jämlikheten
för något enkeltvi får
Enligt Eulers teorem
Den multiplikativa gruppen av restringens modulo består av restklasser [41] .
Exempel. Det reducerade systemet av rester modulo 14 består av restklasser:
Antalet genererande element i en ändlig cyklisk grupp är . I synnerhet, om den multiplikativa gruppen i ringen av rester modulo är en cyklisk grupp - vilket är möjligt endast för , där är ett udda primtal, är ett naturligt tal [42] - så finns det generatorer av gruppen ( primitiva rötter modulo ) .
Exempel. Gruppen som betraktas i exemplet ovan har en generator: och
Som ni vet, om är primtal, så 1932 undrade Derrick Lemaire om det finns ett sådant sammansatt tal som är en divisor av . Lehmer övervägde ekvationen:
var är ett heltal. Han lyckades bevisa att om är en lösning på en ekvation, så är det antingen primtal eller så är det en produkt av sju eller flera olika primtal [43] . Andra starka påståenden bevisades senare. Så, 1980, visade Cohen och Hagis att om sammansättning och delar då och var är antalet primtalsdelare. 1970 slog Lieuwens fast att om då och Wall 1980 bevisade att om då [44] .
Än idag är det inte känt om det finns sammansatta lösningar på Lehmers problem. Om vi antar att de inte finns, så erhålls följande enkelhetskriterium: - prime if and only if [43] .
Även om du tittar på de första tio värdena av Euler-funktionen {1, 1, 2, 2, 4, 2, 6, 4, 6, 4} är det slående att det finns många upprepningar bland dem. Carmichaels gissning är att det inte finns något sådant värde som Euler-funktionen bara skulle ta en gång.
1907 föreslog Carmichael som en övning för att bevisa följande uttalande [45] :
Om är ett naturligt tal, så finns det ett naturligt tal somAnnars kan detta påstående formuleras på följande sätt [46] : det finns inget naturligt tal som
Men 1922 upptäckte Carmichael att hans bevis innehöll ett fel. Samma år visade han att om sedan senare denna uppskattning upprepade gånger förbättrades, och det moderna värdet av den nedre gränsen, från vilken det är värt att börja leta efter ett motexempel för Carmichaels gissning, är Detta värde erhölls av Schlafly och Wagon 1994 med Klee-metoden [45] .
Det är värt att notera att Ford 1999 bevisade följande teorem [47] :
Detta betyder att man, givet ett visst antal , kan hitta ett sådant värde bland Euler-funktionens värde att det tas exakt en gång. Ingen har dock kunnat bevisa att det inte finns något sådant värde som Euler-funktionen bara skulle ta en gång [46] .
![]() |
---|