Euler funktion

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 1 oktober 2021; kontroller kräver 3 redigeringar .

Eulerfunktionen är en multiplikativ aritmetisk funktion vars värde är lika med antalet naturliga tal som är mindre och samprimat med det [1] . $\varphi (n)$ $n$

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å . $\varphi (36)=12$

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] . $\varphi (n)$

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

Beräkning

De första 99 värdena av Euler-funktionen [4]

$\varphi (n)$	+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

Allmän information

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. $\varphi (n)$ $[1,\;n-1]$ $n$

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. $\varphi (n)$ $ett$ $n-1$ $n$ $n$ $n$ $\varphi (n)$

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. $\varphi (n)$ $n-1$ $n$ $(n,\;y)$ $y=n-1$ $y=\varphi(n)$ $\varphi (n)$ $n$ $\varphi (n)$ $y=n-1$ $\varphi(n)=n-1$ $n$ $y=n/2$ $\varphi(2n)=\varphi(n)=n-1$ $n$

Euler-funktionens beteende diskuteras mer i detalj i avsnittet #Asymptotiska relationer .

Multiplikativitet för Euler-funktionen

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] $m$ $n$

\varphi(mn)=\varphi(m)\varphi(n).

Bevis på multiplikativitet

Fö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 .

(m,\;m')=1

a

m

a'

m'

a'm+am'

m

m'

Bevis. Om en

a_1'm+a_1m'\equiv a_2'm+a_2m'\pmod{mm'},

sedan

a_1m'\equiv a_2m'\pmod m,

det är därför

a_1\equiv a_2\pmod m;

likaså

a_1'\equiv a_2'\pmod{m'}.

Därför finns det ojämförliga modulo- tal som bildar ett komplett system av modulo-rester .

mm'

mm'

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å:

(m,\;m')=1

a'm+am'

mm'

a

a'

m

m'

(a'm+am',\;mm')=1

\Leftrightarrow (a'm+am',\;m)=1,\;(a'm+am',\;m')=1

\Leftrightarrow (am',\;m)=1,\;(a'm,\;m')=1

\Vänsterhögerpil (a,\;m)=1,\;(a',\;m')=1.

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 det

\varphi(mm')

mm'

\varphi(m)\varphi(m')

a'm+am'

a

m

a'

m'

\varphi(mm')=\varphi(m)\varphi(m').

Eulerfunktionen för ett primtal

För ett enkelt värde på Euler-funktionen ges av en explicit formel [8] : $sid$

\varphi(p)=p-1,

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. $sid$ $sid$ $p-1$

För att beräkna Euler-funktionen av potensen av ett primtal, använd följande formel [8] :

\varphi(p^n)=p^np^{n-1}.

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 . $ett$ $p^{n}$ $p^{n}$ $sid$ $p,\;2p,\;3p,\;\ldots ,\;p^{n-1}s.$ $p^{n-1}$ $p^{n}$ ${\displaystyle p^{n}-p^{n-1))$

Eulerfunktionen för ett naturligt tal

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] : $\varphi (n)$ $n$ $\varphi(p^{n})$ $\varphi (n)$

\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right),\;\;n>1,

där är ett primtal och går igenom alla värden som är involverade i nedbrytningen till primtalsfaktorer. $sid$ $n$

Bevis

Som följer av aritmetikens grundläggande sats är alla naturliga tal unikt representerade i formen: $n>1$

n=p_1^{\alpha_1}\cdot\ldots\cdot p_k^{\alpha_k},

var är primtal och är naturliga tal. $p_1<\ldots<p_k$ $\alpha_1,\;\ldots,\;\alpha_k$

Genom att använda Euler-funktionens multiplikativitet och uttrycket för får vi: $\varphi(p^{k})$ ${\begin{aligned}\varphi (n)&=\varphi (p_{1}^{\alpha _{1)))\varphi (p_{2}^{\alpha _{2))) \cdot \ldots \cdot \varphi (p_{k}^{\alpha _{k)))=\\&=p_{1}^{\alpha _{1))\left(1-{\frac { 1}{p_{1}}}\right)p_{2}^{\alpha _{2}}\left(1-{\frac {1}{p_{2}}}\right)\cdot \ldots \cdot p_{k}^{\alpha _{k}}\left(1-{\frac {1}{p_{k}}}\right)=\\&=p_{1}^{\alpha _ {1}}p_{2}^{\alpha _{2}}\cdot \ldots \cdot p_{k}^{\alpha _{k}}\left(1-{\frac {1}{p_{ 1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdot \ldots \cdot \left(1-{\frac {1}{p_{k} }}\right)=\\&=n\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}} \right)\cdot \ldots \cdot \left(1-{\frac {1}{p_{k}}}\right).\end{aligned}}$

Applikationsexempel: $\varphi (36)=\varphi (2^{2}\cdot 3^{2})=\varphi (2^{2})\varphi (3^{2})=(2^{2} }-2)(3^{2}-3)=2\cdot 6=12.$

Egenskaper

Generaliserad multiplikativitet

Euler-funktionen är en multiplikativ aritmetisk funktion , det vill säga

\varphi (mn)=\varphi (m)\varphi (n)\;\;\;\forall m,\,n\in \mathbb {N} \colon (m,\,n)=1 .

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] : $m$ $n$ $m$ $n$ $m$ $n$

\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n)\cdot\frac{d}{\varphi(d)},

var är den största gemensamma delaren och Denna egenskap är en naturlig generalisering av multiplikativitet. $d$ $m$ $n.$

Bevis på generaliserad multiplikativitet

Låt då och i det allmänna fallet och Därför kan vi skriva: $(m,\,n)=d,$ $m = m'd, \; n = n'd,$ $(m',\,d)\neq 1$ $(n',\,d)\neq 1.$

d=d_{1}^{\delta _{1))\cdot \ldots \cdot d_{k}^{\delta _{k))\cdot d_{k+1}^{\delta _ {k+1}}\cdot \ldots \cdot d_{K}^{\delta _{K)),

m'=d_{1}^{\alpha _{1))\cdot \ldots \cdot d_{k}^{\alpha _{k))\cdot p_{1}^{\beta _{ 1))\cdot \ldots \cdot p_{r}^{\beta _{r)),

n'=d_{k+1}^{\gamma _{k+1}}\cdot \ldots \cdot d_{K}^{\gamma _{K}}\cdot q_{1}^{ \varepsilon _{1}}\cdot \ldots \cdot q_{s}^{\varepsilon _{s}}.

Här är de första divisorerna också divisorer och de sista divisorerna är divisorer Låt oss skriva: $k$ $d$ $m',$ $Kk$ $d$ $n'.$

\varphi (mn)=\varphi (d^{2}\cdot m'n')=\varphi ((d_{1}^{\delta _{1))\cdot \ldots \cdot d_{ k}^{\delta _{k}}\cdot d_{k+1}^{\delta _{k+1}}\cdot \ldots \cdot d_{K}^{\delta _{K}}) ^{2}\cdot d_{1}^{\alpha _{1}}\cdot \ldots \cdot d_{k}^{\alpha _{k}}\cdot p_{1}^{\beta _{ 1}}\cdot \ldots \cdot p_{r}^{\beta _{r}}\cdot d_{k+1}^{\gamma _{k+1}}\cdot \ldots \cdot d_{K }^{\gamma _{K}}\cdot q_{1}^{\varepsilon _{1}}\cdot \ldots \cdot q_{s}^{\varepsilon _{s}}).

På grund av Euler-funktionens multiplikativitet, och även med hänsyn till formeln

\varphi(p^n) = p^n(1-\frac{1}{p}),

var är ett primtal får vi: $sid$

{\begin{aligned}\varphi (mn)&=d_{1}^{\alpha _{1}+\delta _{1}}\left(1-{\frac {1}{d_{ 1}}}\right)\cdot \ldots \cdot d_{k}^{\alpha _{k}+\delta _{k}}\left(1-{\frac {1}{d_{k}} }\right)\cdot p_{1}^{\beta _{1}}\left(1-{\frac {1}{p_{1}}}\right)\cdot \ldots \cdot p_{r} ^{\beta _{r}}\left(1-{\frac {1}{p_{r}}}\right)\cdot d_{k+1}^{\delta _{k+1}}\ left(1-{\frac {1}{d_{k+1}}}\right)\cdot \ldots \cdot d_{K}^{\delta _{K}}\left(1-{\frac { 1}{d_{K))}\right)\times \\&\;\times \;d_{k+1}^{\gamma _{k+1}+\delta _{k+1}}\ vänster(1-{\frac {1}{d_{k+1}}}\right)\cdot \ldots \cdot d_{K}^{\gamma _{K}+\delta _{K}}\left (1-{\frac {1}{d_{K}}}\right)\cdot q_{1}^{\varepsilon _{1}}\left(1-{\frac {1}{q_{1} }}\right)\cdot \ldots \cdot q_{s}^{\varepsilon _{s}}\left(1-{\frac {1}{q_{s}}}\right)\cdot d_{1 }^{\delta _{1}}\left(1-{\frac {1}{d_{1}}}\right)\cdot \ldots \cdot d_{k+1}^{\delta _{k +1}}\left(1-{\frac {1}{d_{k+1}}}\right)\times \\&\;\times \;{\frac {1}{\left(1- {\frac {1}{d_{1}}}\right)\cdot \ldots \cdot \left(1-{\fr  ac {1}{d_{K}}}\right)}}.\end{aligned}}

Den första raden skrivs i den andra - och den tredje kan representeras som Därför: $\varphi(m),$ $\varphi(n),$ $d/\varphi(d).$

\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n) \cdot \frac{d}{\varphi(d)}.

Några speciella fall:

$\;\varphi\left(n^m\right) = n^{m-1}\varphi(n).$
$\varphi (2m)={\begin{cases}2\varphi (m),&m=2k,\;k\in \mathbb {N} ,\\\varphi (m),&m=2k-1 ,\;k\in \mathbb {N} .\end{cases}}$
$\varphi(M)\cdot\varphi(d) = \varphi(m)\cdot\varphi(n),$ där är den minsta gemensamma multipeln av och , och är deras största gemensamma divisor. $M$ $m$ $n$ $d$

Eulers teorem

Egenskapen etablerad av Euler används oftast i praktiken :

a^{\varphi(m)}\equiv 1\pmod m,

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: $a$ $m$
$\varphi(m)$ $m$
$m,$

a^{m - 1}\ekvivalent 1\pmod m.

Den senare formeln finner användning i olika primatitetstester .

Andra egenskaper

Baserat på hur Euler-produkten är representativ, är det lätt att få följande användbara uttalande: $\varphi (n)$

a\mid b \Högerpil \varphi(a)\mid\varphi(b).

Följande likhet [10] [11] är en konsekvens av Zsigmondys sats :

\varphi (a^{n}+b^{n})\equiv 0{\pmod {n)),\;a>b\geqslant 1.

Vilket naturligt tal som helst kan representeras som summan av värdena för Euler-funktionen från dess naturliga delare [12] :

\sum_{d\mid n}\varphi(d)=n.

Summan av alla tal mindre än ett givet tal och relativt primtal till det uttrycks i termer av Euler-funktionen:

\sum_{1\leqslant k\leqslant n\atop(k,\;n)=1}k=\frac{1}{2}n\varphi(n), \; n > 1.

Många värden

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

Euler-funktionen tar bara jämna värden för Dessutom, om den har olika udda primtalsdelare, $\varphi (n)$ $n > 2.$ $n$ $r$ $2^{r} \mid \varphi(n).$

Bevis (Euler-funktionen tar bara jämna värden för n > 2) Om är faktiskt ett udda primtal och sedan

sid

\alfa > 1

p^{\alpha - 1}(p - 1)

- även. Från jämlikhet

\varphi(n)=\prod_{i=1}^{k}p_i^{\alpha_i - 1}(p_i - 1)

påstående följer.

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.

Värdena för Euler-funktionen upprepas (till exempel ), så den inversa funktionen är flervärdig . $\varphi(1) = \varphi(2) = 1$
Euler-funktionen tar bara jämna värden för det vill säga om udda och $n > 2$ $\varphi ^{-1}(m)=\varnothing ,$ $m$ $m\neq 1.$

I detta avseende behövs speciella analysmetoder. Ett användbart verktyg för att studera förbilden är följande sats [14] . $\varphi$

Låt - även, låt oss sätta $m$ $A(m)=m\prod _{p-1\mid m}{\frac {p}{p-1)),$ var är enkelt. $sid$

Om då

n \in \varphi^{-1}(m),

m<n\leqslant A(m).

Bevis för satsen Självklart, om då Å andra sidan, om och då

\varphi(n) = m,

m < n.

\varphi(n) = m

n=p_{1}^{\alpha _{1}}\cdot \ldots \cdot p_{s}^{\alpha _{s)),

m = n \prod_{i=1}^s \frac{p_i-1}{p_i} \; \Höger pil\; n = m \prod_{i=1}^s \frac{p_i}{p_i-1}.

Men om då alltså

p\mid n,

p-1\mid \varphi (n).

\forall p_{i}:\;p_{i}-1\mid m.

Följaktligen

n\leqslant A(m).

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: $m\in \mathbb {N}$

1) beräkna ;

A(m)

2) beräkna för alla från halvintervallet ;

\varphi (n)

n

(m,\,A(m)]

3) alla tal som bildar elementets omvända bild .

n,

\varphi(n)=m,

m

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. $n,$ $\varphi(n)=m;$
$A(m)$ $m$ $m$ $A(m)-m$

Exempel 1 (förbildsberäkning)

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

A(4) = 4 \cdot \frac{2}{1} \cdot \frac{3}{2} \cdot \frac{5}{4} = 15.

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:

\varphi ^{-1}(4)=\{5,\;8,\;10,\;12\}.

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: $m,$ $\varphi(m) = 14.$

\varphi ^{-1}(14)=\varnothing .

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

A(14) = 14 \cdot \frac{2}{1} \cdot \frac{3}{2} = 42.

Efter att ha sorterat igenom alla siffror från 15 till 42 är det lätt att verifiera det

\varphi (n)\neq 14,\;n\in (15,\,42].

Asymptotiska relationer

De enklaste ojämlikheterna

Den nedre gränsen för värdena för Euler-funktionen [15] [16] : $\varphi (n)\geqslant {\sqrt {n)),$

för alla utom

n,

n=2

n = 6.

En övre gräns för komposit [15] [17] : $n$ $\varphi (n)\leqslant n-{\sqrt {n)),$

för vilken förening som helst

n.

För alla naturvärden är den dubbla ojämlikheten giltig [15] : $n\geqslant 3$ $\frac{\log2}{2} \cdot \frac{n}{\log{n}} < \varphi(n) < n.$

Jämförelse av φ( n ) med n

Den övre gränsen för förhållandet närmar sig enhet med tillväxt [18] : $\varphi(n)/n$ $n$ $\varlimsup \frac{\varphi(n)}{n} = 1.$
Samtidigt kan förhållandet vara godtyckligt stort [19] : $\varphi(n)/n^{1-\delta}$ $\forall \delta >0\colon {\frac {\varphi (n)}{n^{1-\delta ))}\högerpil \infty .$

Förhållandet mellan successiva värden

Följande likheter visar hur oförutsägbar Euler-funktionen är [20] : $\lim \inf {\frac {\varphi (n+1)}{\varphi (n)))=0$ och $\lim \sup {\frac {\varphi (n+1)}{\varphi (n)))=\infty .$
Formlerna ovan erhölls av Somayajulu 1950. Och fyra år senare bevisade Schinzel och Sierpinski [20] att uppsättningen

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

tät i uppsättningen av reella positiva tal.

Samma år fastställde de [20] att uppsättningen

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

tight på intervallet

(0,\;1).

Asymptotik för summor

Det exakta uttrycket för summan av successiva värden för Euler-funktionen [21] är: $\sum_{n\leqslant x}\varphi(n)=\frac{3}{\pi^2}x^2+O(x\ln x).$

Detta innebär att den genomsnittliga ordningen för Euler-funktionen är lika med . Detta resultat är intressant eftersom det tillåter en att få sannolikheten för händelsen att två slumpmässigt valda naturliga tal är coprima. Denna sannolikhet är nämligen lika med [22] .

6n/\pi ^{2}

6/\pi ^{2}

Med hänsyn till uttrycket ovan kan vi erhålla följande asymptotiska uppskattningar: $\sum _{k=1}^{n}{\frac {k}{\varphi (k)))=O(n)$ ; $\sum _{k=1}^{n}{\frac {1}{\varphi (k)))=O(\ln n)$ .
Med hjälp av Euler-funktionens multiplikativitet och egenskaperna hos summan av divisorer är det lätt att fastställa att [23] $\sigma(n)$ ${\frac {6}{\pi ^{2))}<{\frac {\varphi (n)\sigma (n)}{n^{2))}<1,\;n>1$ .

Ordningen för Euler-funktionen

1909 fick Landau jämställdheten [24] [25] : $\lim\inf\frac{\varphi(n)}{n}\log\log n = e^{-\gamma},$

var är Euler-Mascheroni-konstanten .

\gamma

Detta resultat kan förfinas. 1962 erhölls en lägre uppskattning för Euler-funktionen [26] : $\varphi (n)\geqslant {\frac {n}{e^{\gamma }\log \log n+{\frac {2{,}5}{\log \log n))))$

för alla , med ett undantag i detta fall bör ersättas med Detta är en av de mest exakta nedre gränserna för [27] .

n\geqslant 3

n=2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23;

2{,}5

2{,}50637.

\varphi (n)

Som en övre uppskattning fastställdes följande faktum [28] : det finns oändligt många naturliga tal så att $n$ $\varphi(n) < e^{-\gamma} \frac {n} {\log \log n}.$

Som Paulo Ribenboim påpekar om beviset för denna ojämlikhet [27] : "Bevismetoden är intressant genom att ojämlikheten först etableras under antagandet att Riemann-hypotesen är sann, och sedan under antagandet att den inte är det. Sann."

Relation till andra funktioner

Möbius funktion

Följande formel kan användas för att beräkna [29] : $\varphi (n)$ $\varphi(n)=\sum_{d\mid n} d\cdot\mu\left(\frac{n}{d}\right),$

var finns Möbius-funktionen .

\mamma)

Andra relationer med Möbius-funktionen: $\sum_{k=1}^n\varphi(k)=\frac{1}{2}\left(1+\sum_{k=1}^n \mu(k)\left\lfloor\frac{n }{k}\höger\rgolv^2\höger);$ $\sum_{k=1}^n\frac{\varphi(k)}{k}=\sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{ n}{k}\höger\rgolv;$ $\sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)))={\frac {n}{\varphi (n)))$ [30] .

Dirichlet-serien

Dirichlet-serien med koefficienter kan representeras i termer av Riemann zeta-funktionen [31] : $\varphi (n)$ $\sum_{n=1}^\infty\frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}, \; s > 2.$

Lambert-serien

Summan av Lambert-serien med koefficienter [32] : $\varphi (n)$ $\sum_{n=1}^\infty\frac{\varphi(n)q^n}{1-q^n}=\frac{q}{(1-q)^2}, \; |q|<1.$

Största gemensamma divisor

Euler-funktionen är den diskreta Fouriertransformen av den största gemensamma divisorn [33] : $\varphi (n)=\summa \limits _{k=1}^{n}\gcd(k,\,n)e^{{-2\pi i}{\tfrac {k}{n }}}.$

Verklig del:

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

Till skillnad från Euler-produkten kräver beräkningar med dessa formler inte kunskap om divisorer

n.

Förbindelse med latinska rutor

Antalet cykliska latinska kvadrater av ordning med en fast första rad ges av Euler-funktionen . Denna funktion kan användas när man beräknar värdet på Euler-funktionen genom att räkna motsvarande antal kvadrater av en given ordning med hjälp av en algoritm utan multiplikationer och divisioner, men detta är asymptotiskt långsammare än beräkningen baserad på faktoriseringen av argumentet . Cykliska diagonala latinska kvadrater är en delmängd av cykliska latinska kvadrater, så antalet cykliska diagonala latinska kvadrater med en fast första rad (sekvens A123565 i OEIS ) är en nedre gräns för värdet av Euler-funktionen [34] . $N$ $\varphi (N)$ $N$ $N$ $\varphi (N)$

Tillämpningar och exempel

Euler-funktion i RSA

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] . $n$

I stadiet för att skapa ett par hemliga och offentliga nycklar,

\varphi(n) = \varphi(p \cdot q) = (p-1) \cdot (q-1),

var och är enkla. Sedan väljs slumpmässiga tal så att $sid$ $q$ $d,\ e$

d \cdot e = 1 \;\bmod \;\varphi(n).

Meddelandet krypteras sedan med mottagarens publika nyckel:

c = m^e \;\bmod \;n.

Efter det kan bara ägaren av den hemliga nyckeln dekryptera meddelandet : $d$

m = c^d \;\bmod \;n.

Riktigheten av det sista påståendet är baserat på Eulers sats och den kinesiska restsatsen .

Dekrypteringsbevis

På grund av valet av nummer vid skapandet av nycklar

e \cdot d = 1 + a \cdot \varphi(n).

Om då, med hänsyn till Eulersatsen, $(m,\,n)=1,$

c^d = m^{ed} = m^{1}m^{a\varphi(n)} = m \cdot 1^{a} = m \;\bmod \;n.

I det allmänna fallet, och kan ha gemensamma delare, men dekrypteringen visar sig fortfarande vara korrekt. Låt Enligt den kinesiska restsatsen: $m$ $n$ $m = 0 \;\bmod \;p.$

m = c^d \;\bmod \;n \;\Leftrightarrow \;\begin{cases} m = c^d \;\bmod \;p, \\ m = c^d \;\bmod \;q . \end{fall}

Genom att ersätta får vi identiteten $c = m^e,$

\begin{cases} m^{ed} = 0 = m \;\bmod \;p, \\ m^{ed} = m(m^{q-1})^{a(p-1)} = m \cdot 1^{a(p-1)} = m \;\bmod \;q. \end{fall}

Följaktligen,

m^{ed} = m \;\bmod \;pq.

Beräkning av det inversa elementet

Euler-funktionen kan användas för att beräkna inversen av ett element modulo , nämligen [36] : $n$

a^{-1} \equiv a^{\varphi(n)-1} \pmod n,

(a,\,n)=1.

Denna formel följer av Eulers teorem :

1 = (a \cdot a^{-1}) \cdot a^{\varphi(n)} \;\bmod \;n = en \cdot (a^{-1} \cdot a^{\varphi( n)}) \;\bmod \;n = a \cdot a^{\varphi(n) - 1} \;\bmod \;n.

Exempel (beräkning av omvänd element)

Hitta , det vill säga ett antal sådant att $5^{-1} \;\bmod \;7$ $x$

5 \cdot x \equiv 1 \pmod 7.

Uppenbarligen, och har inte gemensamma delare förutom en, , medan talet är primtal och $5$ $7$ $(5,7)=1$ $7$

\varphi(7)=7-1=6,

Därför är det bekvämt att använda formeln ovan:

5^{6-1} \;\bmod \;7 = 5^{5} \;\bmod \;7 = 25 \cdot 25 \cdot 5 \;\bmod \;7 = (-3) \cdot ( -3) \cdot 5 \;\bmod \;7 = 9 \cdot 5 \;\bmod \;7 = 2 \cdot 5 \;\bmod \;7 = 3.

Det är lätt att kontrollera vad som verkligen är

5 \cdot 3 \equiv 1 \pmod 7.

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] . $O(k^2),$ $O(k^3)$ $k = \lceil \log_2{n} \rceil.$ $\varphi(n)-1$

Anmärkning 2 (Ingen lösning i fall ( a , n ) ≠ 1)

Om då det inversa elementet inte existerar, eller med andra ord, ekvationen $(a,\,n)\neq 1,$ $a$

a \cdot x \equiv 1 \pmod n

har ingen lösning på mängden naturliga tal [39] .
Bevis. Sannerligen, antar

(a,\,n)=d>1,

och lösningen finns. Då enligt definitionen av den största gemensamma divisorn

a=d\cdot a',\ n=d\cdot n',

och

(a',\,n')=1;

så du kan skriva:

d \cdot a' \cdot x = d \cdot n' \cdot t + 1,

var

t\in \mathbb {N} _{0},x\in \mathbb {N} ;

eller, ordna om villkoren,

a' \cdot x - n' \cdot t = \frac{1}{d}.

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

d=1

vilket strider mot antagandet.

Linjär jämförelselösning

Metoden för att beräkna det inversa elementet kan användas för att lösa jämförelsen

a \cdot x \equiv b \pmod n.

Lösningen ges av formeln [37] :

x \equiv b \cdot a^{\varphi(n)-1} \pmod n,

(a,\,n)=1.

Exempel (Linjär jämförelselösning)

Tänk på jämförelsen

7 \cdot x \equiv 3 \pmod 9.

Hur kan du använda denna formel: $(7.9)=1,$

x = 3 \cdot 7^{\varphi(3^{2})-1} \;\bmod \;9 = 3 \cdot 7^{3 \cdot (3-1) - 1} \;\bmod \ ;9 = 3 \cdot 7^{5} \;\bmod \;9 = 3 \cdot 49 \cdot 49 \cdot 7 \;\bmod \;9 = 3 \cdot 4 \cdot 4 \cdot 7 \;\ bmod \;9 = 3.

Genom substitution ser vi till det

7 \cdot 3 \equiv 3 \pmod 9.

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 $(a,\,n)\neq 1$

2 \cdot x \equiv 3 \pmod 4

har ingen lösning på mängden naturliga tal. Samtidigt, jämförelse

4 \cdot x \equiv 6 \pmod {22}

har två lösningar

x = 7, \; x=18.

Beräkning av resten av en division

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 $2^{100}.$

\varphi(125) = \varphi(5^3) = 5^3 - 5^2 = 100,

vi får

2^{100} \;\bmod \;125 = 2^{125 - 25} \;\bmod \;125 = 2^{\varphi(125)} \;\bmod \;125 = 1 \;\bmod \;125.

När vi nu går från modul till modul har vi: $125$ $1000$

2^{100} \equiv 1 \pmod{125} \equiv 376 \pmod{1000}.

Därför slutar decimalrepresentationen av ett tal på $2^{100}$ $376.$

Exempel 2 (återstoden av division med 1001)

Låt oss hitta resten efter att ha dividerat med Det är lätt att se det $729^{720}$ $1001.$

(729,\;1001)=1.

Därför använder multiplikativiteten av Euler-funktionen och jämlikheten

\varphi(p) = p - 1,

för något enkelt

p,

vi får

\varphi(1001) = \varphi(7 \cdot 11 \cdot 13) = \varphi(7) \cdot \varphi(11) \cdot \varphi(13) = 6 \cdot 10 \cdot 12 = 720.

Enligt Eulers teorem

729^{720} \equiv 1 \pmod{1001}.

Hitta ordningen för den multiplikativa gruppen av en restring

Den multiplikativa gruppen av restringens modulo består av restklasser [41] . Exempel. Det reducerade systemet av rester modulo 14 består av restklasser: $m$ $\varphi(m)$
$\varphi(14) = 6$ $[1]_{14},\ [3]_{14},\ [5]_{14},\ [9]_{14},\ [11]_{14},\ [13 ]_{fjorton}.$

Tillämpningar i gruppteori

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 $G$ $\varphi(|G|)$ $m$ ${\displaystyle m=2,\;4,\;p^{n},\;2p^{n))$ $sid$ $n$ $\varphi(\varphi(m))$ $m$
$\mathbb {Z} _{14}^{\times },$ $\varphi(\varphi(14)) = \varphi(6) = 2$ $3$ $5.$

Återstående frågor

Lemaires problem

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: $sid$ $\varphi(p) = p - 1.$ $n$ $\varphi (n)$ $n-1$

k\varphi(n) = n-1,

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] . $k$ $n$ $n$ $n$ $\varphi (n)$ $n-1,$ $n > 10^{20}$ $\omega (n)\geqslant 14,$ $\omega(n)$ $3\mitten av n,$ $\omega (n)\geqslant 213$ $n>5{,}5\cdot 10^{570}.$ $30\mitten av n,$ $\omega (n)\geqslant 26$

Ä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] . $n$ $\varphi (n)\mid n-1$

Carmichaels hypotes

Ä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. $m$

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 som

n

m\neq n

\varphi(n)=\varphi(m).

Annars kan detta påstående formuleras på följande sätt [46] : det finns inget naturligt tal som $m$ $\dim(\varphi^{-1}(m)) = 1.$

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] . $\dim(\varphi^{-1}(m)) = 1,$ $m>10^{37}.$ $m=10^{10^{7}}.$

Det är värt att notera att Ford 1999 bevisade följande teorem [47] :

\forall k\geqslant 2\;\exists m\colon \dim(\varphi ^{-1}(m))=k.

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] . $k\geqslant 2,$ $m,$ $k$

Se även

Lista över föremål uppkallade efter Leonhard Euler

Anteckningar

↑ Euler funktion // Mathematical Encyclopedia (i 5 volymer). - M .: Soviet Encyclopedia , 1985. - T. 5. - S. 934.
↑ Sandifer, 2007 , sid. 203.
↑ Gabidulin, 2011 , RSA Systems.
↑ OEIS - sekvens A000010 _
↑ Burton, 2007 , Teorem 7.2, sid. 133.
↑ Hardy, 1975 , Theorem 59, sid. 52.
↑ Hardy, 1975 , Theorem 60, sid. 53.
↑ 1 2 3 Sagalovich, 2007 , Beräkning av Euler-funktionen, sid. 35-36.
↑ Burton, 2007 , Euler's Phi-Function, sid. 136.
↑ Weisstein, MathWorld, Totient Function
↑ Ruiz, S., A Congruence With the Euler Totient Function, 2004
↑ Vinogradov, 1952 , Euler-funktion.
↑ Informationen i detta avsnitt är baserad på artikeln: Coleman, Några kommentarer om Eulers totientfunktion
↑ Gupta H., 1981
↑ 1 2 3 Handbook, 2005 , Elementära ojämlikheter för φ.
↑ Kendall och Osborn 1965
↑ Sierpinski och Schinzel 1988
↑ Hardy, 1975 , Teorem 326, sid. 267.
↑ Hardy, 1975 , Teorem 327, sid. 267.
↑ 1 2 3 Ribenboim, 1996 , Values of Euler's Function, sid. 38.
↑ Hardy, 1975 , Theorem 330, sid. 268.
↑ Hardy, 1975 , Teorem 332, sid. 269.
↑ Hardy, 1975 , Teorem 329, sid. 267.
↑ Handbook, 2005 , Om funktionen n /φ( n ).
↑ Hardy, 1975 , Theorem 328, sid. 267.
↑ Rosser, J. Barkley och Schoenfeld, Lowell. Ungefärliga formler för vissa funktioner i primtal // Illinois J. Math. : journal. - 1962. - Vol. 6 , nr. 1 . - S. 64-94 . (Sat 15)
↑ 1 2 Ribenboim, 1996 , Distribution of Values of Euler's Function, sid. 320.
↑ Nicholas, 1983
↑ Vinogradov, 1952 , sid. 29-31.
↑ Rosica Dineva, Euler Totient-, Möbius- och Divisor-funktionerna
↑ Hardy, 1975 , Teorem 288, sid. 250.
↑ Hardy, 1975 , Teorem 309, sid. 258.
↑ Schramm, 2008
↑ Vatutin E.I. Om uppräkningen av cykliska latinska kvadrater och beräkningen av värdet av Euler-funktionen med hjälp av dem // Högpresterande datorsystem och -teknologier. 2020. V. 4, nr 2. S. 40–48.
↑ Gabidulin, 2011 , RSA-krypteringssystem, sid. 96.
↑ Alferov, 2002 , sid. 462-463.
↑ 1 2 Schneier, 1995 , The Euler Totient Function.
↑ Gabidulin, 2011 , Finding the multiplicative inverse modulo, sid. 233.
↑ Schneier, 1995 , Talteori.
↑ Sagalovich, 2007 , sid. 36.
↑ Sagalovich, 2007 , Reducerat system för avdrag.
↑ Vinogradov, 1952 , sid. 106.
↑ 1 2 Lehmer, 1932
↑ Ribenboim, 1996 , sid. 36-37.
↑ 1 2 Ribenboim, 1996 , sid. 39-40.
↑ 1 2 Coleman, Några anmärkningar om Eulers totientfunktion
↑ Ford, 1999

Litteratur

Charles Sandifer. Leonhard Eulers tidiga matematik. - MAA, 2007. - S. 391. - ISBN 0-88385-559-3 .
Jozsef Sandor, Dragoslav S. Mitrinovic, Borislav Crstici. Eulers φ-funktion // Handbook of Number Theory I. - Springer, 2005. - 622 sid.
Vinogradov I.M. Fundamentals of Number Theory. - 5:e uppl. - M. - L .: Gostekhizdat, 1952. - 180 sid. — 100 000 exemplar.
GH Hardy, EM Wright. En introduktion till talteorin. - fjärde upplagan. - Oxford: Oxford University Press, 1975. - 421 sid.
Alferov A. P., Zubov A. Yu., Kuzmin A. S., Cheremushkin A. V. Elements of Algebra and Number Theory // Fundamentals of Cryptography. — 2:a uppl., rättad. och ytterligare - M. : Helios ARV, 2002. - 480 sid. — ISBN 5-85438-025-0 .
Bruce Schneier. Applied Cryptography: Protocols, Algorithms and Source Code in C. - Australien: John Wiley & Sons, 1995. - ISBN 0-471-12845-7 .
Sagalovich Yu. L. Introduktion till algebraiska koder - M. : MIPT , 2007. - 262 sid. — ISBN 978-5-7417-0191-1
Paul Ribenboim. Den nya boken med primtalsrekord. - New York: Springer, 1996. - ISBN 0-387-94457-5 .
Gabidulin E. M., Kshevetsky A. S., Kolybelnikov A. I. Informationssäkerhet: en handledning. - M. : MIPT, 2011. - 262 sid. — ISBN 5-7417-0377-9 .
David M Burton. Elementär talteori. — Sjätte upplagan. - University of New Hampshire: McGraw-Hill, 2007. - 512 sid. - ISBN 978-0-07-305188-8 .
Arnold V.I. Euler-grupper och aritmetik av geometriska progressioner. - M. : MTSNMO, 2003. - 44 sid. — ISBN 5-94057-141-7 .

Länkar

Arnold V. I., Euler-grupper och aritmetiken för geometriska progressioner (2003)
Coleman R., Några kommentarer om Eulers totientfunktion (2012)
Dineva R., The Euler Totient, the Möbius, and the Divisor Functions (2005)
Ford K., Antalet lösningar av φ(x) = m (1999)
József Sándor, Dragoslav S. Mitrinovic, Borislav Crstici, Handbook of Number Theory I (2005)
Gupta H., Eulers totient funktion och dess invers (1981)
Hardy, Wright An Introduction to theory of Numbers (2008)
Lehmer D.H., On Euler's Totient Function (1932)
Ruiz S., A Congruence With the Euler Totient Function (2004)
Schramm, Wolfgang, The Fourier Transform of Functions of the Greatest Common Divisor (2008)
Weisstein, Eric W. "Totient funktion." Från MathWorld - En Wolfram webbresurs. http://mathworld.wolfram.com/TotientFunction.html

Ordböcker och uppslagsverk	Britannica (online)