Kongruenzen beweisen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Beweise:
i) [mm] n^{13}-n \equiv0(mod2730) [/mm] für alle [mm] n\in\IN
[/mm]
ii) [mm] 2^{2n+1}\equiv9n^{2}-3n+2(mod54) [/mm] für alle [mm] n\in\IN [/mm] |
Hallo!
Die Aufgaben zerbrechen mir den Kopf. Ich hab bei beiden natürlich Induktion gemacht, stecke aber beim Induktionsschritt fest:
zu i) bleibt zu zeigen:
[mm] (n+1)^{13}-(n+1)\equiv0(mod2730)
[/mm]
umgeformt:
[mm] (n+1)^{13}-(n+1)=n^{13}-n+\vektor{13 \\ 1}n^{12}+...+\vektor{13 \\12 }n [/mm] ; +1 und -1 haben sich aufgehoben
da [mm] n^{13}-n \equiv0(mod2730) [/mm] als richtig angenommen wurde bleibt noch
[mm] \vektor{13 \\ 1}n^{12}+...+\vektor{13 \\12 }n\equiv0(mod2730) [/mm] zu zeigen
und da hörts auf. Ich hab noch raugefunden, dass 2730=2*3*5*7*13 ist und könnte alles durch 13 teilen dann bliebe mir (mod210), aber ....
zu ii) bleibt zu zeigen:
[mm] 2^{2(n+1)+1}\equiv9(n+1)^{2}-3(n+1)+2(mod54)\gdw2^{2n+1+2}\equiv9n^{2}-3n+2+18n+9-3(mod54)
[/mm]
dann habe ich [mm] 9n^{2}-3n+2 [/mm] durch [mm] 2^{2n+1} [/mm] (IV) ersetzt: [mm] 2^{(2n+1)+2}\equiv2^{2n+1}+18n+6(mod54);
[/mm]
[mm] 2^{2n+1} [/mm] auf beiden Seiten abgezogen: [mm] 3*2^{2n+1}\equiv18n+6(mod54);
[/mm]
durch 6 gekürzt mit ggt(6,54)=6
und erhalte:
[mm] 2^{2n}\equiv3n-1(mod9) [/mm] und da hörts auch hier auf.
Dankbar wär ich für jeden Tipp, wie ich die Aufgaben zum Ende bringen könnte.
Gruß
Ich habe diese Frage in keinem anderen Forum gestellt.
|
|
| |
|
Hallo Vic_Burns,
Du gehst zu kompliziert daran:
> Beweise:
> i) [mm]n^{13}-n \equiv0(mod2730)[/mm] für alle [mm]n\in\IN[/mm]
> ii) [mm]2^{2n+1}\equiv9n^{2}-3n+2(mod54)[/mm] für alle [mm]n\in\IN[/mm]
> Hallo!
>
> Die Aufgaben zerbrechen mir den Kopf. Ich hab bei beiden
> natürlich Induktion gemacht,
Da fängts schon an...
In der Zahlentheorie ist Induktion eher selten ein geeignetes Verfahren, kommt aber natürlich vor.
> stecke aber beim
> Induktionsschritt fest:
>
> zu i) bleibt zu zeigen:
>
> [mm](n+1)^{13}-(n+1)\equiv0(mod2730)[/mm]
>
> umgeformt:
> [mm](n+1)^{13}-(n+1)=n^{13}-n+\vektor{13 \\ 1}n^{12}+...+\vektor{13 \\12 }n[/mm]
> ; +1 und -1 haben sich aufgehoben
Wie schön. Du hast also aus vorher zwei Termen jetzt nur 14 gemacht statt wie zu erwarten 16.
> da [mm]n^{13}-n \equiv0(mod2730)[/mm] als richtig angenommen wurde
> bleibt noch
>
> [mm]\vektor{13 \\ 1}n^{12}+...+\vektor{13 \\12 }n\equiv0(mod2730)[/mm]
> zu zeigen
>
> und da hörts auf.
Ja, da hätte ich auch keine Lust drauf. Sieht nach Sauarbeit aus. Mathematiker sind aber eher faul.
> Ich hab noch raugefunden, dass
> 2730=2*3*5*7*13 ist
Aha. Viel besser.
Wende also den chinesischen Restsatz mal rückwärts an.
[mm] n^{13}-n=(n^{12}-1)*n\equiv 0\mod{2*3*5*7*13}
[/mm]
Dann ist also für [mm] n\in\IN [/mm] und [mm] p\in\{2,3,5,7,13\}
[/mm]
[mm] n(n^{12}-1)\equiv 0\mod{p}\quad \Rightarrow n\equiv 0\mod{p}\quad \vee \quad n^{12}\equiv 1\mod{p}
[/mm]
Das ist mit dem ![[]](/images/popup.gif) "kleinen Fermat" doch ganz leicht zu zeigen.
> zu ii) bleibt zu zeigen:
>
> [mm]2^{2(n+1)+1}\equiv9(n+1)^{2}-3(n+1)+2(mod54)\gdw2^{2n+1+2}\equiv9n^{2}-3n+2+18n+9-3(mod54)[/mm]
>
> dann habe ich [mm]9n^{2}-3n+2[/mm] durch [mm]2^{2n+1}[/mm] (IV) ersetzt:
> [mm]2^{(2n+1)+2}\equiv2^{2n+1}+18n+6(mod54);[/mm]
> [mm]2^{2n+1}[/mm] auf beiden Seiten abgezogen:
> [mm]3*2^{2n+1}\equiv18n+6(mod54);[/mm]
> durch 6 gekürzt mit ggt(6,54)=6
> und erhalte:
> [mm]2^{2n}\equiv3n\red{-}1(mod9)[/mm] und da hörts auch hier auf.
Bis hierhin alles richtig, bis auf den letzten Tippfehler. Statt [mm] \red{-} [/mm] muss es ja [mm] \blue{+} [/mm] heißen. Nur noch ein paar Umformungen:
[mm] 2^{2n}=\left(2^2\right)^n=4^n\equiv 3n\blue{+}1\mod{9}
[/mm]
[mm] \gdw\quad 4^n-1=(4-1)*\summe_{k=0}^{n-1} 4^k\equiv 3n\mod{9}
[/mm]
[mm] \gdw\quad \summe_{k=0}^{n-1} 4^k\equiv n\mod{3}
[/mm]
[mm] \gdw\quad \summe_{k=0}^{n-1} \blue{1}^k\blue{=n}\equiv n\mod{3}
[/mm]
wzzw.
> Dankbar wär ich für jeden Tipp, wie ich die Aufgaben zum
> Ende bringen könnte.
> Gruß
Auch bei der zweiten Aufgabe wäre wahrscheinlich eine Betrachtung [mm] \mod{2} [/mm] und eine [mm] \mod{27} [/mm] praktischer gewesen, zumal sich die zweite auf [mm] \mod{9} [/mm] reduziert hätte.
Die Induktion trägt da eigentlich nichts Neues aus, ist also nur ein Arbeitsbeschaffungsprogramm.
lg
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:08 Do 07.01.2010 | | Autor: | Vic_Burns |
Hey! Vielen Dank für die Hilfe.
Das hilft mir bestimmt noch öfter :)
Gruß vic
|
|
|
|
