ggT ermitteln < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
| |
|
> Bestimme den Wert des folgenden Ausdrucks mit Angabe des
> Lösungswegs:
> [mm]ggT(\,2^{445}+7\,,\,15\,)[/mm]
> Hallo 
>
> Leider sitze ich jetzt schon eine Ewigkeit an dieser
> Aufgabe und ich brauche irgendwie einen kleinen "Schupser"
> in die richtige Richtung..
>
> Ich habe bis jetzt..
>
> [mm]ggT(2^{445}+7,15)=ggT(2^{445}+7-15,15)=ggT(2^{445}-2^{3},15)[/mm]
> Als ggT käme in Betracht [mm]max\{1,3,5,15\}.[/mm]
>
> Ja und nach mehreren Stunden rumprobieren ist irgendwie
> nicht mehr herausgekommen... :-D
> Würde mich freuen, wenn jemand einen Tipp hat...
>
> LG,
> Topologe
Hallo Topologe
(das ist doch ein Naturforscher auf dem Spezial-
gebiet der Mäuse und ![[]](/images/popup.gif) Maulwürfe , oder ?) 
eigentlich musst du doch hier nur die Teilbarkeit
der Zahl [mm] n:=2^{445}+7 [/mm] durch 3 und durch 5 unter-
suchen !
Ein Hinweis, der nützlich sein könnte: wenn du
die Reste der Zweierpotenzen [mm] 2^0, 2^1, 2^2, 2^3, 2^4, [/mm] .....
modulo 3 (oder auch modulo 5) betrachtest, so
erhältst du jeweils eine periodische Zahlenfolge.
LG , Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:18 Fr 25.10.2013 | | Autor: | Topologe |
Hi, danke für den Tipp
Als ggT käme in Betracht: 1,3,5,15.
Untersuchung Teilbarkeit durch 5:
[mm] 2^{0} [/mm] + 7 mod 5 = 3
[mm] 2^{1} [/mm] + 7 mod 5 = 4
[mm] 2^{2} [/mm] + 7 mod 5 = 1
[mm] 2^{3} [/mm] + 7 mod 5 = 0
[mm] 2^{4} [/mm] + 7 mod 5 = 3
[mm] 2^{5} [/mm] + 7 mod 5 = 4
[mm] 2^{6} [/mm] + 7 mod 5 = 1
[mm] 2^{7} [/mm] + 7 mod 5 = 0
[mm] \vdots
[/mm]
[mm] \Rightarrow [/mm] Teilbarkeit durch 5 bei [mm] 2^{4k-1}+7, [/mm] k [mm] \in \IN.
[/mm]
Also [mm] 2^{443}+7 [/mm] mod 5 = 0
[mm] 2^{444}+7 [/mm] mod 5 = 3
[mm] 2^{445}+7 [/mm] mod 5 = 4 [mm] \Rightarrow [/mm] 5 kein Teiler von [mm] 2^{455}+7
[/mm]
Teilbarkeit durch 15:
Ausgeschlossen, da eine Zahl, die durch 15 teilbar ist, auch durch 3 und 5 teilbar sein muss.
Teilbarkeit durch 3:
[mm] 2^{0}+7 [/mm] mod 3 = 2
[mm] 2^{1}+7 [/mm] mod 3 = 0
[mm] 2^{2}+7 [/mm] mod 3 = 2
[mm] 2^{3}+7 [/mm] mod 3 = 0
[mm] 2^{4}+7 [/mm] mod 3 = 2
[mm] \vdots
[/mm]
[mm] \Rightarrow [/mm] Teilbarkeit durch 3 bei [mm] 2^{2k-1}+7, [/mm] k [mm] \in \IN.
[/mm]
Also [mm] 3|2^{445}+7 [/mm] und 3|15 und da 5 und 15 keine gemeinsamen Teiler sind, folgt [mm] ggT(2^{445}+7,15)=3
[/mm]
LG,
Topologe
|
|
|
| |
|
Hallo Topologe,
ja, so stimmts - sowohl der Weg als auch die Lösung.
Etwas abkürzen kann man noch, wenn man [mm] 2^4\equiv 1\mod{5} [/mm] und $445=4*111+1$ sowie [mm] 2^2\equiv 1\mod{3} [/mm] und $445=2*222+1$ mit einbezieht. Beide Äquivalenzen folgen aus dem kleinen Fermat.
Grüße
reverend
|
|
|
|
