47 als Teiler

02/11/2007 - 11:04 von Schnitzspan | Report spam
Hallo,

47 = (2 hoch 7) - (3 hoch 4)
sollen wir ausnutzen um zu zeigen, dass 47 ein Teiler ist von ((2 hoch
23) -1)

steht in der Aufgabe. Ich weiss nicht wie.

Dran in der Vorlesung war gerade euklidischer Algorithmus, auch der
erweiterte und
der Chinesische Restesatz. Geht das damit? Oder mit was anderem? Habt
Ihr einen Tip?


Helmut
 

Lesen sie die antworten

#1 Ulysse from CH
02/11/2007 - 13:49 | Warnen spam
On Fri, 02 Nov 2007 03:04:18 -0700, Schnitzspan
wrote:

47 = (2 hoch 7) - (3 hoch 4)
sollen wir ausnutzen um zu zeigen, dass 47 ein Teiler ist von ((2 hoch
23) -1)
steht in der Aufgabe. Ich weiss nicht wie. (...)



Eine Möglichkeit, die ich gefunden habe, geht so.

Da für ganze Zahlen a,b (a-b) Teiler von (a^3 - b^3) ist (^ steht
bekanntlich für das "hoch" der Exponentiation) ... [siehst du warum ?]
hat man: 2^7-3^4 ist ein Teiler von 2^21-3^12 [denn (a^b)^c=a^(b*c)
wo * wie üblich die Multiplikation darstellt] also auch von 4 mal
diese Differenz, d.h. von 2^23 - 4*(3^12). Damit 47 auch ein Teiler
von 2^23 - 1 ist, brauche ich nur noch, dass 47 ein Teiler von
4*(3^12) - 1 ist. Da dies 2*(3^6) - 1 mal 2*(3^6) + 1 ist, muss ich
zeigen, dass 47 Teiler einer dieser Faktoren ist. Diese Zahlen sind
schon recht klein, so dass es durchaus im Sinne der gestellten
Aufgabe sein kann, dies durch direkte Rechnung festzustellen:
es geht um 1457 und 1459, wovon man leicht sieht, dass die erste
ein Vielfaches von 47 ist.

Das ganze Argument làsst sich noch schöner mit "modulo"
darstellen, wobei man dann beim Rechnen nur noch mit
2-stelligen Zahlen hantieren muss, indem man sich damit begnügt,
dass 3^6 modulo 47 kongruent 24 ist, und 24*2H kongruent 1 !

Vielleicht gibt's was Eleganteres. Wenn man die "zweite Zusatzformel"
zum sog. "quadratischen Reziprozitàtsgesetz" kennt und benützen
darf, geht's noch einfacher und fast ohne Rechnung (auch ohne
die Gleichung 47 = 2^7 - 3^4 zu bemühen) aber so weit bist du
wohl noch eine Weile nicht. Es sollte aber schon kommen, wenn
du in einem Zahlentheorie-Kurs bist.

Ähnliche fragen