Kongruenz mit Exponent |
| 18.01.2015, 12:54 | Tri | Auf diesen Beitrag antworten » | ||||
| Kongruenz mit Exponent Hallo 
Ich soll folgende Kongruenz lösen: Meine Ideen: Offensichtlich löst x=1 (mod 91) die Kongruenz. Durch Probieren hab ich auch gesehen dass 3,4,9,10,12,16,17 funktionieren (aber natürlich sehe ich da keinen Zusammenhang). In einem anderen Thread habe ich vom Logarithmieren zur Basis einer Primitivwurzel modulo 91 gelesen, aber wir hatten den dazugehörigen Satz nicht in der Vorlesung... gibt es denn noch eine andere Variante? |
||||||
| 18.01.2015, 13:24 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Das dürfte schwierig sein, da es gar keine Primitivwurzeln modulo 91=7*13 gibt. 
Löse die beiden Einzelkongruenzen und kombiniere diese Lösungen gemäß Chinesischem Restsatz. |
||||||
| 18.01.2015, 13:59 | Tri | Auf diesen Beitrag antworten » | ||||
Aber ich weiß irgendwie nicht, wie man diese Kongruenzen löst... bis jetzt hatten wir nur Kongruenzen der Form ax=b (mod c) ohne Exponenten. |
||||||
| 18.01.2015, 14:08 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Zunächst mal kannst du die Exponenten reduzieren gemäß (kleinen) Satz von Fermat. Was besagt der für die Primzahlmodule 7 bzw. 13 ? |
||||||
| 18.01.2015, 14:19 | Tri | Auf diesen Beitrag antworten » | ||||
Achso. Also ist . Und x^90 kann ich zerlegen. Also |
||||||
| 18.01.2015, 14:32 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Ich meinte den Fermat eigentlich in der Form für alle (der Wert kommt ja eh nicht als Lösung in Frage). |
||||||
| Anzeige | ||||||
|
|
||||||
| 18.01.2015, 14:50 | Tri | Auf diesen Beitrag antworten » | ||||
Und zufälliger Weise teilt 6 die 90... also ist nun x^90 = (x^6)^15 = 1^15 = 1 mod 7 und deshalb ist die ursprüngliche Kongruenz gelöst für alle x die keine Vielfachen von 7 sind? Die zweite Kongruenz ist aber nicht so: Fermat gibt x^12 = 1 mod 13 und zerlegen bringt (x^12)^7*x^6 = 1 mod 13 und das vereinfacht sich zu x^6 = 1 mod 13 weil der erste Faktor 1 ist. Wie kann ich das lösen, außer wieder mit x=1? |
||||||
| 18.01.2015, 15:54 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Richtig.
Eine Möglichkeit: Alle 12 Werte (außer 0) durchprobieren - eigentlich zu rechnen sind da sogar nur 6 (wg. +-). Ein anderer Aspekt: Ist quadratischer Rest modulo 13, d.h. mit , so ist . Ist es hingegen quadratischer Nichtrest, so folgt . |
||||||
| 18.01.2015, 20:49 | Tri | Auf diesen Beitrag antworten » | ||||
Okay. Die zweite Teilkongruenz wird von allen x erfüllt, die kongruent zu 1, 3, 4, 9, 10 oder 12 in modulo 13 sind. Reicht es jetzt als Lösung zu sagen, dass x beide Teilkongruenzen erfüllen muss? Wie kann ich den chinesischen Restsatz schlau anwenden? Ich seh nur ganz viele "einzelne" Simultankongruenzen, die zu lösen wären. Sowas wie x=1 mod 7 und x= 1 mod 13. Und dann die nächste x=1 mod 7 und x=2 mod 13. Und die nächste x=3 mod 7 und x=4 mod 13. Das kann ich doch unmöglich alles rechnen müssen 
|
||||||
| 19.01.2015, 09:32 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Es sind schon ziemlich viele Lösungen, das ist richtig: Von den primen Restklassen modulo 91 sind immerhin , also genau die Hälfte, tatsächlich auch Lösungen dieser Kongruenz. Man kann natürlich einfach so vorgehen: Schreibe die 6 Lösungen modulo 13 als Lösungen modulo 91 (also +13k), das sind 1,3,4,9,10,12, 14,16,17,22,23,25, 27,29,30,35,36,38, 40,42,43,48,49,51, 53,55,56,61,62,64, 66,68,69,74,75,77, 79,81,82,87,88,90 Von diesen 42 Zahlen musst du jetzt noch die durch 7 teilbaren Zahlen streichen, dann hast du deine 36 Lösungen modulo 91. |
||||||
| 20.01.2015, 10:05 | Tri | Auf diesen Beitrag antworten » | ||||
Ah ja das is clever. Vielen Dank!
|
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
