Kongruenzen und Gleichungen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 15:15 Do 31.12.2009 | | Autor: | pitmat |
| Aufgabe | Gesucht sind alle a, für die gilt:
a^28 kongruent zu 13 modulo 28 |
Hat vielleicht jemand einen Tipp, wie man an so eine Aufgabe rangehen kann? Nur einen Miniansatz, ich möchte das dann auch selbst weiter lösen! Danke!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:39 Do 31.12.2009 | | Autor: | leduart |
Hallo
hilft dir [mm] 13^2=1mod28
[/mm]
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:56 Do 31.12.2009 | | Autor: | pitmat |
Leider nicht. Was bringt mir das, wie macht man dann weiter?
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:27 Do 31.12.2009 | | Autor: | pitmat |
Wieso steht da: Reaktion unnötig ? Ich finde das nicht unnötig ...
Wenn [mm] 13^2 [/mm] mod 28 = 1 mod 28 ist, ist [mm] 13^3 [/mm] mod 28 = x^28 mod 28 - eine neue Gleichung und wie macht man damit weiter?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:38 Do 31.12.2009 | | Autor: | abakus |
> Wieso steht da: Reaktion unnötig ? Ich finde das nicht
> unnötig ...
>
> Wenn [mm]13^2[/mm] mod 28 = 1 mod 28 ist,
... ist [mm] x^{56} \equiv [/mm] 1 mod 28.
Gruß Abakus
> ist [mm]13^3[/mm] mod 28 = x^28 mod
> 28 - eine neue Gleichung und wie macht man damit weiter?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:53 Do 31.12.2009 | | Autor: | pitmat |
Ja, stimmt, aber wie löse ich das auf? Ich kann das jetzt ausprobieren und alle x suchen, aber wie kann man das ohne Ausprobieren lösen? (ich glaub, ich bin gerade etwas doof.)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:16 Do 31.12.2009 | | Autor: | abakus |
> Ja, stimmt, aber wie löse ich das auf? Ich kann das jetzt
> ausprobieren und alle x suchen, aber wie kann man das ohne
> Ausprobieren lösen? (ich glaub, ich bin gerade etwas
> doof.)
Hallo,
wenn [mm] x^{56} [/mm] bei Teilung durch 28 den Rest 1 lässt, entsteht der Rest 1 auch, wenn man [mm] x^{56} [/mm] durch 4 bzw. durch 7 teilt.
Es gilt also [mm] x^{56}\equiv [/mm] 1 mod 7 und [mm] x^{56} \equiv [/mm] 1 mod 4.
Nach dem kleinen Fermat gilt (falls x nicht durch 7 teilar ist) [mm] x^6\equiv [/mm] 1 mod 7 und damit auch [mm] x^{54}\equiv [/mm] 1 mod 7.
Gruß Abakus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:53 Do 31.12.2009 | | Autor: | pitmat |
danke! den allerletzten Schritt verstehe ich aber nicht - wie kommst du nun auf [mm] x^6 [/mm] bzw. x^54 ist kongruent mod 7?
|
|
|
| |
|
Hallo pitmat,
> danke! den allerletzten Schritt verstehe ich aber nicht -
> wie kommst du nun auf [mm]x^6[/mm] bzw. x^54 ist kongruent mod 7?
abakus hat ja geschrieben, daß [mm]x^{6} \equiv 1 \ \operatorname{mod} \ 7[/mm],
falls x nicht durch 7 teilbar ist.
Das gilt nach dem ![[]](/images/popup.gif) kleinen Fermat.
Da [mm]x^{54}=\left(x^{6}\right)^{9}[/mm] gilt auch
[mm]x^{54}=\left(x^{6}\right)^{9} \equiv 1^{9} = 1 \operatorname{mod} \ 7[/mm]
Daher die Kongruenz [mm]x^{54} \equiv 1 \operatorname{mod} \ 7[/mm].
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:56 Do 31.12.2009 | | Autor: | pitmat |
noch eine Frage: Hier ist es ja so, dass 7 und 4 teilerfremd sind und als Produkt 28 ergeben.
Wie würde man vorgehen, wenn man statt x^56 ist kongruent 1 modulo 28 etwa x^56 ist kongruent 1 modulo 32 berechnen müsste?
|
|
|
| |
|
Hallo pitmat,
> noch eine Frage: Hier ist es ja so, dass 7 und 4
> teilerfremd sind und als Produkt 28 ergeben.
>
> Wie würde man vorgehen, wenn man statt x^56 ist kongruent
> 1 modulo 28 etwa x^56 ist kongruent 1 modulo 32 berechnen
> müsste?
Die Kongruenz
[mm]x^{56} \equiv 1 \ \operatorname{mod} \ 32[/mm]
läßt sich dann auf die Kongruenz
[mm]x^{56} \equiv 1 \ \operatorname{mod} \ 2[/mm]
zurückführen.
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:05 Fr 01.01.2010 | | Autor: | pitmat |
Okay, danke, das habe ich verstanden, auch die Antwort zur ersten Frage. Allerdings weiß ich nun nicht: Wie kann man denn x^56 ist kongruent 1 mod 2 noch weiter vereinfachen?
Oder ist das dann das Endergebnis? Das würde dann heißen, dass x ungerade ist, aber das hätte man auch gleich erkennen können und das stimmt dann auch nicht immer. also wenn du Aufgabe zum Beispiel x^28 ist kongruent 17 mod 32 lauten würde, könnte man ja etwa 3 oder 13 einsetzen. Wie bestimmt man dann alle x? Es wäre toll wenn du mir noch einmal damit weiterhelfen könntest!
|
|
|
| |
|
Hallo pitmat,
> Okay, danke, das habe ich verstanden, auch die Antwort zur
> ersten Frage. Allerdings weiß ich nun nicht: Wie kann man
> denn x^56 ist kongruent 1 mod 2 noch weiter vereinfachen?
> Oder ist das dann das Endergebnis? Das würde dann heißen,
> dass x ungerade ist, aber das hätte man auch gleich
> erkennen können und das stimmt dann auch nicht immer. also
> wenn du Aufgabe zum Beispiel x^28 ist kongruent 17 mod 32
> lauten würde, könnte man ja etwa 3 oder 13 einsetzen. Wie
> bestimmt man dann alle x? Es wäre toll wenn du mir noch
> einmal damit weiterhelfen könntest!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:15 Fr 01.01.2010 | | Autor: | pitmat |
kann das sein, dass die eigentliche Antwort irgendwie verloren gegangen ist?
|
|
|
| |
|
Hallo pitmat,
> kann das sein, dass die eigentliche Antwort irgendwie
> verloren gegangen ist?
Ich hab nix gemacht.
Gruss
MathePower
|
|
|
| |
|
Hallo pitmat,
> Okay, danke, das habe ich verstanden, auch die Antwort zur
> ersten Frage. Allerdings weiß ich nun nicht: Wie kann man
> denn x^56 ist kongruent 1 mod 2 noch weiter vereinfachen?
Nun, für welche Zahlen gilt, daß deren 56. Potenz wieder ungerade ist?
Das gilt natürlich für alle ungeraden Zahlen.
> Oder ist das dann das Endergebnis? Das würde dann heißen,
> dass x ungerade ist, aber das hätte man auch gleich
Es stimmt aber, daß die Kongruenz für alle ungeraden Zahlen gilt.
> erkennen können und das stimmt dann auch nicht immer. also
> wenn du Aufgabe zum Beispiel x^28 ist kongruent 17 mod 32
> lauten würde, könnte man ja etwa 3 oder 13 einsetzen. Wie
Nun, 17*17 läßt bei Division durch 32 den Rest 1.
> bestimmt man dann alle x? Es wäre toll wenn du mir noch
> einmal damit weiterhelfen könntest!
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:39 Fr 01.01.2010 | | Autor: | pitmat |
ach je, ich hatte mich nur immer verrechnet ... klar passt das! vielen Dank für deine Hilfe!
|
|
|
| |
|
Hallo pitmat,
Kongruenzen sind eine oft erstaunliche Angelegenheit. Dein Beispiel [mm] \mod{32} [/mm] mag zufällig sein, aber es hat eine außergewöhnliche Sonderstellung.
Für ungerade [mm] p\in\IP [/mm] ist [mm] x^k\equiv 1\mod{p^n} [/mm] für alle zu p teilerfremden x bei [mm] k=(p-1)p^{n-1}. [/mm] Es gibt aber noch andere k, jedenfalls für bestimmte x.
Bei den Zweierpotenzen ist die Lage eine andere. Es ist [mm] x^k\equiv 1\mod{2^n} [/mm] für alle ungeraden x (und n>2) bei [mm] k=2^{n-2}, [/mm] was der vorigen Formel ja nicht entspricht.
Restklassen zum Modul einer Primzahlpotenz sind also ein Sonderfall, der nicht so einfach zu lösen ist. Bleib also erst einmal in dem Bereich, den ihr auch behandelt. Es ist ein bisschen wie an der Grundschule, wo man m.W. heute in der 1. Klasse im Zahlenraum bis 20 rechnet, in der 2. dann bis 100 oder gar 1000, in der 3. bis zu einer Million. Am Anfang geht es um die grundlegenden Fertigkeiten und die prinzipielle Einsicht, erst später um die generelle Erweiterung. In der 5. Klasse müsste man jedenfalls auch mit 2674-stelligen Zahlen rechnen können, wenn man soviel Zeit hätte. Das ist bei den Restklassen nicht anders...
Nur Mut! Das Thema ist spannend und vielfältig. Es verlangt aber ein bisschen Denkarbeit und die Bereitschaft, Erwartungen aufzugeben. Oft ist es eben anders, als man vorher dachte.
lg
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:22 Sa 02.01.2010 | | Autor: | pitmat |
Danke für deine ausfühliche Antwort! Allerdings bin ich nun total verwirrt - könntest du mir vielleicht für diese ausgedachte neue Aufgabe konkret sagen, was da die Lösung wäre?
also x^28 ist kongruent zu 17 mod 32
dass man auf x^56 ist kongruent zu 1 mod 2 kommt, ist das denn noch richtig? mich verwirrt, dass man 1 nicht einsetzen kann in die Ausgangsgleichung. und zu deiner Formel passt es auch nicht. damit käme man ja nur zu [mm] x^2 [/mm] ist kongruent 1 mod 8, aber auch das passt doch nict in die Ausgangsgleichung ..
wie löst man das hier?
|
|
|
| |
|
Hallo pitmat,
kurz im Vorübergehen (bin gerade mit einer anderen Arbeit beschäftigt)...
Du hattest zwei Aufgaben erdacht.
Eine hieß: [mm] x^{56}\equiv 1\mod{32}. [/mm]
Die vollständige Lösung hat Dir MathePower schon gegeben: [mm] x\equiv 1\mod{2}. [/mm] Mit anderen Worten: jede ungerade Zahl erfüllt die Ausgangsgleichung.
Das liegt daran, dass für jedes ungerade n gilt [mm] n^8\equiv 1\mod{32}, [/mm] und damit auch für jeden Exponenten, der ein Vielfaches von 8 ist - wie z.B. 56.
Die andere Aufgabe war [mm] x^{28}\equiv 17\mod{32}.
[/mm]
Das können wir mit dem Wissen um Kongruenzen zu einem Zweierpotenzmodul erst einmal vereinfachen auf [mm] x^4\equiv 17\mod{32}.
[/mm]
Nun ist die einfachste Vorgehensweise, in zwei Stufen die quadratischen Reste [mm] \mod{32} [/mm] zu betrachten. (Die vierte Potenz wird ja oft als "Biquadrat" bezeichnet.)
17 ist ein quadratischer Rest. Sei [mm] z=x^2, [/mm] dann sind Lösungen von [mm] z^2\equiv 17\mod{32}\quad z=\pm7 [/mm] und [mm] z=\pm9, [/mm] also [mm] z\in\{7,9,23,25\}_{\mod{32}}
[/mm]
Nun sind aber 7 und 23 keine quadratischen Reste, so dass wir uns auf der Suche nach x beschränken können auf [mm] x^2\equiv 9\mod{32} [/mm] und [mm] x^2\equiv 25\mod{32}.
[/mm]
Über die quadratischen Reste zu einem Zweierpotenzmodul [mm] 2^n [/mm] kann man noch wissen, dass sie [mm] \mod{2^{n-1}} [/mm] gleich sind. Es genügt also, hier die Zahlen bis 16 zu untersuchen, und selbst von denen nur die Hälfte, da [mm] k^2\equiv (16-k)^2\mod{32} [/mm] ist. Bleiben die Zahlen 1 bis 8.
Weiter kannst Du folgern, dass x ungerade sein muss.
Damit bleiben noch die Werte 1,3,5,9 auf ihren quadratischen Rest zu untersuchen.
Es zeigt sich, dass 3 und 5 jeweils einen der gesuchten Reste ergeben. Damit sind also Lösungen der gesuchten Kongruenz [mm] x^{28}\equiv 17\mod{32} [/mm] die folgenden:
[mm] x=\blue{3}
[/mm]
[mm] x=\blue{5}
[/mm]
[mm] x=16-\blue{5}=11
[/mm]
[mm] x=16-\blue{3}=13
[/mm]
[mm] x=\blue{3}+16=19
[/mm]
[mm] x=\blue{5}+16=21
[/mm]
[mm] x=(16-\blue{5})+16=27
[/mm]
[mm] x=(16-\blue{3})+16=29
[/mm]
also [mm] x\in\{3,5,11,13,19,21,27,29\}_{\mod{32}}
[/mm]
***
Ein Tipp: schmeiß nie zufällig erdachte Restklassenaufgaben in die Runde. Vielleicht wolltest Du die Antwort ja doch noch gar nicht wissen. 
Viel Erfolg weiterhin, das Thema ist vielfältig...
reverend
|
|
|
|
