| Autor |
Beitrag |
    
Tiffany (T_L)
| | Veröffentlicht am Sonntag, den 13. Januar, 2002 - 21:14: | 
|
Hallo,
Wie löst man möglichst schnell folgendes Problem:
Weisen Sie nach, daß 33053 ein Teiler der Zahl 19 · 2766522 + 3 ist.
Ich hab' überhaupt keinen Plan. Könnt ihr mir helfen?
Tiffany |
Kay Schönberger (Kay_S)
| | Veröffentlicht am Mittwoch, den 16. Januar, 2002 - 19:22: |
|
Hallo Tiffany,
Ich kann dir vorerst nur eine Teillösung anbieten.
Bezeichne im folgenden n = 33053.
Der Ansatz besteht darin, erst einmal eine geeignete Kongruenzgleichung mod n zu finden, in der sinnigerweise eine 2er-Potenz auftritt, so z. B.
2irgendwas º z (mod n), wobei z idealerweise 1 oder -1 ist.
Das kriegt man so schön natürlich nicht hin, z sollte dann wenigstens möglichst klein sein bzw. möglichst wenige und kleine Primfaktoren besitzen.
Im vorgelegten Fall ist n = 215 + 3 * 5 * 19, d.h. es gilt
(I) 215 = - 3 * 5 * 19 (mod n)
Nun versucht man die Primteiler in z ganz zu eliminieren bzw. wenigstens zu verkleinern. Sehr unangenehm ist hier natürlich die 19.
Mit etwas Glück fand ich die Beziehung 711 º 195 (mod n), wie man noch mit einem Taschenrechner nachweisen kann. Um nun 19 zu ersetzen, müssen wir (I) mit 5 potenzieren (Kongruenzgesetze). Wir erhalten:
(II) 275 º - 35 * 55 * 195 (mod n)
Wegen 711 º 195 (mod n) kann man nun 195 substituieren:
(III) 275 º - 35 * 55 * 711 (mod n)
Tip: Versuche, 3, 5 und 7 jeweils auf die selbe Art durch 2 zu ersetzen. Wenn ich den gesamten Lösungsweg habe, stelle ich ihn ins Board.
Kay S. |
|
