 |
|||
| HSG |
|
Motivation
Beim Studium der Multiplikationstafeln (z.B. mit tafeln.py) fällt auf, dass gewisse Zeilen alle Reste insbesondere die Eins enthalten und andere nicht. Die Existenz eines multiplikativen Inversen ist aber aus vielen Gründen von Interesse.
>>> mTafel(15) * | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ---+--------------------------------------------- 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 | 0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 3 | 0 3 6 9 12 0 3 6 9 12 0 3 6 9 12 4 | 0 4 8 12 1 5 9 13 2 6 10 14 3 7 11 5 | 0 5 10 0 5 10 0 5 10 0 5 10 0 5 10 6 | 0 6 12 3 9 0 6 12 3 9 0 6 12 3 9 7 | 0 7 14 6 13 5 12 4 11 3 10 2 9 1 8 8 | 0 8 1 9 2 10 3 11 4 12 5 13 6 14 7 9 | 0 9 3 12 6 0 9 3 12 6 0 9 3 12 6 10 | 0 10 5 0 10 5 0 10 5 0 10 5 0 10 5 11 | 0 11 7 3 14 10 6 2 13 9 5 1 12 8 4 12 | 0 12 9 6 3 0 12 9 6 3 0 12 9 6 3 13 | 0 13 11 9 7 5 3 1 14 12 10 8 6 4 2 14 | 0 14 13 12 11 10 9 8 7 6 5 4 3 2 1
Wie bereits früher bewiesen, sind gerade die a-Zeilen mit (a,m) = 1 die 'bewussten' Zeilen. Euler fasste diese Zahlen zu einem sogenannten reduzierten Restesystem zusammen. Im Beispiel für m = 15 gehören die Zahlen 1, 2, 4, 7, 8, 11, 13, 14 dazu.
Aufgabe 1
Bestimme die reduzierten Restesysteme zu m = 10, 12 und 13.
Die Eulerfunktion
Die Anzahl der Zahlen in einem reduzierten Restesystem zu m wird mit φ(m) bezeichnet. Nach obigem Beispiel ist also φ(15) = |{1,2,4,7,8,11,13,14}| = 8.
def gcd(a, b): # aus fractions.py
"""Calculate the Greatest Common Divisor of a and b.
Unless b==0, the result will have the same sign as b (so that when
b is divided by it, the result comes out positive).
"""
while b:
a, b = b, a%b
return a
def phi(n):
"""
Eulersche phi-Funktion
"""
return len([x for x in range(n) if gcd(x,n) == 1])
def phii(n):
"""
berechnet iterativ die Eulerfunktion
"""
s = 1
a = 2
while a < n:
if ggt(a,n) == 1:
s = s + 1
a = a + 1
return s
def phir(n):
"""
berechnet (end-)rekursiv die Eulerfunktion
"""
def h(akku,n,a):
if a == 1:
return akku + 1
else:
if ggtr(a,n) == 1:
return h(akku+1,n,a-1)
else:
return h(akku,n,a-1)
return h(0,n,n-1)
Satz 4
a ≡ b (m) ⇒ (a,m) = (b,m)
Beweis: a ≡ b (m) ⇔ m|(a-b) ⇔ ∃ q mit q⋅m = a-b ⇔ a = b + q⋅m man kann an der Gleichung ablesen, dass gemeinsame Teiler von b und m auch gemeinsame Teiler von a und m und umgekehrt sind, es folgt die Behauptung ∎
Beispiel
a = 7, m = 10, (a,m) = 1, die Zahlen b = 17, 27, 37, ... ,für die a ≡ b (m) gilt, sind ebenfalls teilerfremd ( (b,m) = 1 ) zu m = 10
Definition
Ein System von Zahlen, die zu einem gegebenen Modul m teilerfremd und paarweise inkongruent modulo m sind, heißt reduziertes Restesystem. Die Anzahl der Zahlen in einem reduzierten Restesystem wird mit φ(m) (Eulersche Funktion) bezeichnet.
Beispiel
m = 10, reduziertes Restesystem: 1, 3, 7, 9 ( (1,10)=1, (3,10)=1, (7,10)=1, (9,10)=1 ), φ(m) = 4
Satz 5
(k,m) = 1 und a1, a2, ..., aφ(m) ist reduziertes Restesystem bezüglich m ⇒ ka1, ka2, ..., kam ist reduziertes Restesystem bezüglich m
Beweis: Wenn ai zu m teilerfremd ist und k ebenfalls, so ist es auch kai. Der Rest ergibt sich aus Satz3. ∎
Beispiel
>>> m = 15 >>> r = [1, 2, 4, 7, 8, 11, 13, 14] >>> k = 22 >>> ggt(m,k) 1 >>> r1 = [x*k%m for x in r] >>> r1 [7, 14, 13, 4, 11, 2, 1, 8]
Aufgabe 2
Wähle irgendein Modul m und bestimme mit einer list comprehension das reduzierte Restesystem r. Wähle dann ein k mit (k,m) = 1 und bestimme r1.
Aufgabe 3
Schreibe eine Python-Funktion rmTafel(m), die zu einem Modul m eine Multiplikationstafel zu dem reduzierten Restesystem ausgibt. Untersuche damit die multiplikativen Eigenschaften der reduzierten Restesysteme.
Delphi
// Herrmann, Algorithmen Arbeitsbuch, S.154
function euler(n : longint) : longint;
var
phi : real;
p : tP;
h : tH;
i,z : integer;
begin
phi := n;
primfak(n,p,h);
i := 1;
while h[i] > 0 do
begin
phi := phi*(1 - 1/p[i]);
i := i+1;
end;
result := round(phi);
end;
Links
- Eulersche φ-Funktion - wikipedia