Eulers sats

Från Wikipedia
Hoppa till: navigering, sök

Eulers sats inom talteorin säger att för positiva heltal a och n sådana att a och n är relativt prima så gäller

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

där φ(n) betecknar Eulers φ-funktion.

Satsen är en generalisering av Fermats lilla sats.

En viktig tillämpning av satsen är vid RSA-kryptering, då man utnyttjar att det för heltal a och primtal p och q sådana att p ≠ q och SGD(a,p) = SGD(a,q) = 1 gäller att a(p-1)(q-1) ≡ 1 (mod p⋅q), vilket följer av satsen eftersom Φ(p⋅q) = (p-1)(q-1), om p och q är olika primtal och SGD(a,pq) = 1.

Satsen kan användas för att lättare reducera stora potenser modulo n. Betrakta till exempel problemet att hitta den sista decimalsiffran av 7222, dvs 7222 (mod 10). Notera att 7 och 10 är relativt prima, och att φ(10) = 4. Eulers sats ger att 74 = 1 (mod 10), och vi får 7222 = 74·55 + 2 = (74)55·72 = 155·72 = 49 = 9 (mod 10).

Generellt när man reducerar en potens av a modulo n (där a och n är relativt prima) måste man arbeta modulo φ(n) i exponenten till a. Detta är innebörden i en alternativ formulering av Eulers sats, nämligen att om a och n är relativt prima så gäller:

x \equiv y\ (\operatorname{mod}\ \varphi(n)) \Rightarrow a^x \equiv a^y\ (\operatorname{mod}\ n)

Bevis[redigera | redigera wikitext]

Leonhard Euler publicerade ett bevis 1736. Satsen kan bevisas genom att använda Lagranges teorem från den abstrakta algebran. Talen a som är relativt prima med n bildar en grupp under multiplikation mod n. Detta är enhetsgruppen till ringen Z/nZ. Denna grupp har φ(n) element, och Eulers sats följer sedan från Lagranges teorem.

Nedan följer ett bevis som utnyttjar det faktum att värdet av φ(m) är antalet inverterbara element i Zm = {0, 1, 2, ..., m-1}.

Antag SGD(y,m) = 1. För y = z + r·m (där z,r ε Zm) vill vi visa att SGD(z,m) = 1 och att yφ(m) ≡ zφ(m) (mod m), ty om SGD(z,m) = 1 är zφ(m) ≡ 1(mod m), vilket skulle bevisa satsen.

zφ(m) ≡ 1(mod m) om SGD(z,m) = 1[redigera | redigera wikitext]

SGD(z,m) = 1 är ekvivalent med att z är inverterbar i Zm. Ty om z är inverterbar finns ett tal c ε Zm s.a. z·c ≡ 1 (mod m), så z·c - k·m = 1 för något k. En delare till z och m delar z·c och därmed även 1, så SGD(z,m) = 1. Omvänt gäller att om SGD(z,m) = 1 så existerar heltal z' och c' s.a. z·z' + c·c' = 1 (detta inses enklast genom att utföra euklides algoritm baklänges), dvs. z·z' ≡ 1 (mod m), så z är inverterbar.

Låt Um = {x1, x2, ..., xk} vara mängden av alla inverterbara element i Zm och ansätt a,b ε Um. Då är (a·b)−1 = a−1·b−1 (detta gäller för godtyckliga a,b ε Um). (a·b)·(a·b)−1 = (a·b)·a−1·b−1 = a·(b·b−1)·a−1 ≡ a·a−1 ≡ 1 (mod m), så a·UmUm. Att b = 1·b ≡ a·a−1·b = a·(a−1·b) (mod m) medför att Um ⊆ a·Um vilket ger att a·Um = Um. Eftersom z är inverterbar följer att (z·x1)·(z·x2)·...·(z·xk) ≡ x1·x2·...·xk (mod m), så zφ(m) ≡ 1 (mod m).

SGD(z,m) = 1 och yφ(m) ≡ zφ(m) (mod m)[redigera | redigera wikitext]

En delare till z och m delar även y = z + r·m, så SGD(z,m) = 1 (Vi har ju antagit att SGD(y,m) = 1).

yφ(m) = (z + r·m)φ(m) = (enligt binomialsatsen) = \sum_{i=0}^{\varphi(m)} \binom{\varphi(m)}{i} z^i \, (rm)^{\varphi(m) - i} = 
z^{\varphi(m)} + \sum_{i=0}^{\varphi(m) - 1} \binom{\varphi(m)}{i} z^i \, (rm)^{\varphi(m) - i} \equiv
z^{\varphi(m)} (\operatorname{mod}\ m)

Det sista steget i beräkningarna följer av att φ(m) − i ≠ 0 för i ε [0, φ(m) − 1].

QED.