matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenZahlentheorieAufgabe Beweis Teilbarkeit
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Zahlentheorie" - Aufgabe Beweis Teilbarkeit
Aufgabe Beweis Teilbarkeit < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Aufgabe Beweis Teilbarkeit: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:46 Mi 05.03.2014
Autor: gummibaum

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!

        
Bezug
Aufgabe Beweis Teilbarkeit: Antwort
Status: (Antwort) fertig Status 
Datum: 22:58 Mi 05.03.2014
Autor: MaslanyFanclub

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.)

Bezug
        
Bezug
Aufgabe Beweis Teilbarkeit: Restklassen
Status: (Antwort) fertig Status 
Datum: 23:08 Mi 05.03.2014
Autor: reverend

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

Bezug
                
Bezug
Aufgabe Beweis Teilbarkeit: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:08 Do 06.03.2014
Autor: gummibaum

Vielen lieben Dank!

Bezug
                
Bezug
Aufgabe Beweis Teilbarkeit: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 11:02 Di 11.03.2014
Autor: gummibaum

Möchte das Thema nochmal aufgreifen...
Kann man den Weg noch etwas ausführlicher erklären?

Bezug
                        
Bezug
Aufgabe Beweis Teilbarkeit: Antwort
Status: (Antwort) fertig Status 
Datum: 07:13 Do 13.03.2014
Autor: UniversellesObjekt

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

Bezug
                
Bezug
Aufgabe Beweis Teilbarkeit: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:45 Mo 08.09.2014
Autor: gummibaum

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!

Bezug
                        
Bezug
Aufgabe Beweis Teilbarkeit: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                        
Bezug
Aufgabe Beweis Teilbarkeit: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:24 Mo 08.09.2014
Autor: gummibaum

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.


Bezug
                                
Bezug
Aufgabe Beweis Teilbarkeit: Antwort
Status: (Antwort) fertig Status 
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:
    []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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]