Eulers sats

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2022-09)
Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

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 7²²², dvs 7²²² (mod 10). Notera att 7 och 10 är relativt prima, och att φ(10) = 4. Eulers sats ger att 7⁴ = 1 (mod 10), och vi får 7²²² = 7^{4·55 + 2} = (7⁴)⁵⁵·7² = 1⁵⁵·7² = 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

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 Z_m = {0, 1, 2, ..., m-1}.

Antag SGD(y,m) = 1. För y = z + r·m (där z,r ε Z_m) 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

SGD(z,m) = 1 är ekvivalent med att z är inverterbar i Z_m. Ty om z är inverterbar finns ett tal c ε Z_m 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 U_m = {x₁, x₂, ..., x_k} vara mängden av alla inverterbara element i Z_m och ansätt a,b ε U_m. Då är (a·b)⁻¹ = a⁻¹·b⁻¹ (detta gäller för godtyckliga a,b ε U_m). (a·b)·(a·b)⁻¹ = (a·b)·a⁻¹·b⁻¹ = a·(b·b⁻¹)·a⁻¹ ≡ a·a⁻¹ ≡ 1 (mod m), så a·U_m ⊆ U_m. Att b = 1·b ≡ a·a⁻¹·b = a·(a⁻¹·b) (mod m) medför att U_m ⊆ a·U_m vilket ger att a·U_m = U_m. Eftersom z är inverterbar följer att (z·x₁)·(z·x₂)·...·(z·x_k) ≡ x₁·x₂·...·x_k (mod m), så z^φ(m) ≡ 1 (mod m).

SGD(z,m) = 1 och y^φ(m) ≡ z^φ(m) (mod m)

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)$