Kongruenzen lösen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Löse die Kongruenz [mm] x^7 \equiv [/mm] 1 (mod 29) |
Hi,
wisst ihr vielleicht,wie man solche Kongruenzen löst?? Dazu habe ich leider nichts gefunden....
Grüße
|
|
| |
|
Hallo jaruleking,
das kann ich nicht beantworten, aber ein paar Hinweise hätte ich:
> Löse die Kongruenz [mm]x^7 \equiv[/mm] 1 (mod 29)
Der Modul 29 ist prim und es gilt [mm] 29\equiv 1\mod{7}, [/mm] wobei die 7 hier der o.g. Exponent ist. Es gibt also ein k, so dass 29=k*7+1 ist, k=4.
Dann gibt es in der 7. Potenz nur k=4 Restklassen, in die alle zu 29 teilerfremden Zahlen fallen. (Diese sind hier: 1,12,17,28 - gerade die Zahlen, für die gilt: $ [mm] m^4\equiv 1\mod{29} [/mm] $)
Außerdem ist auch vorherzusagen, dass Deine Kongruenz genau 7 Lösungen hat (hier: 1,7,16,20,23,24,25). Es sind logischerweise alle Elemente der Restklassengruppe, die die Ordnung 7 haben.
Nur wie man die ermittelt, weiß ich nicht. Außer wie hier mit einer Tabellenkalkulation, meine ich...
Grüße
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:04 Sa 23.07.2011 | | Autor: | Arniebo |
Hallo,
wie es ganz genau geht, weiß ich nicht, allerdings habe ich eine Idee, über die man vielleicht suchen könnte: mit der Eulersche Phi-Funktion und der Formel [mm] a^\varphi(m) \equiv [/mm] (mod m), da [mm] \varphi(29)=28, [/mm] da es eine Primzahl ist, und 28*4=7 ist.
Weiter weiß ich allerdings auch nicht.
Liebe Grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:20 Sa 23.07.2011 | | Autor: | felixf |
Moin,
> Löse die Kongruenz [mm]x^7 \equiv[/mm] 1 (mod 29)
>
> wisst ihr vielleicht,wie man solche Kongruenzen löst??
> Dazu habe ich leider nichts gefunden....
einiges haben meine Vorredner ja schon dazu gesagt.
Um alle Loesungen zu finden, geht man wie folgt vor. Man sucht sich zuerst eine Primitivwurzel modulo 29, also eine ganze Zahl $a$ mit [mm] $a^n \equiv [/mm] 1 [mm] \pmod{29} \Leftrightarrow [/mm] 28 [mm] \mid [/mm] n$ (die multiplikative Ordnung ist also 28).
Jetzt kann man jede ganze Zahl $b$, die nicht kongruent zu 0 modulo 29 ist, als [mm] $a^b \mod [/mm] 29$ darstellen mit $b [mm] \in \IN$, [/mm] und wenn man $0 [mm] \le [/mm] b < 28$ fordert, dann ist die Darstellung sogar eindeutig.
Sei also $x = [mm] a^b$; [/mm] damit [mm] $x^7 [/mm] = [mm] a^{7 b} \equiv [/mm] 1 [mm] \pmod{29}$ [/mm] ist, muss $7 b$ ein Vielfaches von 28 sein. Das ist aber genau dann der Fall, wenn $b$ ein Vielfaches von [mm] $\frac{28}{7} [/mm] = 4$ ist. Da $0 [mm] \le [/mm] b < 28$ gelten muss, bleibt somit $b [mm] \in \{ 0, 4, 8, 12, 16, 20, 24 \}$.
[/mm]
Wenn du also [mm] $a^0, a^4, a^8, a^{12}, \dots, a^{24}$ [/mm] modulo 29 bestimmst, hast du alle Loesungen der Kongruenz [mm] $x^7 \equiv [/mm] 1 [mm] \pmod{29}$. [/mm] (Und so ein $a$ musst du natuerlich auch erstmal bestimmen. Oft kann man $a = 2$ oder $a = 3$ nehmen, und du musst nur schauen ob [mm] $a^{28/7} \not\equiv [/mm] 1 [mm] \pmod{29}$ [/mm] und [mm] $a^{28/2} \not\equiv [/mm] 1 [mm] \pmod{29}$ [/mm] ist (da 28 nur die Primfaktoren 2 und 7 hat).
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:19 Sa 23.07.2011 | | Autor: | jaruleking |
hi,
vielen Dank für eure tipps.
grüße
|
|
|
|
