Division mit Rest < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:07 Fr 14.01.2011 | | Autor: | Bodo0686 |
| Aufgabe | | Welchen Rest läßt 3^99 bei Division durch 101 |
Hallo Zusammen,
ich hänge ein wenig.
Aber zu meinem Lösungsvorschlag.
Lösung mittels Fermat
[mm] n^{p-1}\equiv [/mm] 1(mod p)
Zerlege den Exponenten:
99=k*100+r -> k=1 und r = (-1)
-> [mm] 3^{1(101+(-1))}\equiv [/mm] 3^(-1) mod 101 [mm] \gdw (3^{101+(-1)})^1\equiv [/mm] 3^(-1) mod 101 [mm] \gdw 3^{100}\equiv 3^1
[/mm]
Nun muss ich mir doch den Rest von [mm] 3^1 [/mm] mod 101 angucken, oder?
Bitte um Hilfe! Danke!
|
|
| |
|
> Welchen Rest läßt 3^99 bei Division durch 101
> Hallo Zusammen,
>
> ich hänge ein wenig.
> Aber zu meinem Lösungsvorschlag.
>
> Lösung mittels Fermat
> [mm]n^{p-1}\equiv[/mm] 1(mod p)
Hallo,
übertragen auf Deine Aufgabe:
101 ist eine Primzahl,
also ist [mm] 3^{100}\equiv [/mm] 1 (mod 101).
>
> Zerlege den Exponenten:
> 99=k*100+r -> k=1 und r = (-1)
Soweit folge ich gut: 99=1*100+(-1).
>
> -> [mm]3^{1(101+(-1))}\equiv[/mm] 3^(-1) mod 101
Wieso?
Es ist doch, wie Du oben selbst schreibst, nach dem kl. Fermat [mm] 3^{100}=3^{(101+(-1)}\equiv [/mm] 1 (mod 101).
Es ist nicht [mm] 3^{101}\equiv [/mm] 1 (mod 101).
(Wozu das kongruent ist, kannst Du Dir mal überlegen.)
>
> Nun muss ich mir doch den Rest von [mm]3^1[/mm] mod 101 angucken,
> oder?
Das wäre kein echtes Problem: wenn ich 3 durch 101 teile, dann behalte ich den Rest 3.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:34 Fr 14.01.2011 | | Autor: | Bodo0686 |
> > Welchen Rest läßt 3^99 bei Division durch 101
> > Hallo Zusammen,
> >
> > ich hänge ein wenig.
> > Aber zu meinem Lösungsvorschlag.
> >
> > Lösung mittels Fermat
> > [mm]n^{p-1}\equiv[/mm] 1(mod p)
>
> Hallo,
>
> übertragen auf Deine Aufgabe:
>
> 101 ist eine Primzahl,
>
> also ist [mm]3^{100}\equiv[/mm] 1 (mod 101).
>
> >
> > Zerlege den Exponenten:
> > 99=k*100+r -> k=1 und r = (-1)
>
> Soweit folge ich gut: 99=1*100+(-1).
>
> >
> > -> [mm]3^{1(101+(-1))}\equiv[/mm] 3^(-1) mod 101
>
> Wieso?
Hängt denn nicht gerade 3^(-1) hier im speziellen die -1 mit dem Rest zusammen den ich bei der Zerlegung des Exponenten erhalten habe?
>
> Es ist doch, wie Du oben selbst schreibst, nach dem kl.
> Fermat [mm]3^{100}=3^{(101+(-1)}\equiv[/mm] 1 (mod 101).
>
> Es ist nicht [mm]3^{101}\equiv[/mm] 1 (mod 101).
> (Wozu das kongruent ist, kannst Du Dir mal überlegen.)
Aber ich habe doch nirgendwo [mm] 3^{101} [/mm] ... stehen? Oder übersehe ich etwas?
>
>
> >
> > Nun muss ich mir doch den Rest von [mm]3^1[/mm] mod 101 angucken,
> > oder?
>
> Das wäre kein echtes Problem: wenn ich 3 durch 101 teile,
> dann behalte ich den Rest 3.
Ok, das ist klar!
>
> Gruß v. Angela
>
Grüße
|
|
|
| |
|
> > > Welchen Rest läßt 3^99 bei Division durch 101
> > > Hallo Zusammen,
> > >
> > > ich hänge ein wenig.
> > > Aber zu meinem Lösungsvorschlag.
> > >
> > > Lösung mittels Fermat
> > > [mm]n^{p-1}\equiv[/mm] 1(mod p)
> >
> > Hallo,
> >
> > übertragen auf Deine Aufgabe:
> >
> > 101 ist eine Primzahl,
> >
> > also ist [mm]3^{100}\equiv[/mm] 1 (mod 101).
> >
> > >
> > > Zerlege den Exponenten:
> > > 99=k*100+r -> k=1 und r = (-1)
> >
> > Soweit folge ich gut: 99=1*100+(-1).
> >
> > >
> > > -> [mm]3^{1(101+(-1))}\equiv[/mm] 3^(-1) mod 101
> >
> > Wieso?
>
> Hängt denn nicht gerade 3^(-1) hier im speziellen die -1
> mit dem Rest zusammen den ich bei der Zerlegung des
> Exponenten erhalten habe?
Hallo,
wenn ich jetzt nicht gerade ein blackout habe, mochtest Du den Rest von [mm] 3^{99} [/mm] bei Division durch 101 wissen. Richtig?
Demnach, was Du eingangs schriebst, kennst Du den kl. Fermat.
Folglich weißt Du, daß [mm] 3^{100} [/mm] bei Division durch 101 den Rest 1 läßt.
Es ist doch [mm] 3^{99}=3^{100-1}=3^{100}*3^{-1}, [/mm] also ist [mm] 3^{99} [/mm] kongruent zu [mm] 3^{-1}, [/mm] wobei man nun darüber nachdenken müßte, was [mm] 3^{-1} [/mm] ist.
Du wurschtelst aber mit [mm] 3^{100}=3^{101-1} [/mm] rum und erzählst, daß das kongruent ist zu [mm] 3^{-1}, [/mm] obgleich der kl. Fermat etwas anderes sagt.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:15 Fr 14.01.2011 | | Autor: | Bodo0686 |
Ok,
ich schreibe es nochmal auf:
Lösung mittels Fermat:
[mm] n^{p-1}\equiv [/mm] 1 (mod p)
101 [mm] \in \IP
[/mm]
[mm] 3^{100}\equiv [/mm] mod 101
Zerlege den Exponenten nun in folgende Darstellung:
99=k*100+r
-> k=1 und r=(-1)
[mm] 3^{99} [/mm] = [mm] 3^{1(100+(-1))} \equiv 3^{-1} [/mm] mod 101
Nächster Schritt:
Betrachte nun den Rest [mm] 3^{-1} [/mm] bei Division durch 101.
Hätte man 3 mod 101 käme ja 3 heraus... Kann man [mm] 3^{-1} [/mm] nicht quasi als Inverses betrachten?
Grüße
|
|
|
| |
|
Hallo Bodo,
> Ok,
>
> ich schreibe es nochmal auf:
>
> Lösung mittels Fermat:
>
> [mm]n^{p-1}\equiv[/mm] 1 (mod p)
> 101 [mm]\in \IP[/mm]
>
> [mm]3^{100}\equiv[/mm] mod 101
>
> Zerlege den Exponenten nun in folgende Darstellung:
> 99=k*100+r
> -> k=1 und r=(-1)
>
> [mm]3^{99}[/mm] = [mm]3^{1(100+(-1))} \equiv 3^{-1}[/mm] mod 101
>
> Nächster Schritt:
>
> Betrachte nun den Rest [mm]3^{-1}[/mm] bei Division durch 101. ![[ok]](/images/smileys/ok.gif "[ok]")
>
> Hätte man 3 mod 101 käme ja 3 heraus... Kann man [mm]3^{-1}[/mm]
> nicht quasi als Inverses betrachten?
[mm]3^{-1}[/mm] ist das multiplikativ Inverse zu 3 (modulo 101)
dh. [mm]3\cdot{}3^{-1} \ \equiv \ 1 \ \ \operatorname{mod}(101)[/mm]
Bestimme also das zu 3 multiplikativ Inverse in [mm]\IZ_{101}[/mm]
Löse also [mm]3\cdot{}x \ \equiv \ 1 \ \ \operatorname{mod}(101)[/mm]
Wie das geht, weißt du?!
> Grüße
Gruß
schachuzipus
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:33 Fr 14.01.2011 | | Autor: | Bodo0686 |
Also d.h ja quasi, dass ich alle x aus [0,...,100] bestimmen muss für die sich modulo 101 ein Rest von 1 ergibt.
[mm] 3x\equiv [/mm] 1 mod 101
Alle x [mm] \le [/mm] 33 fallen ja eh schon weg da dort ja nur die bekannten Reste auftreten. x > 33 ist daher interessant.
34 wäre ja ein solches x und ich glaube auch das einzigste.
setze t=34 -> 34+t*101. Welche der Zahlen 34+t*101 liegt nun in der Zahlenmenge {0,...,100}? Für t=0 erhält man 34, t=1 erhält man 135, fällt aber raus!
Also ist 34 die einzigste Lösung.
Stimmt das so?
|
|
|
| |
|
> Also d.h ja quasi, dass ich alle x aus [0,...,100]
> bestimmen muss für die sich modulo 101 ein Rest von 1
> ergibt.
>
> [mm]3x\equiv[/mm] 1 mod 101
>
> Alle x [mm]\le[/mm] 33 fallen ja eh schon weg da dort ja nur die
> bekannten Reste auftreten. x > 33 ist daher interessant.
>
> 34 wäre ja ein solches x und ich glaube auch das
> einzigste.
Hallo,
ja.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:02 Fr 14.01.2011 | | Autor: | Bodo0686 |
Hallo,
also hätten wir nun:
[mm] 3^{99}=3^{(100+(-1))}\equiv 3^{-1} [/mm] mod 101
[mm] \gdw 3^{99}=3^{(100+(-1))}\equiv [/mm] 102 mod 101
Also ist der Rest 102?
Wie komme ich auf Rest [mm] 102?3x\equiv1mod101 [/mm] x=34 ist der gesuchte Wert
34*3=102
Grüße
|
|
|
| |
|
Hallo Bodo,
> also hätten wir nun:
>
> [mm]3^{99}=3^{(100+(-1))}\equiv 3^{-1}[/mm] mod 101
Ja, soweit wart Ihr hier schon in der Diskussion, sofern [mm] 3^{-1} [/mm] das multiplikativ Inverse zu 3 ist (s. Angelas Hinweis).
> [mm]\gdw 3^{99}=3^{(100+(-1))}\equiv[/mm] 102 mod 101
>
> Also ist der Rest 102?
Das ist Quatsch. Völliger.
In welche Restklasse gehört denn die 102 [mm] \mod{101}?
[/mm]
> Wie komme ich auf Rest [mm]102?3x\equiv1mod101[/mm] x=34 ist der
> gesuchte Wert
> 34*3=102
Das ist der gesuchte Wert. Wie hast Du ihn denn gefunden?
Alles außer Raten und Probieren dürfte einen erklärbaren Hintergrund haben.
Und zur Frage der Eindeutigkeit: da 101 eine Primzahl ist - was weißt Du über Ringe und/oder über Gruppen?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:04 Fr 14.01.2011 | | Autor: | Bodo0686 |
> Hallo Bodo,
>
> > also hätten wir nun:
> >
> > [mm]3^{99}=3^{(100+(-1))}\equiv 3^{-1}[/mm] mod 101
>
> Ja, soweit wart Ihr hier schon in der Diskussion, sofern
> [mm]3^{-1}[/mm] das multiplikativ Inverse zu 3 ist (s. Angelas
> Hinweis).
>
> > [mm]\gdw 3^{99}=3^{(100+(-1))}\equiv[/mm] 102 mod 101
> >
> > Also ist der Rest 102?
>
> Das ist Quatsch. Völliger.
> In welche Restklasse gehört denn die 102 [mm]\mod{101}?[/mm]
>
> > Wie komme ich auf Rest [mm]102?3x\equiv1mod101[/mm] x=34 ist der
> > gesuchte Wert
> > 34*3=102
>
> Das ist der gesuchte Wert. Wie hast Du ihn denn gefunden?
> Alles außer Raten und Probieren dürfte einen
> erklärbaren Hintergrund haben.
Ich habe die Kongruenz von [mm] 3x\equiv [/mm] 1 mod 101 berechnet.
ggT(3,101)=1 -> Damit kommt 1 Lösung in Frage. Man hat 34+t*101. Nun schaut man nach welche Zahlen in der Zahlenmenge {0,...,100} liegen. Und das ist ja nur die 34.
> Und zur Frage der Eindeutigkeit: da 101 eine Primzahl ist
> - was weißt Du über Ringe und/oder über Gruppen?
>
> Grüße
> reverend
>
Grüße
|
|
|
| |
|
Hallo nochmal,
Mist, habe einen falschen Knopf gedrückt - Antwort weg ...
Daher die Verzögerung ...
> > Hallo Bodo,
> >
> > > also hätten wir nun:
> > >
> > > [mm]3^{99}=3^{(100+(-1))}\equiv 3^{-1}[/mm] mod 101
> >
> > Ja, soweit wart Ihr hier schon in der Diskussion, sofern
> > [mm]3^{-1}[/mm] das multiplikativ Inverse zu 3 ist (s. Angelas
> > Hinweis).
> >
> > > [mm]\gdw 3^{99}=3^{(100+(-1))}\equiv[/mm] 102 mod 101
> > >
> > > Also ist der Rest 102?
> >
> > Das ist Quatsch. Völliger.
> > In welche Restklasse gehört denn die 102 [mm]\mod{101}?[/mm]
> >
> > > Wie komme ich auf Rest [mm]102?3x\equiv1mod101[/mm] x=34 ist der
> > > gesuchte Wert
> > > 34*3=102
> >
> > Das ist der gesuchte Wert. Wie hast Du ihn denn gefunden?
> > Alles außer Raten und Probieren dürfte einen
> > erklärbaren Hintergrund haben.
>
> Ich habe die Kongruenz von [mm]3x\equiv[/mm] 1 mod 101 berechnet.
> ggT(3,101)=1 -> Damit kommt 1 Lösung in Frage. ![[kopfkratz3]](/images/smileys/kopfkratz3.gif "[kopfkratz3]")
Was soll das heißen? Lösung für was??
Du musst den ggT, also 1, als ganzzahlige LK der beteiligten Zahlen 3 und 101 darstellen:
[mm]\operatorname{ggT}(3,101)=1=a\cdot{}3+b\cdot{}101[/mm] mit [mm]a,b\in\IZ[/mm]
[mm]a,b[/mm] kannst du durch Rückwärtseinsetzen und -rechnen aus der Berechnung des ggT mit dem Euklidischen Algorithmus berechnen.
Damit dann rein in die zu lösende Kongruenz [mm]3\cdot{}x \ \equiv \ \red{1} \ \ \operatorname{mod}(101)[/mm] und die [mm]\red{1}[/mm] entsprechend ersetzen.
> Man hat
> 34+t*101. Nun schaut man nach welche Zahlen in der
> Zahlenmenge {0,...,100} liegen. Und das ist ja nur die 34.
>
>
> > Und zur Frage der Eindeutigkeit: da 101 eine Primzahl ist
> > - was weißt Du über Ringe und/oder über Gruppen?
> >
> > Grüße
> > reverend
> >
>
> Grüße
LG
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:28 Fr 14.01.2011 | | Autor: | Bodo0686 |
> Hallo nochmal,
>
> Mist, habe einen falschen Knopf gedrückt - Antwort weg
> ...
>
> Daher die Verzögerung ...
>
> > > Hallo Bodo,
> > >
> > > > also hätten wir nun:
> > > >
> > > > [mm]3^{99}=3^{(100+(-1))}\equiv 3^{-1}[/mm] mod 101
> > >
> > > Ja, soweit wart Ihr hier schon in der Diskussion, sofern
> > > [mm]3^{-1}[/mm] das multiplikativ Inverse zu 3 ist (s. Angelas
> > > Hinweis).
> > >
> > > > [mm]\gdw 3^{99}=3^{(100+(-1))}\equiv[/mm] 102 mod 101
> > > >
> > > > Also ist der Rest 102?
> > >
> > > Das ist Quatsch. Völliger.
> > > In welche Restklasse gehört denn die 102 [mm]\mod{101}?[/mm]
> > >
> > > > Wie komme ich auf Rest [mm]102?3x\equiv1mod101[/mm] x=34 ist der
> > > > gesuchte Wert
> > > > 34*3=102
> > >
> > > Das ist der gesuchte Wert. Wie hast Du ihn denn gefunden?
> > > Alles außer Raten und Probieren dürfte einen
> > > erklärbaren Hintergrund haben.
> >
> > Ich habe die Kongruenz von [mm]3x\equiv[/mm] 1 mod 101 berechnet.
> > ggT(3,101)=1 -> Damit kommt 1 Lösung in Frage.
>
>
> Was soll das heißen? Lösung für was??
>
> Du musst den ggT, also 1, als ganzzahlige LK der
> beteiligten Zahlen 3 und 101 darstellen:
>
> [mm]\operatorname{ggT}(3,101)=1=a\cdot{}3+b\cdot{}101[/mm] mit
> [mm]a,b\in\IZ[/mm]
>
> [mm]a,b[/mm] kannst du durch Rückwärtseinsetzen und -rechnen aus
> der Berechnung des ggT mit dem Euklidischen Algorithmus
> berechnen.
>
> Damit dann rein in die zu lösende Kongruenz [mm]3\cdot{}x \ \equiv \ \red{1} \ \ \operatorname{mod}(101)[/mm]
> und die [mm]\red{1}[/mm] entsprechend ersetzen.
>
> > Man hat
> > 34+t*101. Nun schaut man nach welche Zahlen in der
> > Zahlenmenge {0,...,100} liegen. Und das ist ja nur die 34.
>
>
>
> >
> >
> > > Und zur Frage der Eindeutigkeit: da 101 eine Primzahl ist
> > > - was weißt Du über Ringe und/oder über Gruppen?
> > >
> > > Grüße
> > > reverend
> > >
> >
> > Grüße
>
> LG
>
> schachuzipus
>
Also hätte man nun:
[mm] 3^{99} \equiv [/mm] 34 mod 101 dort stehen?
Grüße
|
|
|
| |
|
Hallo nochmal,
zitiere doch bitte mit etwas mehr Bedacht, lösche Unnötiges weg!
> Also hätte man nun:
>
> [mm]3^{99} \equiv[/mm] 34 mod 101 dort stehen?
So sieht's aus!
>
> Grüße
LG
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:57 Fr 14.01.2011 | | Autor: | Bodo0686 |
Im Klartext ist die Aufgabe nun beendet und ich habe als Lösung den Rest 34 ermittelt, richtig?
|
|
|
| |
|
Hallo,
> Im Klartext ist die Aufgabe nun beendet und ich habe als
> Lösung den Rest 34 ermittelt, richtig?
Ja, es ist [mm]3^{99} \ \equiv \ 3^{-1} \ = \ 34 \ \equiv \ 34 \ \ \operatorname{mod}(101)[/mm]
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:09 Fr 14.01.2011 | | Autor: | reverend |
Hallo nochmal,
> Im Klartext ist die Aufgabe nun beendet und ich habe als
> Lösung den Rest 34 ermittelt, richtig?
Fertig warst Du schon vorher, nur hast Du noch nicht verraten, wie Du die 34 ermittelt hast. Auch das gehört zur Aufgabe.
Für die Uni solltest Du zumindest angeben, ob Du über hellseherische Fähigkeiten verfügst, den erweiterten euklidischen Algorithmus benutzt hast, sowieso nur im 101er-System rechnest, endeckt hast, dass 102 durch 3 teilbar ist - oder was auch immer.
Grüße
reverend
|
|
|
|
