www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenZahlentheorieTeilbarkeit
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Zahlentheorie" - Teilbarkeit
Teilbarkeit < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Teilbarkeit: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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 []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?

        
Bezug
Teilbarkeit: Antwort
Status: (Antwort) fertig Status 
Datum: 02:29 So 15.07.2012
Autor: reverend

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


Bezug
                
Bezug
Teilbarkeit: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                        
Bezug
Teilbarkeit: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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]

Bezug
                                
Bezug
Teilbarkeit: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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... :-/

Bezug
                                        
Bezug
Teilbarkeit: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                        
Bezug
Teilbarkeit: Antwort
Status: (Antwort) fertig Status 
Datum: 13:28 So 15.07.2012
Autor: reverend

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


Bezug
                                
Bezug
Teilbarkeit: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                                        
Bezug
Teilbarkeit: Antwort
Status: (Antwort) fertig Status 
Datum: 15:43 So 15.07.2012
Autor: reverend

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


Bezug
                                                
Bezug
Teilbarkeit: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                                                        
Bezug
Teilbarkeit: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]