Teilbarkeit durch 30 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:05 Di 06.01.2009 | | Autor: | svcds |
| Aufgabe | | Beweisen Sie: Für jede natürliche Zahl a gilt: 30 | ( [mm] a^{25}) [/mm] - a) |
Hi,
also ich hab mir gedacht, dass man 30 auch als 5*6 schreiben kann, also ist [mm] (a^{25}) [/mm] - a durch 5 und 6 teilbar.
Kann man jetzt weitermachen, indem man mit Kongruenzen rechnet?
Also 6 [mm] \equiv (a^{25}) [/mm] - a und 5 [mm] \equiv (a^{25})-a [/mm] , d.h. mit 2 linearen Kongruenzen bei denen am Ende dasselbe dann steht und dann q.e.d. also bewiesen?
LG
svcds
|
|
| |
|
> Beweisen Sie: Für jede natürliche Zahl a gilt: 30 | (
> [mm]a^{25})[/mm] - a)
> Hi,
>
> also ich hab mir gedacht, dass man 30 auch als 5*6
> schreiben kann, also ist [mm](a^{25})[/mm] - a durch 5 und 6
> teilbar.
Hi Knut,
man muss nachweisen, dass [mm] a^{25}-a [/mm] durch 5 und 6
(oder durch die Primzahlen 2, 3 und 5) teilbar
ist. Und das klingt dann doch sehr nach dem
kleinen Fermatschen Satz, der sagt, dass eine
Primzahl p stets ein Teiler von [mm] a^{p-1}-1 [/mm] ist,
falls a nicht durch p teilbar ist.
Um ihn hier wirklich anwenden zu können, muss
man sich zuerst um mögliche Faktorzerlegungen
des Terms [mm] $a^{25}-a$ [/mm] kümmern - und das ist gar
nicht schwer.
LG
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:31 Do 08.01.2009 | | Autor: | svcds |
was wäre denn der erste Schritt?
also
a^(p-1) [mm] \equiv [/mm] 1 (mod p)
|
|
|
| |
|
Ja, das wäre schonmal ein Anfang.
Dann weißt Du zumindest etwas über die Restklassen mod 2,3,5.
Danach könnte Dir der ![[]](/images/popup.gif) Chinesische Restsatz weiterhelfen.
Grüße,
reverend
|
|
|
| |
|
hallo Knut,
ich habe mir das mit der Anwendung des "kleinen
Fermat" so gedacht:
Zu zeigen ist, dass der Term $\ [mm] T=a^{25}-\,a$ [/mm] durch $2$,
durch $3$ und durch $5$ teilbar ist, falls [mm] a\in\IN.
[/mm]
Nehmen wir mal den Fall $p=3$ :
Ist a selbst durch 3 teilbar, dann natürlich auch
[mm] T=a*(a^{24}-1). [/mm] Ist hingegen a nicht durch 3 teilbar,
dann ist die Voraussetzung für die Anwendung des
Satzes erfüllt, und er sagt, dass 3 ein Teiler von
[mm] a^{3-1}-1 [/mm] bzw. von [mm] a^2-1 [/mm] ist. Würde es nun gelingen zu
zeigen, dass [mm] a^2-1 [/mm] ein Teiler von [mm] a^{24}-1 [/mm] ist, dann
wären wir am Ziel. Nun setzen wir [mm] q=a^2 [/mm] und zeigen:
[mm] a^{24}-1=q^{12}-1 [/mm] ist stets durch [mm] q-1=a^2-1 [/mm] teilbar.
Dies ist einfach, denn
[mm] $\bruch{q^{12}-1}{q-1}\ [/mm] =\ [mm] 1+q+q^2+ [/mm] ..... + [mm] q^{11}$
[/mm]
(Summenformel für geometrische Zahlenfolge !)
Weil [mm] q=a^2 [/mm] ganzzahlig ist, stellt natürlich auch die
Summe auf der rechten Seite eine ganze Zahl dar.
Analog verfährt man mit den Fällen $p=2$ und $p=5$ .
LG al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:21 Do 08.01.2009 | | Autor: | svcds |
Man man man...da soll Arithmetik das leichteste sein bzw. die Anfangsvorlesung und dann immer sowas :), danke schon mal.
Man könnte dann doch a^24-1 durch [mm] a^2-1 [/mm] teilen oer? Also mit Polynomdivision , dann seh ich doch, dass es ein Teiler ist.
|
|
|
| |
|
> Man könnte dann doch a^24-1 durch [mm]a^2-1[/mm] teilen oder ?
> Also mit Polynomdivision , dann seh ich doch, dass es ein Teiler ist.
Klar, so geht's auch - Polynomdivision zwar etwas langw [mm] {\vektor{ier\\eil}} [/mm] ig ... 
Noch eine Idee: binomische Formeln:
$\ [mm] a^{24}-1=(a^{12}-1)*(a^{12}+1)$
[/mm]
$\ [mm] a^{12}-1=(a^{6}-1)*(a^{6}+1)$
[/mm]
etc.
LG
|
|
|
| |
|
Hallöchen...
ich habe die Aufgabe auch mal parallel gelöst und ich sehe gerade nicht das Problem, dass man noch Polynomdivision benutzen muss...
Ich habe auch [mm] a(a^{24}-1)\equiv [/mm] 0 benutzt. und dann eben auch aufgeteilt nach [mm] a\equiv [/mm] 0 oder [mm] a^{24}-1\equiv [/mm] 0 [mm] \gdw a^{24}\equiv [/mm] 1 (modulo der entsprechenden PZ).
Jetzt stelle ich [mm] a^{24} [/mm] "einfach" immer als Doppelpotenz dar, meine:
bspw. [mm] (a^{3-1})^{12} [/mm] für p=3
mit dem kleinen Fermat ist doch dann immer [mm] a^{3-1}\equiv [/mm] 1 (mod 3) also kann ich das ersetzen und es gilt immer [mm] 1^{12}\equiv [/mm] 1 (mod 3)
also für alle a...
und dann zeige ich das auch für 2 und 5. (bei der 2 braucht man ausnahmsweise beide bedingungen, da [mm] (a^{1})^{24} [/mm] nur [mm] \equiv [/mm] 1 für a ungerade...ist aber a gerade..gilt eben [mm] a\equiv [/mm] 0 (mod 2)
(mit diesen Begründungen kann man das übrigens ereitern und auch sehen, dass 42, 210, und 2730 auch [mm] a^{25}-a [/mm] teilt.)
Oder hab ich irgendwo einen Denkfehler??
LG, Laika
PS: ich wusste nicht, wie ich das hier anders als als Frage posten sollte... irgendwie ging "antworten" nicht... (habe jetzt (paar Minuten später) gesehen, dass ich auf die Frage hätte gehen müssen, um zu antworten...)
aber iwie ja auch OK, da ich gern jemand hätte, der da mal drüber guckt, was ich mir gedacht hab. Danke auf jeden Fall!
|
|
|
| |
|
Hallo Laikaloup, ![[willkommenvh]](/images/smileys/willkommenvh.png "[willkommenvh]")
Du hast keinen Denkfehler gemacht.
a^25-a ist in der Tat immer durch 2,3,5,7 und 13 teilbar und damit auch durch alle 31 Zahlen, die sich daraus zusammensetzen lassen.
Schwieriger nachzuweisen wäre, dass das dann auch alle garantierten Teilbarkeiten sind, aber das war ja auch nicht gefordert.
Grüße,
reverend
|
|
|
|
