Aufgabe Beweis Teilbarkeit < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeigen Sie:
[mm] 13 | (27^{1379} - 14^{1379}) [/mm] |
Hallo zusammen,
mittlerweile habe ich rausgefunden, dass man die Aufgabe mittels der folgenden Summenformel [m]x^n-y^n = (x-y) \summe_{i=0}^{n-1} x^{n-1-i} y^i [/m] nachweisen kann.
Ich habe also [m]x^n-y^n = (x-y) \summe_{i=0}^{n-1} x^{n-1-i} y^i [/m] mit [m]x = 27, y = 14, n = 1379[/m]:
Nachdem ich die Start- und Endwerte der Summe in die Funktion eingesetzt habe, sieht das folgendermaßen aus:
[m]27^{1379}-14^{1379} = (27-13) \summe_{i=0}^{1378} 27^{n-1-i} 14^i = 27^{1378} + 27^{1377} * 14 + 27^{1376} * 14^2 + ... + 14^{1378} [/m]
Ja, die "Indizien" sprechen dafür [m]27-14 = 13[/m] und [m]13 | 1378[/m], aber
wie kann ich es mathematisch korrekt aufschreiben, so dass es wirklich gezeigt / bewiesen werden kann?
Hoffe ich habe mich nirgendswo vertippt :)
Vielen Dank im voraus für Eure Hilfe!
|
|
| |
|
Hallo,
wie du bereits sagtest ist:
$ [mm] 27^{1379}-14^{1379} [/mm] = (27-14) [mm] \summe_{i=0}^{1378} 27^{n-1-i} 14^i [/mm] $
Die Summe ist eine natürliche Zahl, nennen wir sie k; Also:
$ [mm] 27^{1379}-14^{1379} [/mm] = (27-14) k=13 k$
und damit ist 13 ein Teiler.
Imho ist hier aber Restklassenrechnung der natürlichere Ansatzpunkt zum Beweis (und geht mindestens genau so schnell.)
|
|
|
| |
|
Hallo gummibaum,
hier mal ganz kurz der andere Weg:
> Zeigen Sie:
>
> [mm]13 | (27^{1379} - 14^{1379})[/mm]
[mm] 27^{1379}-14^{1379}\equiv 1^{1379}-1^{1379}\equiv 0\bmod{13}
[/mm]
Fertig.
Natürlich kann man auch den Exponenten "reduzieren" (das allerdings mod 12); das ist hier aber gar nicht nötig.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:08 Do 06.03.2014 | | Autor: | gummibaum |
Vielen lieben Dank!
|
|
|
| |
|
Möchte das Thema nochmal aufgreifen...
Kann man den Weg noch etwas ausführlicher erklären?
|
|
|
| |
|
Was genau ist denn unklar? Modulo einer festen Zahl (13) kann man gewöhnlich addieren und multiplizieren. Gilt insbesondere [mm] a=1\mod13, [/mm] so gilt auch [mm] a^n=1\mod13 [/mm] für alle ganzen Zahlen $ n $. Nichts amderes hat reverend verwendet.
Liebe Grüße,
UniversellesObjekt
|
|
|
| |
|
Hi.
> > Zeigen Sie:
> > [mm]13 | (27^{1379} - 14^{1379})[/mm]
>
> [mm]27^{1379}-14^{1379}\equiv 1^{1379}-1^{1379}\equiv 0\bmod{13}[/mm]
>
> Fertig.
> Natürlich kann man auch den Exponenten "reduzieren" (das
> allerdings mod 12); das ist hier aber gar nicht nötig.
>
> Grüße
> reverend
Würde das tatsächlich ausreichen? Es scheint mir so wenig... trotz der logischen Nachvollziehbar- und Knappheit!
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:23 Mo 08.09.2014 | | Autor: | Marcel |
Hallo,
> Hi.
>
> > > Zeigen Sie:
> > > [mm]13 | (27^{1379} - 14^{1379})[/mm]
> >
> > [mm]27^{1379}-14^{1379}\equiv 1^{1379}-1^{1379}\equiv 0\bmod{13}[/mm]
>
> >
> > Fertig.
> > Natürlich kann man auch den Exponenten "reduzieren"
> (das
> > allerdings mod 12); das ist hier aber gar nicht nötig.
> >
> > Grüße
> > reverend
>
> Würde das tatsächlich ausreichen? Es scheint mir so
> wenig... trotz der logischen Nachvollziehbar- und
> Knappheit!
https://matheraum.de/read?i=1013354!
Wie gesagt:
$1 [mm] \equiv [/mm] 27 [mm] \mod [/mm] 13$
liefert auch
[mm] $1^{N} \equiv 27^N \mod [/mm] 13$
für jedes $N [mm] \in \IN\,.$
[/mm]
Zudem kennst Du hoffentlich die Regel
$a [mm] \equiv [/mm] b [mm] \mod [/mm] m$ und $c [mm] \equiv [/mm] d [mm] \mod [/mm] m$
liefert
$a-c [mm] \equiv [/mm] b-d [mm] \mod m\,.$
[/mm]
Falls nicht: Der Beweis ist ein Einzeiler wegen
[mm] $a-c-(b-d)=(a-b)-(c-d)\,.$
[/mm]
Übrigens hätte man mit dem kleinen Fermat (aber nicht dem kleinen Gauß)
durchaus auch den Exponenten reduzieren können gemäß
[mm] $a^p \equiv [/mm] a$ [mm] $\mod$ $p\,$ [/mm] für alle $a [mm] \in \IZ$ [/mm] und alle $p [mm] \in \IP.$
[/mm]
Aber das wäre nicht besonders schön, und auch dann würde man sicher
irgendwann
[mm] $27=2*13+1\,$
[/mm]
benutzen wollen.
Übrigens wäre das sowieso auch ein gehbarer Weg gewesen:
[mm] $14=(13+1)^{1379}$
[/mm]
und
[mm] $27=(2*13+1)^{1379}\,.$
[/mm]
Du siehst hier (relativ) schnell, dass bei beiden Zahlen bei Division durch
[mm] $13\,$ [/mm] "der Rest [mm] $1\,$" [/mm] bleibt. (Schnell sehen bedeutet:
Binomische Formel nutzen und schauen, in welchen Summanden der
Faktor 13 offensichtlich drinsteckt!)
Gruß,
Marcel
|
|
|
| |
|
Ergänzung.
Gegeben ist also [m]m=13, a=27^{1379}, b=13^{1379}[/m]
Zu zeigen: [m]m \, | \, (a-b) \Leftrightarrow a \equiv b \mod m[/m]
Es gilt: [m]27^{1379} - 13^{1379} \equiv 14^{1379} - 14^{1379} \equiv 0 \mod 13[/m]
Also gilt: [m]13 \, | \, 27^{1379} - 13^{1379}[/m] bzw. [m]13 \, | \, 0[/m]
(So nebenbei: Muss oben im letzten Schritt eigentlich [m]... \, = 0[/m] oder [m]... \, \equiv 0[/m] stehen?)
Zusätzlich kann man sagen, dass für alle [m]k \in \IN[/m] gilt:
[m]k \, | \, 0[/m], also jede natürliche Zahl ist Teiler von 0.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:45 Mo 08.09.2014 | | Autor: | Marcel |
Hallo,
> Ergänzung.
>
> Gegeben ist also [m]m=13, a=27^{1379}, b=13^{1379}[/m]
es war [mm] $b=\red{14}^{1379}$
[/mm]
> Zu zeigen: [m]m \, | \, (a-b) \Leftrightarrow a \equiv b \mod m[/m]
Vorsicht: Nicht diese Äquivalenz ist zu zeigen. Du meinst, dass eine der
beiden Aussagen (die zueinander äquivalent sind), zu beweisen ist!
(Du könntest also schreiben:
Zu zeigen: $m|(a-b)$ [mm] ($\iff$ [/mm] $a [mm] \equiv [/mm] b [mm] \mod [/mm] m$).
Dabei bedeutet das in Klammern Geschriebene eine Ergänzung, d.h. es
ist zu lesen als:
Zu zeigen: [mm] $m|(a-b)\,$ [/mm] bzw. (die dazu gleichwertige Aussage) $a [mm] \equiv [/mm] b [mm] \mod m\,.$)
[/mm]
> Es gilt: [m]27^{1379} - 13^{1379} \equiv 14^{1379} - 14^{1379} \equiv 0 \mod 13[/m]
Das ist auch richtig, das folgt aber aus
$27 [mm] \equiv [/mm] 14 [mm] \mod 13\,.$
[/mm]
Und, wie UniversellesObjekt erwähnte, weil Du hier "wie üblich multiplizieren"
(und damit auch potenzieren) darfst. Etwas lasch gesagt!
> Also gilt: [m]13 \, | \red{(}\, 27^{1379} - 13^{1379}\red{)}[/m]
Besser Klammern setzen.
> bzw. [m]13 \, | \, 0[/m]
Besser, Du sagst:
Wegen $27 [mm] \equiv [/mm] 14 [mm] \mod [/mm] 13$ ist
[mm] $27^{1379}\equiv 14^{1379} \mod [/mm] 13$
gleichwertig zu der offensichtlich wahren Aussage
[mm] $14^{1379} \equiv 14^{1379} \mod [/mm] 13$
bzw.
[mm] $14^{1379}-14^{1379} \equiv [/mm] 0 [mm] \mod 13\,.$
[/mm]
Aus dieser folgt also die Behauptung!
> (So nebenbei: Muss oben im letzten Schritt eigentlich [m]... \, = 0[/m]
> oder [m]... \, \equiv 0[/m] stehen?)
In diesem speziellen Fall geht eigentlich beides. Die Bedeutung wäre ein
wenig anders. Gleichheit ist halt Gleichheit. Solange da [mm] $=\,$ [/mm] und [mm] $\equiv$ [/mm] verwendet
werden, meint man halt "kongruent modulo". Deswegen darfst Du
$40 [mm] \equiv [/mm] 27 [mm] \equiv [/mm] 14 [mm] \mod [/mm] 13$
schreiben, aber in
$40 [mm] \equiv [/mm] 27=14 [mm] \mod 13\,$ [/mm]
würde man [mm] $27=14\,$ [/mm] anstreichen. (Naja, es sei denn, Du sagst irgendwo
so etwas wie, dass [mm] $14\,$ [/mm] die $14 [mm] \in \IZ/(13\IZ)$ [/mm] sei - aber warum schreibst
Du dann überhaupt noch [mm] $\equiv$... $\mod [/mm] 13$?)
Nun gibt's aber auch noch den Modulo als einen ausgezeichneten
Respräsentanten, und dann würde man
$1=27 [mm] \mod 13\,$
[/mm]
schreiben dürfen, weil eben [mm] $27\,$ [/mm] bei Division durch [mm] $13\,$ [/mm] den Rest [mm] $1\,$ [/mm] läßt.
(Hier würde aber $27=1 [mm] \mod [/mm] 13$ falsch werden. Warum das so ist:
![[]](/images/popup.gif) Nachlesen: http://de.wikipedia.org/wiki/Division_mit_Rest#Modulo)
Mach' Dir halt klar, was die Symbole im entsprechenden Kontext bedeuten,
dann merkst Du selbst, was Du (nicht) schreiben darfst (solltest).
> Zusätzlich kann man sagen, dass für alle [m]k \in \IN[/m] gilt:
> [m]k \, | \, 0[/m], also jede natürliche Zahl ist Teiler von 0.
Ja, es reicht aber [mm] $13\,|\, 0\,,$ [/mm] so dass (etwa)
$0 [mm] \equiv [/mm] 0 [mm] \mod 13\,$
[/mm]
sicherlich wahr ist!
Gruß,
Marcel
|
|
|
|
