Restklassenarithmetik |
| 12.02.2011, 15:53 | Langer22 | Auf diesen Beitrag antworten » | ||||
| Restklassenarithmetik Ich hab Probleme beim Lösen folgender Aufgabe: Man gebe den ganzzahligen Rest bei der Berechnung (47^7 + 87^12):44, d.h. man berechne (47^7 + 87^12)mod 44. Meine Ideen: Das Problem bei mir liegt darin das ich nicht so ganz verstanden habe was hinter dem Bgeriff MOD steckt. Aufgaben in dehnen man z.b. die geringste Anzahl an Umfülloperationen berechnen sollte konnte ich lösen. Ich habe es bis jetzt so verstanden das z.B. mod 7 das selbe ist als, wenn man in der Restklasse bzw. mit der Restklasse 7 rechnet. Ist das so Richtig? |
||||||
| 12.02.2011, 16:17 | lgrizu | Auf diesen Beitrag antworten » | ||||
| RE: Restklassenarithmetik Was ist denn die Restklasse 7? Richtig wäre, die Restklassen modulo 7. Restklassen und Modulorechnung prinzipiell nur Teilen mit Rest, wobei die Reste betrachtet werden, so können von beliebigen ganzen Zahlen bei Division durch zum Beispiel 4 folgende möglichen Reste entstehen: 0,1,2,3. Das sind dann die kleinsten positiven Repräsentanten der Restklassen modulo 4 der ganzen Zahlen. Bei deiner Aufgabe kannst du dir erst mal überlegen, welchen Rest 47 bei Division durch 44 erzeugt und diesen dann geeignet potenzieren. Analog kann man 87 betrachten, hier bietet es sich an, den Betragskleinsten Repräsentanten zu betrachten, der in der gleichen Resklasse liegt wie 87 mod 44. Die Ergebnisse kann man dann addieren. |
||||||
| 12.02.2011, 16:43 | Langer22 | Auf diesen Beitrag antworten » | ||||
Also mit restklasse 7 meinte ich modulo 7. Also bei der Aufgabe, 5a + 7b =11 | in (Restklasse) modulo 5 => 0a +2b = 1 => 1b =3 bzw. b= 3+ 5* k , mit k = Rest und a = -2-7* k ------------------------ Bei 47 : 44 hätte ich also den Rest 3 nur wie Potenziere ich den jetzt? |
||||||
| 12.02.2011, 16:58 | lgrizu | Auf diesen Beitrag antworten » | ||||
Modulo 4 gibt es vier Restklassen, es gibt nicht eine Restklasse modulo 4, die Elemente, die in einer Resklasse b modulo a liegen sind die Elemente, die bei Division durch a den selben Rest lassen, wie b. So liegen zum Beispiel 1,5,9 in der gleichen Restklasse modulo 4. Deshalb habe ich in meinem ersten Beitrag den Plural gewählt. 5a+7b=11 soll also modulo 5 gelöst werden, wir bestimmen zuerst die kleinsten Repräsentanten der jeweiligen Restklasse, so liegen 5 und 0 in der gleichen Restklasse modulo 5 und 7 und 2 liegen in der gleichen Restklasse , 11 liegt in der gleichen Restklasse wie 1. Wir können das also darauf beschränken, die Äquivalenz (das "=" ist hier auch nicht ganz richtig) zu lösen. Nun kann a beliebig gewählt werden, das Inverse von 2 modulo 5 ist 3, also . Wie du allerdings auf eine Lösung für a kommst ist mir Schleierhaft, a kann in jeder Resklasse liegen, also beliebig sein. |
||||||
| 12.02.2011, 17:10 | Langer22 | Auf diesen Beitrag antworten » | ||||
Auf a bin ich duchr umstellen der Anfangsgleichung nach a und hab dann den Allgemeinen Ausdruck von B genommen und eingesetzt. -------------------------- Also ich hab mir nochmal ein Youtube Video angeschaut um bei der eigentlichen Problemaufgabe weiter zu kommen und bin jetzt erstmal so weit gekommen: Als erstes hab ich die Summanden im einzeln Betrachtet so wie du bereits sagtest: 47^7 = -1^7 = -1 mod 44 87^12 = -1^12 = -1 mod 44 Gedankengang hierbei war das ich möglichst versucht habe bei beiden auf den selben Rest zu kommen. Ist das soweit erstmal richtig, und wenn ja wie mache ich weiter? ( Der Einfachheit halber hab ich wieder nur Gleichzeichen benutzt) |
||||||
| 12.02.2011, 17:13 | lgrizu | Auf diesen Beitrag antworten » | ||||
Sicher, dass das richtig ist? 
Ich denke, dass ist. Edit: lies dir den letzten Beitrag noch einmal durch, es geht da auch darum, was eine Restklasse ist, es gibt nicht eine Restklasse modulo 7, sondern sieben! |
||||||
| Anzeige | ||||||
|
|
||||||
| 12.02.2011, 17:26 | Langer22 | Auf diesen Beitrag antworten » | ||||
Ja, 47 = 3mod 44 ist auch richtig sofoern ich das richig verstanden habe. nur hätte ich ja bei 87 = 43 mod 44 . Und ich dachte halt das man die Summe nur bilden kann wenn die gleichen Representanten vorhanden sind. Obwohl diese ja hier nicht Positiv sind sondern vom Betrag her die kleinsten. |
||||||
| 12.02.2011, 17:30 | lgrizu | Auf diesen Beitrag antworten » | ||||
87 liegt in der gleichen Restklasse wie 43 und -1, es ist tatsächlich von Vorteil, hier -1 als Repräsentanten der Restklasse zu wählen. Dass eine negative und eine positive Zahl vorkommt ist ganz egal. Aber -1 liegt doch nicht in der gleichen Restklasse modulo 44 wie 3, das ist falsch. Die beiden Repräsentanten, die also zu potenzieren sind sind -1 und 3, nun berechne einmal 3^(12) mod 44. |
||||||
| 12.02.2011, 17:50 | Langer22 | Auf diesen Beitrag antworten » | ||||
87^12 = -1^12 = -1 mod 44 47^7 = 3^7 mod44 Wie kommst du auf 3^12 mod44? Ansatz: Muss man jetzt nicht versuchen die 3^7 etwas um zu schreiben, also bsp: 3^4 *3^3 = 81 * 27 oder sowas in der Art? |
||||||
| 12.02.2011, 17:53 | lgrizu | Auf diesen Beitrag antworten » | ||||
Ich habe die Potenzen durcheinandergebracht, sorry.
Die Idee ist gut, mach mal weiter. |
||||||
| 12.02.2011, 18:05 | Langer22 | Auf diesen Beitrag antworten » | ||||
3^4 *3^3 = 81 * 27 = 37 *27 mhhh einfacher wirds irgendwie gerade nich xD, die 27 stört mich. |
||||||
| 12.02.2011, 18:07 | lgrizu | Auf diesen Beitrag antworten » | ||||
Wir wählen wieder den Betragskleinsten Repräsentanten der Restklasse, in der 81 liegt, dieser ist -7. Nun kann man (-7)*27=-189 schnell ausrechnen, welches ist der kleinste positive Repräsentant der Restklasse, in der auch -189 liegt? |
||||||
| 12.02.2011, 18:17 | Langer22 | Auf diesen Beitrag antworten » | ||||
47^7 = 3^7 mod44 3^7 = 3^4 * 3^3 = 81 *27 = -7 * 27 =-189 -189 = -13 mod 44 ? |
||||||
| 12.02.2011, 18:24 | lgrizu | Auf diesen Beitrag antworten » | ||||
Das ist richtig, wir rechnen, wenn es möglich ist mit den betragskleinsten Repräsentanten einer Restklasse. Üblicherweise geben wir als Ergebnis jedoch den kleinsten positiven Repräsentanten einer Restklasse an, welches ist der kleinste positive Repräsentant der Restklasse, in der -13 und -189 liegen? |
||||||
| 12.02.2011, 19:11 | Langer22 | Auf diesen Beitrag antworten » | ||||
Ich hab keine ahnung 
|
||||||
| 12.02.2011, 20:25 | lgrizu | Auf diesen Beitrag antworten » | ||||
Es ist -13+44=31. |
||||||
|
|