Teilbarkeit < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:38 Sa 14.07.2012 | | Autor: | Manu87 |
| Aufgabe | Sei $N$ eine ganze Zahl und $m$ eine zu $N$ teilerfremde Zahl. Beweisen Sie: Es gibt eine ganze Zahl $n [mm] \geq [/mm] 1$ so, dass: [mm] $N|(m^n [/mm] - 1)$. Finden Sie jeweils das kleinste $n$ für $m = 3, 5, 7$ und $N = 358.$
Hinweis: Überlegen Sie, welche $n$ in Frage kommen, und potenzieren Sie möglichst effzient |
Hallo,
also ich stehe hier abartig auf dem Schlauch und weiß nicht einmal wie ich ansetzen soll. Wenns hilft: Titel der Aufgabe ist multiplikative Ordnung. Und mit diesem effizientem Potenzieren ist ![[]](/images/popup.gif) binäre Exponentiation gemeint. Trotz allem weiß ich nicht wie ich die Sache angehen soll...
Ich habe es schon irgendwie mit dem euklidischen Algo weiter zu kommen, àla [mm] $\operatorname{ggT}(N,m^n-1)$, [/mm] aber das hat mich auch nicht sonderlich weiter gebracht...
Ein kleiner Denkanstoß und/oder ein paar Stichwörter wären sehr nett.
Gruß
Manuel
EDIT:
Okay ich glaube ich habe eine Lösung gefunden. Zumindest für den Beweis.
Aus der Aufgabe geht hervor $N [mm] \in \mathbb{Z}, m\in \mathbb{N}, [/mm] n [mm] \in \mathbb{N}^*,m \bot N$.\\
[/mm]
Zu zeigen:
[mm] $$\exists [/mm] n : [mm] N|m^n-1$$
[/mm]
[mm] $$\Leftrightarrow&m^n\equiv [/mm] 1 [mm] (\operatorname{mod}N)$$
[/mm]
[mm] \textbf{Satz von Euler.} [/mm] Sei [mm] $a\bot [/mm] b$, dann gilt:
[mm] $$a^{\varphi(b)}\equiv [/mm] 1 [mm] (\operatorname{mod}b)$$
[/mm]
Wähle nun [mm] $n=\varphi(N)$. [/mm] Aus [mm] $\varphi: \mathbb{Z}\rightarrow \mathbb{N}$, [/mm] $m [mm] \bot [/mm] N$ und dem Satz von Euler folgt [mm] $\exists [/mm] n : [mm] N|m^n-1$ [/mm] ist eine Tautologie.
Wie bekomme ich jetzt die kleinsten n raus?
|
|
| |
|
Hallo Manuel,
da bist Du doch auf dem völlig richtigen Weg!
> Sei [mm]N[/mm] eine ganze Zahl und [mm]m[/mm] eine zu [mm]N[/mm] teilerfremde Zahl.
> Beweisen Sie: Es gibt eine ganze Zahl [mm]n \geq 1[/mm] so, dass:
> [mm]N|(m^n - 1)[/mm]. Finden Sie jeweils das kleinste [mm]n[/mm] für [mm]m = 3, 5, 7[/mm]
> und [mm]N = 358.[/mm]
> Hinweis: Überlegen Sie, welche [mm]n[/mm] in Frage
> kommen, und potenzieren Sie möglichst effzient
>
> Hallo,
>
> also ich stehe hier abartig auf dem Schlauch und weiß
> nicht einmal wie ich ansetzen soll. Wenns hilft: Titel der
> Aufgabe ist multiplikative Ordnung. Und mit diesem
> effizientem Potenzieren ist
> binäre Exponentiation
> gemeint. Trotz allem weiß ich nicht wie ich die Sache
> angehen soll...
>
> Ich habe es schon irgendwie mit dem euklidischen Algo
> weiter zu kommen, àla [mm]\operatorname{ggT}(N,m^n-1)[/mm], aber
> das hat mich auch nicht sonderlich weiter gebracht...
>
> Ein kleiner Denkanstoß und/oder ein paar Stichwörter
> wären sehr nett.
>
> Gruß
> Manuel
>
>
> EDIT:
> Okay ich glaube ich habe eine Lösung gefunden. Zumindest
> für den Beweis.
Ja, aber nicht nur das.
> Aus der Aufgabe geht hervor [mm]N \in \mathbb{Z}, m\in \mathbb{N}, n \in \mathbb{N}^*,m \bot N[/mm][mm] .\\
[/mm]
>
> Zu zeigen:
>
> [mm]\exists n : N|m^n-1[/mm]
> [mm]\Leftrightarrow&m^n\equiv 1 (\operatorname{mod}N)[/mm]
>
> [mm]\textbf{Satz von Euler.}[/mm] Sei [mm]a\bot b[/mm], dann gilt:
> [mm]a^{\varphi(b)}\equiv 1 (\operatorname{mod}b)[/mm]
> Wähle nun
> [mm]n=\varphi(N)[/mm]. Aus [mm]\varphi: \mathbb{Z}\rightarrow \mathbb{N}[/mm],
> [mm]m \bot N[/mm] und dem Satz von Euler folgt [mm]\exists n : N|m^n-1[/mm]
> ist eine Tautologie.
Ok. So weit, so gut.
> Wie bekomme ich jetzt die kleinsten n raus?
Das kleinste n ist definiert als [mm] n=ord(m)\mod{N}
[/mm]
Schreibweisen davon variieren, z.B. auch [mm] ord_N(m) [/mm] etc.
Sicher gilt aber [mm] ord_N(m)|\varphi(N)
[/mm]
Nun ist N=358=2*179, also [mm] \varphi(N)=178=2*89
[/mm]
edit: Ich bin echt zu blöd zum Rechnen...
Also ist [mm] ord_N(m)\in\{2,89,178\}.
[/mm]
Ob die binäre Exponentiation für 89 besser ist oder die Zerlegung [mm] 89=(8+1)^2+8, [/mm] musst Du mal nachrechnen. Vielleicht auch 89=8*11+1 oder 89=(4+1)*(16+1)+4? Das sieht aber nicht besser aus...
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:25 So 15.07.2012 | | Autor: | Manu87 |
> > Wie bekomme ich jetzt die kleinsten n raus?
>
> Das kleinste n ist definiert als [mm]n=ord(m)\mod{N}[/mm]
> Schreibweisen davon variieren, z.B. auch [mm]ord_N(m)[/mm] etc.
>
> Sicher gilt aber [mm]ord_N(m)|\varphi(N)[/mm]
Wie nennt sich das? Hat dieser Satz einen Namen? Oder wonach muss ich suchen um das und das drumherum zu vertstehen.
Danke für deine Hilfe
EDIT
Also ich nutze den Lagrange. Der sagt mir die Ordnung eines Elementes einer Gruppe, hier $m$ oder $3$ in der Aufgabe, teilt die Ordnung der Gruppe also hier $N$ bzw $358$.
Nach Euler gilt hier auf jeden Fall
[mm] $$3^{\varphi(358)} \equiv [/mm] 1 [mm] (\operatorname{mod} [/mm] 358)$$
[mm] $$3^{178} \equiv [/mm] 1 [mm] (\operatorname{mod} [/mm] 358)$$
[mm] $$3^{2*89} \equiv [/mm] 1 [mm] (\operatorname{mod} [/mm] 358)$$
Okay am Ende dann die Primfaktorzerlegung. Aber wie bekomme ich die 2 da raus?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:42 So 15.07.2012 | | Autor: | hippias |
In einer endlichen Gruppe wird die Gruppenordnung (= Anzahl der Elemente) von der Ordnung jeder Untergruppe geteilt (Satz von Lagrange). Speziell fuer zyklische Untergruppen, also die, die von einem Element erzeugt werden, bezeichnet man die Ordnung mit $ord$ etc. Die zu $N$ teilerfremden Zahlen bilden Modulo $N$ eine Gruppe der Ordnung [mm] $\phi(N)$.
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:54 So 15.07.2012 | | Autor: | Manu87 |
Jaaa ich bin Mittlerweile total verwirrt. Lagrange hatten wir in der Gruppentheorie definiert, ebendo wie Fermat jetz in der Ringtheorie, da es eine aktuelle Aufgabe ist vermute ich dass ich mich in Ringen bewege. Gilt jetzt Lagrange auch in Ringen? Und was ist mit Fermat?!?!? ich blicks langsam wirklich nicht mehr. Unser Professor springt auch nur noch wie wild zwischen den Themen hin und her... gerade abstrakt Algebra sollte definitiv sehr strukturiert vermittelt werden... :-/
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:23 So 15.07.2012 | | Autor: | hippias |
Ein mathematischer Satz gilt zu jeder Tag- und Nachtzeit, solange seine Voraussetzungen erfuellt sind. Wenn Du in einem Ring eine Gruppe findest, dann kannst Du alle Saetze anwenden, die in Gruppen gelten. Im Ring der Ganzen Zahlen kannst Du den Satz von Fermat anwenden, doch in einem anderen Ring mag das nicht gehen. Du wirst Dich sicher mit all dem Kram noch gut zurecht finden - so wie alle anderen auch.
|
|
|
| |
|
Hallo nochmal,
danke, dass Du meinen Rechenfehler so freundlich ignoriert hast. Ich habs oben mal verbessert. 
> > > Wie bekomme ich jetzt die kleinsten n raus?
> >
> > Das kleinste n ist definiert als [mm]n=ord(m)\mod{N}[/mm]
> > Schreibweisen davon variieren, z.B. auch [mm]ord_N(m)[/mm] etc.
> >
> > Sicher gilt aber [mm]ord_N(m)|\varphi(N)[/mm]
>
> Wie nennt sich das? Hat dieser Satz einen Namen? Oder
> wonach muss ich suchen um das und das drumherum zu
> vertstehen.
>
> Danke für deine Hilfe
> EDIT
> Also ich nutze den Lagrange. Der sagt mir die Ordnung
> eines Elementes einer Gruppe, hier [mm]m[/mm] oder [mm]3[/mm] in der Aufgabe,
> teilt die Ordnung der Gruppe also hier [mm]N[/mm] bzw [mm]358[/mm].
> Nach Euler gilt hier auf jeden Fall
> [mm]3^{\varphi(358)} \equiv 1 (\operatorname{mod} 358)[/mm]
> [mm]3^{178} \equiv 1 (\operatorname{mod} 358)[/mm]
>
> [mm]3^{2*89} \equiv 1 (\operatorname{mod} 358)[/mm]
> Okay am Ende
> dann die Primfaktorzerlegung. Aber wie bekomme ich die 2 da
> raus?
Die bekommst Du nicht weg. Aber man sieht auf einen Blick, dass [mm] \ord_N{m} [/mm] für die gegebenen m nicht 2 sein kann, da [mm] m^2 [/mm] höchstens zweistellig ist, N aber dreistellig, so dass sicher [mm] m^2\not\equiv 1\mod{N}.
[/mm]
Du wirst also überprüfen müssen, was [mm] m^{89}\mod{N} [/mm] ist. Möglich sind da nur noch +1 oder -1.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:32 So 15.07.2012 | | Autor: | Manu87 |
> Die bekommst Du nicht weg. Aber man sieht auf einen Blick,
> dass [mm]\ord_N{m}[/mm] für die gegebenen m nicht 2 sein kann, da
> [mm]m^2[/mm] höchstens zweistellig ist, N aber dreistellig, so dass
> sicher [mm]m^2\not\equiv 1\mod{N}.[/mm]
>
> Du wirst also überprüfen müssen, was [mm]m^{89}\mod{N}[/mm] ist.
> Möglich sind da nur noch +1 oder -1.
>
> Grüße
> reverend
>
Okay also ich vertseh immer noch nicht ganz wie du das gemacht hast.
Was ich mittlerweile irgendwo in irgendeinem Lemma gelesen hab ist, dass [mm] $\operatorname{ord}(m)$ [/mm] ein Teiler von [mm] $\varphi(358)=178$ [/mm] ist. Also ist meine Aufgabe jetzt den kleinsten dieser Teiler zu finden für den gerade noch die Kongruenz zu 1 mod 358 gilt. Nur wie finde ich diese Menge heraus. Jene Menge müsste isch auch komplett durchtesten. Gibts da keine günstigeren Ansätze?
|
|
|
| |
|
Hallo,
lies doch nochmal alles. Ich verstehe nicht, wo jetzt noch ein Problem liegt.
> [...] Jene Menge müsste isch auch komplett durchtesten.
> Gibts da keine günstigeren Ansätze?
Es gibt jetzt für jedes m noch genau einen Test durchzuführen. Geht es überhaupt noch günstiger?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:17 So 15.07.2012 | | Autor: | Manu87 |
Ich vertseh wie du meinst. Klar in dem Fall ist es günstig. Aber das auch nur weil die Aufgabe so nett gestellt ist. Wenn da jetzt 15 Teiler wären, wüsste ich nicht ob ich die alle herausfinden würde.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:23 So 15.07.2012 | | Autor: | reverend |
Hi,
> Ich vertseh wie du meinst. Klar in dem Fall ist es
> günstig. Aber das auch nur weil die Aufgabe so nett
> gestellt ist. Wenn da jetzt 15 Teiler wären, wüsste ich
> nicht ob ich die alle herausfinden würde.
Ah, ok. Das stimmt natürlich.
Bei einer Klausuraufgabe musst Du das nicht fürchten, da geht es ja darum, ob Du das Prinzip verstanden hast.
In der Realität passiert allerdings immer genau das, was Du da befürchtest. Manchmal gibt es noch ein paar mehr Möglichkeiten, die Auswahl einzuengen, aber meistens nicht.
Hattet Ihr übrigens schon quadratische Reste? Wenn nein, dann hilft Dir das folgende nicht weiter. Lies es dann nochmal, wenn Ihr das Thema behandelt habt.
Bei der vorliegenden Aufgabe entspricht die Untersuchung gerade der Frage, ob m ein quadratischer Rest [mm] \mod{\blue{179}} [/mm] ist. Das wäre für m=17 leicht zu beantworten, wenn man bemerkt, dass [mm] 14^2\equiv 17\mod{179} [/mm] ist. Damit ist klar, dass 17 ein quadr.Rest ist. Damit kann man sich das dann vergleichsweise doch aufwändigere Potenzieren mit 89 ersparen. Aber m=17 war hier leider gar nicht gefragt...
Grüße
reverend
|
|
|
|
