Teilbarkeit in Z < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:31 Do 18.07.2013 | | Autor: | SaskiaCl |
| Aufgabe | a)Zeigen sie für a,b [mm] \in [/mm] Z gilt:
19|10a +b [mm] \gdw [/mm] 19|a +2b
b)Eine natürliche Zahl ist genau dann durch 3 teilbar, wenn ihre Quersumme durch 3 teilbar ist |
Hallo,
Mein Beweis:
a+2b=0 mod 19
[mm] \gdw [/mm] a=-2b
10a +b =0 |*2
[mm] \gdw [/mm] a+2b=0
[mm] \gdw [/mm] a=-2b
Ist der Beweis so korrekt?
Leider habe ich zu der zweiten Aufgabe noch keine Idee
Danke
Saskia
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:59 Do 18.07.2013 | | Autor: | Marcel |
Hallo Saskia,
> a)Zeigen sie für a,b [mm]\in[/mm] Z gilt:
> 19|10a +b [mm]\gdw[/mm] 19|a +2b
>
> b)Eine natürliche Zahl ist genau dann durch 3 teilbar,
> wenn ihre Quersumme durch 3 teilbar ist
> Hallo,
> Mein Beweis:
>
> a+2b=0 mod 19
das Zeichen, was Du vermutlich suchst, ist [mm] $\equiv$ [/mm] anstatt [mm] $=\,.$
[/mm]
> [mm]\gdw[/mm] a=-2b
Mod 19
> 10a +b =0 |*2
> [mm]\gdw[/mm] a+2b=0
> [mm]\gdw[/mm] a=-2b
>
> Ist der Beweis so korrekt?
Eigentlich eher nicht - aber wenn man weiß, was Du meinst, dann passt es
teilweise. Du musst es halt sauber aufschreiben:
Aus
$$19|10a+b [mm] \iff [/mm] 10a [mm] \equiv [/mm] -b [mm] \mod [/mm] 19$$
folgt wegen $2 [mm] \equiv [/mm] 2 [mm] \mod [/mm] 19$ sofort
$$2*10a=20a [mm] \equiv [/mm] 2*(-b)=-2b [mm] \mod 19\,.$$
[/mm]
Wegen [mm] $19a\equiv [/mm] 0 [mm] \mod [/mm] 19$ folgt
[mm] $$20a-19a\equiv [/mm] -2b -0 [mm] \mod 19\,,$$
[/mm]
also
$a [mm] \equiv [/mm] -2b [mm] \mod 19\,.$
[/mm]
(Das gilt nach den Regeln aus Satz 4.2 von ![[]](/images/popup.gif) hier (klick!) - eventuell wirst Du
den Ausschnitt nicht sehen können, dann frage vielleicht nach, ich kann es
auch schnell einfach abtippen.)
Entsprechend kannst Du (ich schreibe jetzt nur noch [mm] "$...\stackrel{19}{\equiv}...$" [/mm] anstatt
[mm] "$...\equiv [/mm] ... [mm] \mod [/mm] 19$," das ist ja eh symmetrisch!), wenn Du von
$a [mm] \stackrel{19}{\equiv} [/mm] -2b$
ausgehst, doch folgern, dass
$10a [mm] \stackrel{19}{\equiv} -20b\,.$
[/mm]
Unter Beachtung von
$0 [mm] \stackrel{19}{\equiv} [/mm] 19b$
folgt dann
$0+10a=10a [mm] \stackrel{19}{\equiv} -b=-20b+19b\,.$
[/mm]
> Leider habe ich zu der zweiten Aufgabe noch keine Idee
Das findest Du in obigem Buch sofort auf der gleichen Seite, wo auch der
erwähnte Satz zu finden ist (unten).
Die Idee ist einfach:
Für jedes $k [mm] \in \IN_0$ [/mm] gilt [mm] $10^k \stackrel{3}{\equiv}1\,.$ [/mm] Daraus folgt für eine
Zahl $a [mm] \in \IN_0$ [/mm] so, dass [mm] $a=\sum_{k=0}^n a_k 10^k$ [/mm] mit Ziffern [mm] $a_k \in \{0,...,9\}$ [/mm] ($k=0,...,n$) [mm] ($a\,$ [/mm] hat also
[mm] $n+1\,$ [/mm] Ziffern, sofern denn [mm] $a_n \not=0$ [/mm] ist) gilt
[mm] $a=\sum_{k=0}^n a_k 10^k \stackrel{3}{\equiv}...$?
[/mm]
(Hinweis: Am Besten ziehst Du die Überlegung eigentlich rückwärts auf:
Aus [mm] $10^0 \stackrel{3}{\equiv}1,$ $10^1\stackrel{3}{\equiv} [/mm] 1, [mm] \ldots$ $,10^n \stackrel{3}{\equiv} [/mm] 1$ ergibt sich auch
[mm] $a_k 10^k \stackrel{3}{\equiv}a_k*1=a_k\,,$
[/mm]
für [mm] $k=0,...,n\,.$ [/mm] Jetzt bilde die Summe dieser [mm] $n+1\,$ [/mm] Gleichungen.)
Nebenbei: Der Beweis geht auch nur mit Mitteln der Analysis:
Sei [mm] $a=\sum_{k=0}^n a_k 10^k$ [/mm] wie oben. Dann folgt
[mm] $a=\sum_{k=0}^n a_k (9+1)^k=\sum_{k=0}^n a_k\sum_{m=0}^k [/mm] {k [mm] \choose [/mm] m} [mm] 9^k=\sum_{k=0}^n a_k +\underbrace{\sum_{k=\red{1}}^n a_k \sum_{m=\red{1}}^k {k \choose m}9^k}_{=:S}\,.$
[/mm]
(Rechne das bitte nochmal nach - ich hoffe mal, dass das so passt. Aber
ich denke schon...
Mit geht's aber mehr um das Prinzip:
Zerlege halt [mm] $\sum_{k=0}^n a_k (9+1)^k$ [/mm] so in zwei Summanden, dass einer der beiden
Summanden die Quersumme ist!)
Offensichtlich ist [mm] $S\,$ [/mm] durch 3 teilbar (läßt also den Rest 0 bei Division durch 3).
Also folgt...?
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:19 Do 18.07.2013 | | Autor: | SaskiaCl |
Vielen Dank für die Ausführliche Antwort, ich werde jetzt erst einmal eine weitere Aufgabe mit diesem Verfahren versuchen zu lösen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:21 Fr 19.07.2013 | | Autor: | fred97 |
Zu a): Machen wir mal die Richtung [mm] "\Rightarrow". [/mm] Geht das denn ohne die "Modulo-Rechnerei" nicht schneller ?
Aus $10a+b=k*19$ mit einem $k [mm] \in \IZ$ [/mm] folgt:
$b=k*19-10a$.
Somit ist
$a+2b=a+38*k-20*a=38*k-19*a=19(2k-a)$
Die Richtung [mm] "\Leftarrow" [/mm] geht genauso.
FRED
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:46 Fr 19.07.2013 | | Autor: | Marcel |
Hi Fred,
> Zu a): Machen wir mal die Richtung [mm]"\Rightarrow".[/mm] Geht das
> denn ohne die "Modulo-Rechnerei" nicht schneller ?
>
> Aus [mm]10a+b=k*19[/mm] mit einem [mm]k \in \IZ[/mm] folgt:
>
> [mm]b=k*19-10a[/mm].
>
> Somit ist
>
> [mm]a+2b=a+38*k-20*a=38*k-19*a=19(2k-a)[/mm]
Du hast es übersichtlicher aufgeschrieben, aber mit der "Modulo-Rechnerei"
kann man es eigentlich "analog schnell" aufschreiben. Ich hab's halt extrem
ausführlich notiert.
> Die Richtung [mm]"\Leftarrow"[/mm] geht genauso.
Wobei ich's nach wie vor gut finde, dass man mit elementarsten
Überlegungen das Ganze auch "schnell" hinbekommt. Hier kann man
quasi sagen: Die "Modulo-Rechnerei" ist nur Umschreiberei mit einer
zusätzlichen Definition - eigentlich kann man auch (ohne
"Neuerkenntnisse" bzw. "Tricks") auch einfach rein per Definitionem
arbeiten: Genau das zeigst Du ja! 
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:02 Fr 19.07.2013 | | Autor: | fred97 |
> Hi Fred,
>
> > Zu a): Machen wir mal die Richtung [mm]"\Rightarrow".[/mm] Geht das
> > denn ohne die "Modulo-Rechnerei" nicht schneller ?
> >
> > Aus [mm]10a+b=k*19[/mm] mit einem [mm]k \in \IZ[/mm] folgt:
> >
> > [mm]b=k*19-10a[/mm].
> >
> > Somit ist
> >
> > [mm]a+2b=a+38*k-20*a=38*k-19*a=19(2k-a)[/mm]
>
> Du hast es übersichtlicher aufgeschrieben, aber mit der
> "Modulo-Rechnerei"
> kann man es eigentlich "analog schnell" aufschreiben. Ich
> hab's halt extrem
> ausführlich notiert.
>
> > Die Richtung [mm]"\Leftarrow"[/mm] geht genauso.
>
> Wobei ich's nach wie vor gut finde, dass man mit
> elementarsten
> Überlegungen das Ganze auch "schnell" hinbekommt. Hier
> kann man
> quasi sagen: Die "Modulo-Rechnerei" ist nur Umschreiberei
> mit einer
> zusätzlichen Definition - eigentlich kann man auch (ohne
> "Neuerkenntnisse" bzw. "Tricks") auch einfach rein per
> Definitionem
> arbeiten: Genau das zeigst Du ja!
>
> Gruß,
> Marcel
Hallo Marcel,
ich muß Dir was gestehen (sags aber nicht weiter):
die "Modulo-Rechnerei" hab ich nie gemocht.
Frag mich nicht warum.
Gruß FRED
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:10 Fr 19.07.2013 | | Autor: | Marcel |
Hallo Fred,
> > Hi Fred,
> >
> > > Zu a): Machen wir mal die Richtung [mm]"\Rightarrow".[/mm] Geht das
> > > denn ohne die "Modulo-Rechnerei" nicht schneller ?
> > >
> > > Aus [mm]10a+b=k*19[/mm] mit einem [mm]k \in \IZ[/mm] folgt:
> > >
> > > [mm]b=k*19-10a[/mm].
> > >
> > > Somit ist
> > >
> > > [mm]a+2b=a+38*k-20*a=38*k-19*a=19(2k-a)[/mm]
> >
> > Du hast es übersichtlicher aufgeschrieben, aber mit der
> > "Modulo-Rechnerei"
> > kann man es eigentlich "analog schnell" aufschreiben.
> Ich
> > hab's halt extrem
> > ausführlich notiert.
> >
> > > Die Richtung [mm]"\Leftarrow"[/mm] geht genauso.
> >
> > Wobei ich's nach wie vor gut finde, dass man mit
> > elementarsten
> > Überlegungen das Ganze auch "schnell" hinbekommt. Hier
> > kann man
> > quasi sagen: Die "Modulo-Rechnerei" ist nur
> Umschreiberei
> > mit einer
> > zusätzlichen Definition - eigentlich kann man auch
> (ohne
> > "Neuerkenntnisse" bzw. "Tricks") auch einfach rein per
> > Definitionem
> > arbeiten: Genau das zeigst Du ja!
> >
> > Gruß,
> > Marcel
>
>
> Hallo Marcel,
>
> ich muß Dir was gestehen (sags aber nicht weiter):
würde ich nie tun - ich würde es vielleicht verlinken. ![[grins]](/images/smileys/grins.gif "[grins]")
> die "Modulo-Rechnerei" hab ich nie gemocht.
>
> Frag mich nicht warum.
Ich finde schon "die gängige Notation" blöd:
Man schreibt
$x [mm] \equiv [/mm] y [mm] \mod [/mm] n$
bzw., wenn das [mm] $n\,$ [/mm] klar ist
$x [mm] \equiv y\,.$
[/mm]
Daher habe ich auch meine eigene Notation kreiert:
$x [mm] \stackrel{n}{\equiv} y\,,$
[/mm]
die auch wegen der Symmetrie gerechtfertigt ist. Man könnte auch
$x [mm] \stackrel{\mod n}{\equiv} [/mm] y$
schreiben, aber das ist mir dann schon wieder "zu viel des Guten". Dann
vielleicht eher direkt
$x [mm] \stackrel{\mod n}{=} y\,,$
[/mm]
d.h. anstatt des [mm] $\equiv$ [/mm] ein [mm] $=\,.$
[/mm]
P.S. Ob die Schreibweise vielleicht auch schon von jemand anderem
Verwendung findet, sei mal dahingestellt. Das weiß ich nicht. Ich frage mich
nur, wenn nicht, wieso das keiner macht:
Denn $x [mm] \equiv [/mm] y$ zu schreiben birgt halt die Gefahr, dass man irgendwann doch nicht
mehr "Modulo n" rechnet, und das dann vergisst, zu beachten...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:16 Fr 19.07.2013 | | Autor: | fred97 |
Hallo Marcel,
das
$ x [mm] \stackrel{n}{\equiv} [/mm] y\ $
war eine gute Idee von Dir. Nun muß ich aber aufpassen, dass mir die "Modulo-Rechnerei" auf meine alten Tage nicht zu sehr ans Herz wächst.
Gruß FRED
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:55 Fr 19.07.2013 | | Autor: | Marcel |
Hallo Fred,
> [mm]x \stackrel{n}{\equiv} y\[/mm]
>
> war eine gute Idee von Dir. Nun muß ich aber aufpassen,
> dass mir die "Modulo-Rechnerei" auf meine alten Tage nicht
> zu sehr ans Herz wächst.
sag's auch keinem weiter: Ich mochte die Modulo-Rechnerei gar nicht, bis
ich mir diese eigene Notation gebastelt habe. Jetzt mag' ich sie aber auch
nur ein bisschen lieber - von daher glaube ich nicht, dass sie Dir jetzt auf
einmal total ans Herz wächst.
P.S.
Gauss: Untersuchungen über höhere Arithmetik
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:59 Fr 19.07.2013 | | Autor: | fred97 |
> Hallo Fred,
>
> > [mm]x \stackrel{n}{\equiv} y\[/mm]
> >
> > war eine gute Idee von Dir. Nun muß ich aber aufpassen,
> > dass mir die "Modulo-Rechnerei" auf meine alten Tage nicht
> > zu sehr ans Herz wächst.
>
> sag's auch keinem weiter: Ich mochte die Modulo-Rechnerei
> gar nicht, bis
> ich mir diese eigene Notation gebastelt habe. Jetzt mag'
> ich sie aber auch
> nur ein bisschen lieber - von daher glaube ich nicht, dass
> sie Dir jetzt auf
> einmal total ans Herz wächst.
>
> P.S.
>
> Gauss: Untersuchungen über höhere Arithmetik
danke für den schönen Link
FRED
>
> Gruß,
> Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:06 Fr 19.07.2013 | | Autor: | Marcel |
Hi,
a) kann man übrigens auch so lösen:
[mm] $\Rightarrow$:
[/mm]
$19|10a+b [mm] \iff [/mm] 10a+b [mm] \stackrel{19}{\equiv}0 \Longrightarrow [/mm] 10a+b-19a=-9a+b [mm] \stackrel{19}{\equiv} 0\,.$
[/mm]
Addiert man die erste und die letzte Modulo-Gleichheit, so folgt
[mm] $(10a+b)+(-9a+b)\stackrel{19}{\equiv}0 \iff [/mm] a+2b [mm] \stackrel{19}{\equiv}0\,.$
[/mm]
[mm] $\Leftarrow$
[/mm]
$a+2b [mm] \stackrel{19}{\equiv} [/mm] 0 [mm] \Rightarrow [/mm] 11a+22b [mm] \stackrel{19}{\equiv} [/mm] 0$
Subtrahiert man die erste von der letzten Gleichheit:
$11a+22b-(a+2b) [mm] \stackrel{19}{\equiv} [/mm] 0 [mm] \iff [/mm] 10a+20b [mm] \stackrel{19}{\equiv} 0\,.$
[/mm]
Jetzt kann man noch rechnen
$10a+20b [mm] \stackrel{19}{\equiv} [/mm] 0 [mm] \Longrightarrow [/mm] 10a+20b-19b=10a+b [mm] \stackrel{19}{\equiv}0$
[/mm]
und ist fertig.
Nach wie vor: "$x [mm] \stackrel{19}{\equiv} [/mm] y$" steht für $x [mm] \equiv [/mm] y [mm] \mod 19\,.$
[/mm]
Grund, warum man so rechnen darf, wie ich es oben getan habe:
Sind $k, [mm] \ell \in \IZ$ [/mm] beliebig, aber fest, so folgt
$x [mm] \stackrel{n}{\equiv}y \iff [/mm] x+k*n [mm] \stackrel{19}{\equiv} y+\ell*n\,.$
[/mm]
Gruß,
Marcel
|
|
|
|
