Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

41|17^1000-1 ?
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> 41|17^1000-1 ?
 
Autor Nachricht
mir_fällt_nix_ein
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 26.05.2005
Beiträge: 12

BeitragVerfasst am: 26 Mai 2005 - 16:59:45    Titel: 41|17^1000-1 ?

Hallo, ich komm da bei ner Aufgabe nicht weiter.
Die Aufgabe lautet;
Zeigen Sie

a) 41|17^1000-1
b) 4147|12^512-1
c)91|3^91-3
d)15|a^15-4
e)7|2^(3n)-1
f)42|n^7-n

Ich hoffe Jemand kann mir einen Tipp geben
danke
Faulus
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 82

BeitragVerfasst am: 27 Mai 2005 - 13:55:56    Titel:

zu a)

Beh: 17^1000-1 mod 41 = 0

Bew: 17^1000 - 1 mod 41 = 17^(1000 mod phi(41)) - 1 mod 41
= 17^(1000 mod 40) - 1 = 17^0-1 = 1 - 1 = 0

0 / 42 = 0 (stimmt also)

zu c)

Beh: 3^91-3 mod 91 = 0

geht genauso wie a)

3^91 - 3 mod 91 = 3^(91mod phi(91)) = 3^1 - 3 mod 91 = 0

zu d) a^15 - 4 mod 15 = 0

da phi(15) = 8 folgt, dass a^15-4 mod 15 = a^7 - 4 mod 15

ach ja lol :D 1^15-4 mod 15 != 0 (ungleich)
also stimmts ja schomma net

oder soll man hier ein a ausrechnen??


zu e)
hier muss man sehen: 2^(3n) ist immer ein vielfaches voon acht, da 2^3 = 8
also 2^(3n) = 8^n

und 8^n - 1 mod 7 = (8 mod 7)^n - 1 mod 7 = 1^n - 1 mod 7 = 0 mod 7 = 0
stimmt auch

zu b und f überleg ich mir noch was .p


cu...
Faulus
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 82

BeitragVerfasst am: 27 Mai 2005 - 14:04:12    Titel:

also zu f)

die aussage stimmt auch nciht, da z.B. 4^7-4 mod 42 = 21 und nicht 0

b) stimmt, aber ich weiss echt nicht wie man das zeigen soll, ausser rechnen.

einfach exponenten in binärer schreibweise schrieben,
square and multiply algorithmus anwenden (google)
und man kann schnell die moduloexponentiation ausrechnen
mitm taschenrechner .p


cu..
Faulus
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 82

BeitragVerfasst am: 27 Mai 2005 - 14:06:24    Titel:

nomma zu b) :D

man kann uch zeigen dass 12^4 - 1 mod 4147 = 0 ist; da ist ja leicht
zu errechnen .p

und 12^512 ist ja nur ein vielfaches davon , also 12^512-1 mod 4147 = 0


so jetz ham wirs aber ....
Hiob
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 04.05.2005
Beiträge: 1379

BeitragVerfasst am: 27 Mai 2005 - 14:22:11    Titel: Re: 41|17^1000-1 ?

Ich hab sowas noch nicht gerechnet, eweshalb ich noch nicht weiß, wie man solche Aufgaben elegant löst. Ich verlasse mich beim Rechnen einfach auf die hier gefundenen Rechenregeln.

a) 41|17^1000-1
17^1000-1 mod 41
= 17^(2*500) mod 41 - (1 mod 41)
= 289^500 mod 41 - (1 mod 41)
= 2^500 mod 41 - (1 mod 41)
= 2^(10*50) mod 41 - (1 mod 41)
= 1024^50 mod 41 - (1 mod 41)
= (-1)^50 mod 41 - (1 mod 41)
= 1 mod 41 - (1 mod 41)
= 0
Also ist 41 Teiler von 17^1000-1.

b) 4147|12^512-1
12^512-1 mod 4147
= 12^512 mod 4147 - (1 mod 4147)
= 12^(4*128) mod 4147 - (1 mod 4147)
= 20736^128 mod 4147 - (1 mod 4147)
= 1^128 mod 4147 - (1 mod 4147)
= 1 mod 4147 - (1 mod 4147)
= 0
Also ist 4147 Teiler 12^512-1.

c)91|3^91-3
3^91-3 mod 91
= 3^91 mod 91 - (3 mod 91)
= 3^(7*13) mod 91 - (3 mod 91)
= 2187^13 mod 91 - (3 mod 91)
= 3^13 mod 91 - (3 mod 91)
= 1594323 mod 91 - (3 mod 91)
= 3 mod 91 - (3 mod 91)
= 0
Also ist 91 Teiler von 3^91-3.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> 41|17^1000-1 ?
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum