Worksheet: Unterschied zwischen den Versionen

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche
Zeile 1: Zeile 1:
 
__NOTOC__
 
__NOTOC__
[http://http://wiki.zum.de/PH_Heidelberg/Bausteine/Der_chinesische_Restsatz/Worksheet&printable=yes Druckversion]
+
[http://wiki.zum.de/PH_Heidelberg/Bausteine/Der_chinesische_Restsatz/Worksheet&printable=yes Druckversion]
  
 
== Motivation ==
 
== Motivation ==

Version vom 19. Juni 2013, 16:09 Uhr

Druckversion

Motivation

Als Motivation gelte einmal folgendes Beispiel: Ich habe x Bonbons. Wenn ich diese Bonbons an 4 Personen verteile, bleiben 2 Bonbons übrig. Wenn ich sie an 7 Personen verteile, bleiben 3 Bonbons übrig. Wie viele Bonbons habe ich?
Das kann man ja evtl. noch durch Ausprobieren lösen. Wie sieht es aber mit folgendem Problem aus...

Eine alte Frau geht über den Marktplatz. Ein Pferd tritt auf ihre Tasche und zerbricht die gekauften Eier. Der Besitzer des Pferdes möchte den Schaden ersetzen und fragt die alte Frau, wie viele Eier in ihrer Tasche waren. Sie weiß die exakte Zahl nicht mehr, aber sie erinnert sich, dass genau ein Ei übrig bleibt, wenn sie beim Auspacken die Eier immer zu zweit aus der Tasche nimmt. Das Gleiche geschieht, wenn sie die Eier immer zu dritt, zu viert, zu fünft und zu sechst aus der Tasche nimmt. Nur wenn sie die Eier zu siebt aus der Tasche nimmt, bleibt kein Ei übrig. Was ist die kleinste Zahl an Eiern, welche die alte Frau in ihrer Tasche haben kann?

Aber zurück zum Ausgangsproblem mit den Süßigkeiten...


Erarbeitung anhand eines Beispiels

Warum funktioniert der Chinesische Restsatz? Übernehme das Beispiel aus den Videos und mache dir ergänzende Notizen dazu.

x \ \equiv\ 2 \ mod\ 4
x \ \equiv\ 3 \ mod\ 7







Verallgemeinerung auf zwei Moduln

Es seien m_1 und m_2 teilerfremd und das folgende Kongruenzsystem, das es zu lösen gilt:

  • x\equiv a_1 mod m_1
  • x\equiv a_2 mod m_2

Man bestimmt Zahlen x_1 und x_2 folgendermaßen:



Dann ist eine Lösung \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ , denn



Weitere Lösungen ergeben sich durch


Ganz allgemein: Der chinesische Restsatz

Die Zahlen m_1, ..., m_n seien paarweise teilerfremd. Dann besitzt das Kongruenzsystem

  • x\equiv a_1 mod m_1
  • ...
  • x\equiv a_n mod m_n

eine Lösung x\ mod\ m mit m=m_1\cdot...\cdot m_n und alle weiteren Lösungen y liegen in derselben Kongruenzklasse wie xmodulo m bzw. y\ \equiv\ x\ mod\ m.

Vervollständige den Beweis und mache dir gegebenenfalls Randnotizen:

Man bildet k_i = \frac{m}{m_i}
Dann gilt ggT(k_i,m_i)=1




















Das Eier-Problem

Versuche das Problem der alten Frau mit ihren kaputten Eiern zu lösen. Stelle ein Kongruenzsystem auf und löse es.





























Fragen

Hast du noch Fragen? Notiere sie dir hier, damit du sie in deiner Lerngruppe, in der Übungsstunde oder in der nächsten Plenumssitzung klären kannst!