Teilbarkeit < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Ist [mm] 2^{20}-1 [/mm] durch 41 teilbar? |
Hallo,
ich brauche dringend Hilfe bei obiger Aufgabe bzw. muss ich allgemein lernen wie man solche Aufgaben löst.
Mein einziger (und mit Sicherheit falscher) Ansatz bisher ist:
[mm] 2^{20} \equiv [/mm] 1 mod 41
Und dann hab ich versucht die Potenzen von [mm] 2^{20} [/mm] etwas aufzulösen bis ich auf eine Zahl stoße die zeigt, dass [mm] 2^{20} \equiv [/mm] 1 mod 41 gilt. Hat aber nicht funktioniert, da:
[mm] (2^2)^{10} [/mm] = [mm] 4^{10} [/mm] = [mm] (4^2)^5 [/mm] = [mm] 16^5 [/mm] .... Bringt mir ja nichts und wieder nichts...
Danke schon mal!
LG
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:46 Fr 04.02.2011 | | Autor: | abakus |
> Ist [mm]2^{20}-1[/mm] durch 41 teilbar?
> Hallo,
>
> ich brauche dringend Hilfe bei obiger Aufgabe bzw. muss ich
> allgemein lernen wie man solche Aufgaben löst.
> Mein einziger (und mit Sicherheit falscher) Ansatz bisher
> ist:
> [mm]2^{20} \equiv[/mm] 1 mod 41
>
> Und dann hab ich versucht die Potenzen von [mm]2^{20}[/mm] etwas
> aufzulösen bis ich auf eine Zahl stoße die zeigt, dass
> [mm]2^{20} \equiv[/mm] 1 mod 41 gilt. Hat aber nicht funktioniert,
> da:
> [mm](2^2)^{10}[/mm] = [mm]4^{10}[/mm] = [mm](4^2)^5[/mm] = [mm]16^5[/mm] .... Bringt mir ja
> nichts und wieder nichts...
>
> Danke schon mal!
> LG
Hallo,
nach dem kleinen Satz von Fermat ist [mm] 2^{40}\equiv [/mm] 1 mod 41.
Also gilt [mm] (2^{20})^2\equiv [/mm] 1 mod 41.
Daraus muss nun nicht zwangsläufig folgen, dass [mm] 2^{20} \equiv [/mm] 1 mod 41, denn auch aus (mal angenommen) [mm] 2^{20}\equiv [/mm] -1 mod 41 würde [mm] 2^{40} \equiv [/mm] 1 mod 41 folgen.
Fakt ist aber: wenn [mm] 2^n [/mm] irgendwann den Rest 1 mod 41 lässt, dann lässt auch [mm] 2^{2n}, 2^{3n} [/mm] usw. den Rest 1.
Hier kannst du dich aber bequem rantasten.
[mm] 2^5=32, [/mm] und 32 [mm] \equiv [/mm] -9 mod 41.
Daraus folgt [mm] 2^{10} \equiv (-9)^2 \equiv [/mm] 81 [mm] \equiv [/mm] -1 mod 82.
Damit gilt [mm] 2^{20} \equiv (-1)^2 \equiv [/mm] 1 mod 42.
Gruß Abakus
|
|
|
| |
|
Ja, das kann ich nachvollziehen. Allerdings wäre ich da niemals selbst drauf gekommen....
Gibt es bei solchen Aufgaben irgendwie eine Stratgie nach der man erstmal vorgehen kann? Ich sehe diese Kongruenzen nie sofort...
LG
So, dann hab ich noch eine Aufgabe:
Zeige, dass 504 für n [mm] \in \IN [/mm] ein Teiler von [mm] (n^3-1)n^3(n^3+1) [/mm] (= P(n)) ist.
Da habe ich 504 in die entsprechenden Primfaktoren zerlegt:
504= [mm] 2^3*3^2*7
[/mm]
Das heißt, es ist zu zeigen: [mm] 2^3 [/mm] |P(n) und [mm] 3^2 [/mm] | P(n) und 7 | P(n)
Und da stehe ich wieder und weiß nicht wo ich anfangen soll....
Sorry!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:26 Fr 04.02.2011 | | Autor: | abakus |
> Ja, das kann ich nachvollziehen. Allerdings wäre ich da
> niemals selbst drauf gekommen....
> Gibt es bei solchen Aufgaben irgendwie eine Stratgie nach
> der man erstmal vorgehen kann? Ich sehe diese Kongruenzen
> nie sofort...
>
> LG
>
> So, dann hab ich noch eine Aufgabe:
>
> Zeige, dass 504 für n [mm]\in \IN[/mm] ein Teiler von
> [mm](n^3-1)n^3(n^3+1)[/mm] (= P(n)) ist.
>
> Da habe ich 504 in die entsprechenden Primfaktoren
> zerlegt:
> 504= [mm]2^3*3^2*7[/mm]
> Das heißt, es ist zu zeigen: [mm]2^3[/mm] |P(n) und [mm]3^2[/mm] | P(n) und
> 7 | P(n)
> Und da stehe ich wieder und weiß nicht wo ich anfangen
> soll....
>
> Sorry!
Hallo,
für gerade n ist [mm] n^3 [/mm] durch 8 teilbar. Für ungerade n sind sowohl [mm] n^3-1 [/mm] als auch [mm] n^3+1 [/mm] gerade, und jede zweite gerade Zahl (also [mm] n^2-1 [/mm] ODER [mm] n^2+1) [/mm] ist sogar durch 4 teilbat.
Für die Teilung durch 7 bzw 9 mache jeweils eine Fallunterscheidung.
n kann mod 9 die Reste -4 bis +4 lassen (man hätte auch 0 bis 8 sagen können, aber schließlich müssen daraus noch 3. Potenzen gebildet werden, das ist bei großen Zahlen unangenehm).
Die 3. Potenzen von -4 bis 4 lassen mod 9 die Reste
-1, 0, 1, -1,0,1,-1,0 bzw 1. Beim Rest 0 ist [mm] n^3 [/mm] selbst durch 9 teilbar, beim Rest -1 ist [mm] n^3+1 [/mm] durch 9 teilbar und beim Rest +1 ist [mm] n^3-1 [/mm] durch 9 teilbar.
Untersuche nun die möglichen Reste von [mm] n^3 [/mm] mod 7 und ziehe Schlussfolgerungen.
Gruß Abakus
|
|
|
|
