Kongruenzrechnung 47|(2^23)-1

Neue Frage »

Banina Auf diesen Beitrag antworten »
Kongruenzrechnung 47|(2^23)-1
Meine Frage:
Beweisen Sie mittels Kongruenzrechnung: 47|(2^23)-1.

Meine Ideen:
Also ich habe meinenBeweis eben ganz stolz aufgeschrieben smile
doch dann habe ich irgendwas darüber gelesen, dass man den beweis anders durchführen muss, falls a-b (von m|a-b) keine primzahl ist. unglücklich
jetzt würde ich gern wissen, ob mein Beweis falsch ist.. :/ und wenn ja, dann bräuchte ich Hilfe und jemanden, der mich erklären kann, was ich anders machen muss! DANKESCHÖN schonmal!!

Hier mein Beweis:

z.z 47|(2^23)-1; d.h. z.z. 2^23-1 \equiv 0 mod 47.
Man bemerkt 2 \equiv 1 mod 47. Es folgt (mit Teil 4 unseres Korollars):
2^23 \equiv 1^23 mod 47. Also
2^23 \equiv 1 mod 47, d.h.

47|(2^23)-1.

liebe grüße,

Banina smile
galoisseinbruder Auf diesen Beitrag antworten »

Zitat:
Man bemerkt .


das ist falsch.
René Gruber Auf diesen Beitrag antworten »

Benutze sowie den kleinen Fermat.
Banina Auf diesen Beitrag antworten »

@ René Gruber: Das verstehe ich leider nicht traurig


Zitat:
Original von galoisseinbruder
Zitat:
Man bemerkt .


das ist falsch.


was ist denn an der stelle falsch?

ist es dann: 2\equiv -1mod 47 ?

DANKE!!! Wink
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von Banina
was ist denn an der stelle falsch?

Anders gefragt: Was soll denn daran richtig sein? Es ist doch absurd zu glauben, dass bei Division durch 47 die beiden Reste 1 und 2 einander identisch sind. geschockt

Ein derartiger Glaube lässt auf ein desaströses Unverständnis des gesamten Modulo-Begriffes schließen. Du solltest also dringend nochmal bei den Grundlagen der Modulrechnung anfangen.

Zitat:
Original von Banina
Das verstehe ich leider nicht

Nach dem eben gesagten kann ich nicht sagen, dass mich das noch wurndert.
Banina Auf diesen Beitrag antworten »

ich frage mich, warum du in diesem forum angemeldet bist, wenn du nicht helfen und erklären, sondern lediglich demotivierende kommentare beitragen möchtest.


Tanzen
 
 
René Gruber Auf diesen Beitrag antworten »

Weil du hier eine Aufgabe angehen willst mit Null Wissen über die Modulorechnung. Also mach dich das erstmal schlau, und dann kannst du das wieder hier angehen.
galoisseinbruder Auf diesen Beitrag antworten »

@Banina:
Dann sei froh dass oben René Gruber und nicht ich geantwortet hat- dann wärst du noch demotivierter. ich kann ihm nur vollumfänglich zustimmen.
Man kann nur denen helfen, die auch bereit dazu sind Hilfe anzunehmem.

Und ja: Die Wahrheit ist manchmal demotivierend.
banani Auf diesen Beitrag antworten »

Aha. Ich bin also in diesem FRAGEFORUM falsch, weil ich eine FRAGE stelle. Und werde nun weggeschickt, um die Antwort auf meine Frage selbst zu suchen (,weil ich mich angeblich noch ÜBERHAUPT GAR NICHT damit beschäftigt habe verwirrt ). Man, man, man. Big Laugh Big Laugh Big Laugh

Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink Wink
René Gruber Auf diesen Beitrag antworten »

Du bist nicht der erste und sicher auch nicht der letzte, der hier rumjammert, ach wie schlecht er doch hier behandelt wird. Die Grundlagen der Modulrechnung anschauen, dann noch den Satz von Fermat, und schon könntest du die obige Komplettlösung verstehen. Aber du spammst ja lieber hier mit Smilies rum - na dann Tschüss.
HannaSG Auf diesen Beitrag antworten »

Hallo,

ich habe auch einen Ansatz und komme nicht so richtig weiter.
Meine Idee:

47=48-1=2^{4}*3-1 d.h. 3*2^{4}-1=47
Somit gilt:
3*2^{4}-1\equiv 0 mod 47 also 3*2^{4} \equiv 1 mod 47

man kann nun mit 5 potenzieren: 3^{5}*2^{20} \equiv 1 mod 47

kann man das so machen? und wie kann man jetzt weiter vorgehen?
normaler weise würde ich jetzt 3^{5} zerlegen:
3^{5}=243=47-196=47* ???

habe ich ich schon vorher irgendwo vertan?

Lg Hanna
galoisseinbruder Auf diesen Beitrag antworten »

Hallo HannaSG,

dein Ansatz ist zwar sehr weit vom Standardansatz entfernt, aber offensichtlich in diesem Fall kreativ genug zu funktionieren:


Ist richtig, wenn du jetzt noch ausrechnest ... stehts da.

Im allgemeinen ist bei solchen Aufgaben, wie bereits erwähnt, der kleiner Fermat hilfreich.
HannaSG Auf diesen Beitrag antworten »

Danke smile

ich habe dann 8\equiv 3^{5} mod 47
also 2^{3} \equiv 3^{5} mod 47

kann ich dann daraus schlussfolgern, dass 2^{3} * 2^{20} \equiv 1 mod 47
und damit dann 2^{23} \equiv 1 mod 47 gilt?

dann kann man schreiben 2^{23}-1 \equiv 0 mod 47 \Rightarrow 47 l 2^{23}-1

ist das so korrekt?

nur interessehalber...wie kann man denn den kleinen Fermat anwenden? der ggT ist doch nicht 1 und das ist doch vorraussetzung für den satz. oder habe ich das falsch verstanden?

Danke für die Hilfe!

Lg
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von HannaSG
ist das so korrekt?

Ja, ist korrekt.

Zitat:
Original von HannaSG
der ggT ist doch nicht 1 und das ist doch vorraussetzung für den satz.

Von welchem ggT sprichst du? Es ist ggT(2,47)=1 bzw. (siehe oben) auch ggT(7,47)=1, also sind die Voraussetzungen durchaus erfüllt.
Matt tee Auf diesen Beitrag antworten »

Hallo ich dachte ich greife die Inhalte mal auf,

habe mich mal an der Aufgabe versucht, verstehe aber nicht wie man den kleinen Satz von Fermat hier sinnvoll anwenden kann.

Also ich komme damit dann auf



das mit der 2^46 also (2^23)^2 sieht mir ja schon ziemlich gut aus, aber leider komme ich mit den mir zur Verfügung stehenden Formeln/Rechenregeln nicht weiter, jedenfalls sehe ich nicht wie ich das jetzt wieder runterbrechen kann...

Wäre schön, wenn Ihr dazu noch nen Rat hättet.

Vielen Dank
René Gruber Auf diesen Beitrag antworten »

Eben das ist das Problem: Aus kann man über



erstmal nur folgern, dass oder aber gilt.


Oben habe ich die Sache dadurch gelöst, dass ich direkt nachgewiesen habe, dass 2 ein quadratischer Rest modulo 47 ist, und zwar gemäß

,

und habe dann den kleinen Fermat auf Basis 7 statt Basis 2 angewandt.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »