Rechnen mit kongruenten Zahlen


(Bearbeitet von Jonas Bauer und Felix Lück, Schuljahr 2005/06, Klasse 9c)


 

1. Die Resteuhr




Aufgaben:

Bestimme den 3er-Rest der beiden Zahlen (Hinweis in Klammern)
1312 und 7      (1 + 3 + 1 + 2)

759 und 21

8879 und 32

5234 und 14

Bestimme den 9er-Rest von
255 und 12;   7432 und 16;    856 und 19;    3276 und 18



Rechnen mit kongruenten Zahlen

Aufgaben:

Welche Aussagen sind für n = 3 richtig?

17 º 1             13 º1              17 º 2             5 º 1               5 º 8               8 º 2 (mod 3)

 

Wir betrachten 3er-Restklassen.

·        Es gilt: 13 º 1 und 17 º 2                    und  13 + 17 = 30 hat den Dreierrest 0
d.h. der 3er-Rest von 13 + 17 ist gleich dem 3er-Rest von 1 + 2

 

·        5 º 2 und 8 º 2                                   und 5 • 8 = 40 hat den Dreierrest 1
d.h. der 3er-Rest von 5 • 8  ist gleich dem 3er-Rest von 2 • 2

 

·        Es gilt also: 1 + 2 º 0 und 2 • 2 = 1


Der Rest der Summe (des Produktes) von a und b bei Division durch n hängt nur davon ab, zu welcher Restklasse a und b gehören.

Es ist also gleichgültig, ob wir die Zahl 5 oder die Zahl 2 aus der Restklasse von 2 nehmen.
Wir schränken unsere Rechnungen mit Resten bei Division durch n auf die Zahlen 0 bis n-1 ein und bezeichnen
die Menge kleinsten nichtnegativen Reste mit

= { 0, 1, 2}

Allgemein: = {0, 1, 2, .... n-1 }

 

Produkttafel für Summentafel für  

0

1

2

0

0

0

0

1

0

1

2

2

0

2

1

+

0

1

2

0

0

1

2

1

1

2

0

2

2

0

1

Gesetze: Gelten K, A, N, I ?

Gesetze: Gelten K, A, N, I ?

Hinweis: Siehe Gruppen

Das neutrale Element der Addition besitzt kein multiplikatives Inverses.

In der Menge = { 1, 2} sind alle Gruppenaxiome erfüllt!


Aufgaben:

Stelle Summen- und Produkttafel für und n = 4 (5, 6, 7, 8) auf.

Welche Elemente besitzen Inverse? Vermutung?

 

Löse in

x + 4 º 1         3x º 1              3x + 2 º 0       2x + 4 º 1       x + 2 º 5        
x2 º 3              x2 º 0


Löse in

2 + x º 5         x + 2 º 0         2x º 4              x*3 º 0            3x º 1              5x º 3

6x º 1             7x º 2

 

Ein JAVA-Applet zur Darstellung von Produkttafeln

Das Applet wurde mit Eclipse 3.2, dem Designer Jigloo GUI Builder und Java6 entwickelt.

 

 

 

 

Modulare Inverse

(und der Zusammenhang mit dem ggT)

 

Definition (Wiederholung)

Zwei ganze Zahlen a und b heißen "kongruent modulo n" (), wenn sie bei Division durch m denselben Rest r lassen:

In Zeichen:       a ≡ b mod n   Û a = k•n + r  und  b = l•n + r mit k,l Î Z und 0 £ r < n.

 

Beispiele

37 ≡ 73 mod 6, denn 37 = 6•6 + 1 und 73 = 12•6 + 1,

aber 37 !≡ 73 mod 7, da 37 = 5•7 + 2 und 73 = 10•7 + 3.

1210 ≡ 0 mod 11, denn 1210 = 110•11 + 0

 

 

Wir betrachten teilerfremde Zahlen a, n Î N, dh. ggT(a; n) = 1

Beispiel 1:      a = 3; n = 5

Der Berlekampalgorithmus liefert eine Vielfachsummendarstellung des ggT 1

            1 =       a * a*    +          n * n*

            1 =       3 * 2    +          5 *(-1)

 

Frage:  Welchen Rest lässt a*a' bei Division durch 5?

            3*2 = 1 + 5*(-1), d.h. 6 ist mit Rest 1 durch 5 teilbar

    -->   3*2 ≡ 6 ≡ 1 mod 5

Die Zahl 2 ist modulares Inverses zu 3 modulo 5.



Beispiel 2:  a = 35; n = 101             

Der BA liefert:    1 = 35*26 + 101*(-9)

Division von 35*26 + 101*(-9) durch 101 lässt den Rest 1, d.h.

35*26 ≡ 1 mod 101



Satz

Teil 1

Für ggT(a; n) = 1 liefert der BA eine Vielfachsummendarstellung:

Es gibt Zahlen   a' , n' ∈   mit

 

            a*a' + n*n' = 1 Division durch n lässt den Rest 1

Û        a*a' ≡ 1 mod n

 

Teil 2

Gilt umgekehrt a*a' ≡ 1 mod n

Û n | a*a' - 1

Û a*a' - 1 ist Vielfaches von n

Û a*a' - 1 = n*n'

Û a*a' - n*n' = 1

Diese diophantische Gleichung ist nur lösbar, wenn ggT(a , n) | 1,
d.h. ggT(a , n) = 1

 

Definition      

Für zwei Zahlen a und n gilt ggT(a , n) = 1

Die Zahl 0 < a' < n  heißt modulares Inverses von a modulo n    
(the modular inverse)

            Û        a*a' ≡ 1 mod n


Aufgabe:         Finde modulare Inverse zu a < 21 modulo 21

 

a

1

2

4

5

8

10

11

13

16

17

19

20

a*

1

11

16

17

8

19

2

13

4

5

10

20

 

Eine Lösung:     2 *11 ≡ 22 ≡ 1 mod 21

 

Bemerkung:

Falls d = ggT(a , n) > 1, dann gibt es kein modulares Inverses.

Beweis:            Wäre für d > 1 die Gleichung a*a' + n*n' = 1 lösbar,

                  dann klammern wir d auf der linken Seite d aus:

d(Aa' + Nn') = 1

Da d > 1, kann das Produkt in nicht 1 sein!

 

Aufgaben (E8)       Modulare Inverse

(a)        Bestimme mit Hilfe des Berlekamp-Algorithmus das modulare Inverse a'
mod 5:             a = 1, 2, 3, 4                           mod 6:             a = 1, 2, 3, 4, 5
mod 7:             a = 1, 2, 3, 4, 5, 6                   mod 100:         a = 17, 21, 25, 97
mod 101:         a = 1, 2, 3, 4, 35

(b)       Löse:
2x ≡ 1 mod 5              5x ≡ 1 mod 17            46x ≡ 1 mod 25          6x ≡ 1 mod 25 
67x ≡ 1 mod 127        66x ≡ 1 mod 109        96x ≡ 1 mod 173        324x ≡ 1 mod 381

(c)        Berechne modulare Inverse zu a = 3, 5, 7, 11, 12, 15, 16, 32  zum Modul n = 91.

(d)       Berechne modulare Inverse zu a= 6, 7, 8, 9, 10, 12, 20, 30, 120 zum Modul n = 19.

(e)        Bestimme für a < 11 alle modularen Inversen modulo 11.

(f)        Bestimme alle modularen Inversen mod 15.

(g)        Löse in :     2x ≡ 4              x*3 ≡ 0            2x ≡ 1              5x ≡ 3              3x ≡ 1

 


Zur�ck Informatik Sekundarstufe I

Zur�ck zur Hauptseite