Wie viele Schüler sind in der Klasse von Herrn Bonaker mindestens?(chinesiche Restsatz/Modulo berechnung)

Question

Aufgabe:

Der Lehrer D. Bonaker möchte seine Schüler für eine Gruppenarbeit in mindestens zwei gleich große Gruppen einteilen. Legt er die Gruppengröße auf 5 Schüler fest, bleiben 4 Schüler  übrig, sollen je 6 Schüler eine Gruppe bilden, bleiben 5 Schüler über. Auch als er die Gruppengröße auf 7 Schüler setzt, bleibt ein Schüler übrig.

a) Wie viele Schüler sind in der Klasse von Herrn Bonaker mindestens?

b) Herr Bonaker hätte nur geduldig weiter suchen müssen, so hätte er eine Gruppeneinteilung gefunden. Mit dieser Information: Wie viele Schüler sind in der Klasse von Herrn Bonaker mindestens?

Problem/Ansatz:

ist meine Lösung für Teil a richtig oder hab ich die Aufgabe falsch verstanden?

… Teil b hab ich gar nicht verstanden .

a )    x1 Kongruenz 4 (mod5)

        x2 Kongruenz 5 (mod6)

        x3 Kongruenz 1 (mod7)

M = 6.5.7=240

M1=42    M2=3    M3=30

x1.42 Kongruenz 1(mod5)       ===> x1 = 3

x2. 35 Kongruenz 1(mod6)      ===> x2 =5

x3 . 30 Kongruenz 1(mod7)     ===>x3 = 4

4.3.42+5.5.35+1.4.30=  894

894 - (3.240)= 174

Comments

Jemand eine Idee zu der b) ?

Haben nur den Hinweis bekommen, dass die Lösung aus a) dann nicht mehr stimmt und wir die kleinste Lösung aus der simultanen Kongruenz nehmen solle.

---

Ist das ein Kommentar / eine Ergänzung oder eine Antwort auf die Frage oder eine der Antworten ? Du hast deinen Beitrag als "Antwort" auf die Frage eingegeben. D.h. ausser dem Fragesteller wird niemand benachrichtigt. 

---

Ja, ich raff's einfach nicht, deswegen Frage. Aufgabenteil b) ist doch dasselbe wie a)? Warum meint unser Prof, dann das die Lösung aus a) unter Annahme von Aufgabenteil b) nicht stimmt und wir die kleinste Lösung aus der simultanen Kongruenz nehmen sollten. Aber genau das macht man doch schon bei der a.

---

Ich habe mir gerade nochmal die Vorlesung dazu angesehen und er meinte

"Die Idee ist, dass sie in Aufgabe b) eine zusätzliche Information haben, nicht wahr. Da steht "angenommen, Sie wissen, dass dieser Lehrer seinen Kurs in Gruppen hätte aufteilen können und oben steht, in mindestens 2 Gruppen, das ist eine zusätzliche Information, die Sie haben, nicht wahr. Vermutlich erfüllt diese Lösung, die sie in Aufgabe a) herausgefunden haben, diese Bedingung nicht, dass der Lehrer, wenn er nur lang genug gesucht hätte, nicht nach 5,6,7 Gruppen schon aufgegeben hätte, es geschafft hätte, sie aufzuteilen in gleich große Gruppen. Das heißt die Antwort aus der a) ist nicht die Antwort für die Aufgabe b). Der chinesische Restsatz gibt Ihnen ja nicht nur eine Lösung für die simultane Kongruenz, sondern ne ganze Menge. Versuchen Sie mal, ob sie die kleinste finden, die es ihnen erlaubt, diese Klasse aufzuteilen in gleich große Gruppen. So, mit diesem Hinweis hab ich Ihnen die Aufgabe quasi schon gelöst."

Ich bin verwirrt, weil die kleinste positive Lösung ist doch diejenige, die man in a genommen hat, um die mindestanzahl der Schüler zu finden.

---

War das denn (auch) deine Frage? Ich habe aus deiner Antwort nun mal einen Kommentar zur Frage gemacht. Nun bitte Geduld und Duplikate vermeiden. mathef wird sich bestimmt nochmals melden auf deine Kommentare. 

Answer 1

Die Schüleranzahl nach den Bedingungen von a) ist mindestens  29.

Comments

würdest du bitte erklären wie du auf 29 kommst

---

x ist kongruent zu 4 mod 5. Damit gilt auch x ist kongruent -1 mod 5.

x ist kongruent zu 5 mod 6. Damit gilt auch x ist kongruent -1 mod 6.

Somit gilt x ist kongruent -1 mod 30.

x ist also 29 oder 59 oder 89 oder 119 oder...

Die 29 erfüllt glücklicherweise auch ohne weiteres Suchen die dritte Bedingung, ist allerdings nicht die Lösung zu b).

Teste dafür  59 oder 89 oder 119 oder...

Answer 2

Es sind mindestens 29; denn

29 ≡ 1 mod 7

29 ≡ 5 mod 6

29 ≡ 4 mod 5

Comments

wie kommst du auf 29?

---

Du hattest dich vertan.

M = 6.5.7=240 ist aber 210

und

M1=42    M2=35    M3=30

und am Schluss

4.3.42+5.5.35+1.4.30=  1499

1499 - (7.210)= 29

So geht es nach dem chin. Restsatz.

---

Wie kommst auf die Zeile

4*3*42 + 5*5*35 + 1*4*30 = 1499

Also 42, 35 und 30 ist klar, weil M1, M2 und M3

Die werden dann jeweils noch mit den Schülern multipliziert die übrig geblieben sind, also

42*4 + 5*35 + 1 * 30

Aber warum müssen die dann mit *3, *5 und 4* multipliziert werden?

Und warum 1499 - (7 * 210) und nicht etwa 1499 - (6* 210) und 1499 - (5 * 210)

Mein Ansatz wäre

M1 = m2 * m3 = 6 * 7 = 42

M2 = m1 * m3 = 5 * 7 = 35

M3 = m1 * m2 = 5 * 6 = 30

Mittels euklischen Algorithmus werden die Darstellungen berechnet

1 = s1 * M1 + t1 * m1 = (-2) * 42 + 17 * 5

1 = s2 * M2 + t2 * m2 = (-1) * 35 + 6 * 6

1 = s3 * M3 + t3 * m3 = (-3) * 30 + 13 * 7


t1 = s1 * M1 = (-2) * 42 = - 84

t2 = s2 * M2 = (-1) * 35 = -35

t3 = s3 * M3 = (-3) * 30 = -90


a = a1 * b1 + a2 * b2 + a3 * b3

  = 4 * (-84) + 5* (-35) + 1* (-90)

  = -601

M = m1 * m2 * m3 = 4 * 5 * 1 = 20

Die Menge aller Lösungen der simulanten Kongruenz ist somit

{ - 601 + k * 20: k € Z}.

So, aber was ist jetzt die kleinste positive Lösung? In dem Fall doch eher 19, weil

-601 + 31 * 20 = 19

---

Achso, weil -601 + 210 + 210 + 210 = 29. SORRY

---

Aber warum müssen die dann mit *3, *5 und 4* multipliziert werden?

Das sind die Inversen von 42 mod 5

, 35 mod 6     bzw. 30 mod 7.

Damit musst du multiplizieren, damit z.B. mod 5 auch

wirklich der gewünschte Rest   bleibt.

Sehr schön erklärt bei

https://www.bing.com/videos/search?q=chinesischer+restsatz&view=detail&mid=09612378658132758DEF09612378658132758DEF&FORM=VIRE

Answer 3

zu a)

Du hast folgendes Gleichungssystem:

Das kleinste n ist offensichtlich 0 und damit ergibt sich

x = 210 * 0 + 29

x = 29

als kleinstes x und somit als Mindestanzahl für die Schüler in der Klasse.