Modulo-Rechnung und Logik < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 20:45 Sa 08.03.2014 | | Autor: | gummibaum |
| Aufgabe 1 | Sei [mm] n\in\IN [/mm] in Dezimalschreibweise gegeben als [m]n = x_1, x_2...x_k[/m], wobei [m]x_i \in \{0,...9\} [/m] für [m]i = 1, ... , k. [/m]
Weisen Sie durch modulo-Rechnung und Logik nach: n ist durch 5 teilbar [mm] \Leftrightarrow x_k \in \{0,5\} [/mm] |
| Aufgabe 2 | Sei [m]x \in \IN[/m] in Dezimalschreibweise gegeben als [m]x =x_nx_{n-1}...x_1x_0[/m] wobei [m]x_i \in \{0,...9 \}[/m] für [m]i = 0,...,n[/m].
Weisen Sie durch modulo-Rechnung und Logik nach:
x ist durch 9 teilbar [m]\Leftrightarrow[/m] die Quersumme von x ist durch 9 teilbar.
Hinweis: [m]10^i = 10^i - 1^i + 1[/m], es gilt: [m](x-y) \, | \, (x^i-y^i)[/m] für alle [m]i \in \IN_0, x, y \in \IR[/m]. |
Kann mir jemand hier auf die Sprünge helfen?
Wie kann ich an die oder i.A. an solche Aufgaben rangehen?
Bitte keine Lösungen, sondern nur Tipps, möchte alles selbst lösen!
Vielen Dank im voraus!
|
|
| |
|
Ist es eigentlich Absicht, dass bei den zwei Aufgaben die ziffern einer Zahl in genau umgekehrter Weise durchgezählt werden?
Tipp:
$ x [mm] =x_nx_{n-1}...x_1x_0 =\sum_{i=0}^n x_i 10^i$ [/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:25 Sa 08.03.2014 | | Autor: | Marcel |
Hallo,
> Sei [mm]n\in\IN[/mm] in Dezimalschreibweise gegeben als [m]n = x_1, x_2...x_k[/m],
> wobei [m]x_i \in \{0,...9\}[/m] für [m]i = 1, ... , k.[/m]
> Weisen Sie
> durch modulo-Rechnung und Logik nach: n ist durch 5 teilbar
> [mm]\Leftrightarrow x_k \in \{0,5\}[/mm]
es wurde ja schon etwas gesagt: Verwende zunächst
[mm] $n=\sum_{n=1}^k x_{k} 10^{k-n}.$
[/mm]
Dann hast Du zwei Beweisteile:
1. [mm] $\Rightarrow:$ [/mm] Vorausgesetzt wird, dass $5 | [mm] n\,.$ [/mm] Du sollst nun nachweisen:
Dann folgt auch $5 | [mm] x_k\,.$
[/mm]
2. [mm] $\Leftarrow:$ [/mm] Vorausgesetzt wird, dass $5 | [mm] x_k\,.$ [/mm] Du sollst nun nachweisen:
Dann folgt auch $5 | [mm] n\,.$ [/mm]
Damit Du ein wenig was siehst, schreibe ich Dir schonmal etwas zu 2.
(wenngleich die Methode da nicht sehr schön und viel zu umständlich
exzerziert wird - aber lass' Dir halt was einfallen, wie man das besser und
kürzer notieren kann mit dem, was Dir zur Verfügung steht):
Es gelte also $5 | [mm] x_k\,.$ [/mm] Wegen $5 | [mm] 10^{n-k}$ [/mm] für $(n-k) [mm] \in \IN=\IN \setminus \{0\}$
[/mm]
können wir schreiben:
[mm] $5|x_k$ [/mm] und $5 | [mm] 10^{1}$ [/mm]
[mm] $\Rightarrow$ [/mm] $5 | [mm] (x_k+x_{k-1}*10^{\overbrace{n-(n-1)}^{=1}}).$
[/mm]
Damit folgt weiter
$5 | [mm] (x_k+x_{k-1}*10^{1}))$ [/mm] und [mm] $5|10^{2}$ [/mm]
[mm] $\Rightarrow$ [/mm] $5 | [mm] (x_k+x_{k-1}*10^{n-(n-1)}+x_{k-2}*10^{n-(n-2)})= (x_k+x_{k-1}*10^{1}+x_{k-2}*10^{2})$
[/mm]
Fortführung dieser Überlegung zeigt
[mm] $5|\sum...=n\,.$
[/mm]
> Sei [m]x \in \IN[/m] in
> Dezimalschreibweise gegeben als [m]x =x_nx_{n-1}...x_1x_0[/m]
> wobei [m]x_i \in \{0,...9 \}[/m] für [m]i = 0,...,n[/m].
> Weisen Sie
> durch modulo-Rechnung und Logik nach:
> x ist durch 9 teilbar [m]\Leftrightarrow[/m] die Quersumme von x
> ist durch 9 teilbar.
> Hinweis: [m]10^i = 10^i - 1^i + 1[/m], es gilt: [m](x-y) \, | \, (x^i-y^i)[/m]
> für alle [m]i \in \IN_0, x, y \in \IR[/m].
Ich gebe Dir auch mal einen Tipp zum Tipp: Man kann einfach mal
[mm] $x^{n+1}-y^{n+1}=(x-y)*\sum_{k=0}^n x^k y^{n-k}$
[/mm]
nachrechnen.
(Und nur, damit "solche Formeln" nicht einfach vom Himmel fallen:
Mit Polynomdivision berechne man
[mm] $(x^{n+1}-y^{n+1})/(x-y).$
[/mm]
Und selbst, wenn man das mit "dem allgemeinen [mm] $n\,$" [/mm] vielleicht erstmal
nicht überblickt:
Man kann ja erstmal sowas für
[mm] $n=1,2,3,4,...\,$
[/mm]
bspw. ausrechnen und dann eine Formel vermuten - die man, wenn man
sonst so gar keine Idee hätte, per vollst. Induktion beweisen kann.)
Reicht das so erstmal als ersten Denkanstoss? (Die erste Aufgabe ist ja
nun eigentlich wirklich schnell gelöst - schau' in Deine Unterlagen, welche
Rechenregeln bzgl. der Modulo-Rechnung ihr benutzen dürft!)
Gruß,
Marcel
|
|
|
| |
|
Vielen Dank erstmal für Eure ausführlichen Antworten.
Ich hätte erstmal eine Bestandaufnahme gemacht, also:
Vor.: [m]n \in \IN[/m] mit [m]n = x_1,x_2...x_k[/m] wobei [m]x_i \in \{ 0,...9 \}[/m] für [m]i = 1,...k[/m] und [m]x_k \in \{ 0, 5 \}[/m] (laut Aufgabenstellung), also für [m]x_k[/m] kommen quasi nur die 0 und 5 in Betracht, weil diese bereits explizit angegeben worden sind: [m]x_k \in \{ 0, 5 \}[/m]
Da es sich um eine Äquivalenz, also eine Biimplikation handelt, schreibe ich die Aufgabenstellung als Aussageformen...
Zu zeigen: [m](5|n \Rightarrow ) \; \wedge \; 5 | x_k \Rightarrow 5|n [/m]
in Worten: Wenn 5 Teiler von n ist, dann ist auch 5 Teiler von [m]x_k[/m] und wenn 5 Teiler von [m]x_k[/m] ist, dann ist auch 5 Teiler von n.
Woher weiß ich, dass als Folgerung (siehe erste Implikation) [m]5|x_k[/m] wegen [m]x_k \in \{ 0, 5 \}[/m], sprich woraus wird dies ersichtlich?
Wird es so vorgelesen? Für [m]x_k[/m] kann man direkt die 0 und 5 einsetzen oder...? ... und es gleich unter "Zu zeigen" aufschreiben?
So, und das war´s... weiter weiß ich leider nicht... wie kann man da weitermachen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:05 So 09.03.2014 | | Autor: | leduart |
Hallo
was ist denn allgemein [mm] x_1x_2,,,x:k [/mm] mod 10? wenn du es als Summe schreibst? teile die Summe auf von 1 bis [mm] 10^{k-1} [/mm] und [mm] x_k*10^0
[/mm]
bis dann, lula
|
|
|
| |
|
Woher soll ich wissen, dass ich genau diese Formel benutzen muss?
[m]n = \summe_{n=1}^{k} x_k*10^{k-n}[/m] oder [m]n = x_nx_{n-1}...x_1x_0 = \summe_{i=0}^{n} x_i*10^i[/m]
Ich probiere es mal mit [m]x_nx_{n-1}...x_1x_0 = \summe_{i=0}^{n} x_i*10^i[/m]
[m]x_nx_{n-1}...x_1x_0 = \summe_{i=0}^{n} x_i*10^i = ... [/m]
[m]i = 0: 0*10^0 = 0 * 1 = 0[/m]
[m]i = 1: 1*10^1 = 1 * 10 = 10[/m]
[m]i = 2: 2*10^2 = 2 * 100 = 200[/m]
.... usw
Aber das ergibt doch alles 0 (mod 10) ?
Sorry, das ist doch Blödsinn, was ich da hingeschrieben habe?!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:21 So 09.03.2014 | | Autor: | leduart |
Hallo
ich verstehe nicht was du machst. warum verschiedene i ?warum bei i=2 etwa [mm] x_2=2 [/mm] oder bei i=0 [mm] x_0=0 [/mm] ?? die [mm] x_i [/mm] haben doch nichts mit i zutun, außer dass sie an der iten Stelle stehen.
[mm] \summe_{i=0}^{n}a_i*10^i=x_0+10*\summe_{i=1}^{n}x_i*10^{i-1}=x_0 [/mm] mod10
(dein letzter Satz stimmt.)
Gruß leduart
|
|
|
| |
|
Ich kann nicht erkennen, was Du geschrieben hast?
Kannst Du es auch nochmal erklären? Was habe ich falsch gemacht?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:23 Mo 10.03.2014 | | Autor: | leduart |
Hallo
tut mir sehr leid, jetzt sollte es lesbar sein.
gruß leduart
|
|
|
| |
|
Hallo zusammen.
Wenn ich also [m]n \in \IN[/m] mit [m]n=x_1 x_2 ... x_k[/m] wobei [m]x_i \in \{ 0...9 \}[/m] für [m]i=i...k[/m] ist und [m]5|n \Rightarrow x_k \in \{ 0, 5 \} [/m] und [m]x_k \in \{ 0, 5 \} \Rightarrow 5|n[/m] zu zeigen ist.
Kann man doch für [m]x_i[/m] mit [m]i=1[/m] oder [m]i=5[/m] einsetzen und erhält für n einmal [m]n=0[/m] und die [m]n=5[/m].
Dann gilt zum einen [m]5|5[/m] und [m]5|0[/m] und das sind beides wahre Aussagen, jedes [m]n \in \IN[/m] ist Teiler von 0 und jeder Zahl teilt sich selbst (Reflexivität?).
Freue mich über Feedback.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:33 Mo 08.09.2014 | | Autor: | Marcel |
Hallo,
> Hallo zusammen.
> Wenn ich also [m]n \in \IN[/m] mit [m]n=x_1 x_2 ... x_k[/m] wobei [m]x_i \in \{ 0...9 \}[/m]
es wäre sinnvoll, für $k > [mm] 1\,$ [/mm] auch [mm] $x_1 \not=0$ [/mm] zu fordern!
> für [m]i=i...k[/m] ist und [m]5|n \Rightarrow x_k \in \{ 0, 5 \}[/m] und
> [m]x_k \in \{ 0, 5 \} \Rightarrow 5|n[/m] zu zeigen ist.
??? (Edit: Die Fragezeichen haben sich erledigt, ich hatte den Sinn des
Satzes verloren, weil ich selbst ihn beim Zitieren zerstückelt habe. Also bis
hierhin kann ich Dir folgen!)
> Kann man doch für [m]x_i[/m] mit [m]i=1[/m] oder [m]i=5[/m] einsetzen und
> erhält für n einmal [m]n=0[/m] und die [m]n=5[/m].
Hier verstehe ich noch weniger, was Du mitzuteilen versuchst!
> Dann gilt zum einen [m]5|5[/m] und [m]5|0[/m] und das sind beides wahre
> Aussagen, jedes [m]n \in \IN[/m]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
ist Teiler von 0 und jeder Zahl
> teilt sich selbst (Reflexivität?).
Auch hier: Das wird gerade echt chaotisch. Die Aufgabe ist sehr leicht zu
lösen:
Es gilt
$n=\sum_{r=1}^k x_r*10^{k-r}\,,$
denn
$n=x_1*10^{k-1}+x_2*10^{k-2}+...+x_{k-1}*10+x_k*1\,.$
Nun ist
$10^s=2^s*5^s \equiv 2^s *0^s=0 \mod 5$ für alle $s \in \IN=\IN \setminus \{0\},$
daher
$n=x_1*10^{k-1}+x_2*10^{k-2}+...+x_{k-1}*10+x_k*1 \equiv 0+0+...+0+x_k=x_k \mod 5\,$ (Begründung?)
also ist obige Kongruenz gleichwertig mit
$(\*)$ $n \equiv x_k \mod 5\,.$
Zeige jetzt mit ($\*$): Für $x_k \in \{0,...,9\}$ gilt
$5\,|\,n$
$\Rightarrow$ $x_k \in \{0,5\}\,.$
Zeige danach mit ($\*$):
$x_k \in \{0,5\}$
$\Rightarrow$ $5\,|\,n\,.$
Nebenbei: Das Ganze kann man auch ohne Modulo-Rechnung machen.
Wieder
$n=\sum_{r=1}^k x_r*10^{k-r}\,.$
Offenbar gilt
$n=x_k+\sum_{r=1}^{k-1} x_r*10^{k-r}\,,$
und
$\sum_{r=1}^{k-1} x_r*10^{k-r}=10*\sum_{r=1}^{k-1}x_r*10^{k-(r+1)}=10*\underbrace{\sum_{s=2}^{k}x_{s-1}*10^{k-s}}_{\in \IN}=5*\red{\underbrace{2*\sum_{s=2}^{k}x_{s-1}*10^{k-s}}_{=:\sigma\in \IN_0}}}\,.$
Wenn nun
$n=x_1+5*\sigma$
mit $\sigma \in \IN_0$ ist, dann gilt $5\,|\,n$ genau dann, wenn $5\,|\,x_1\,.$ Welche
Zahlen kann man also für $x_1 \in \{0,1,2,3,4,5,6,7,8,9\}$ nur noch einsetzen, wenn
man $5\,|\,n$ haben will - und für welche dieser Zahlen gilt $5\,\not|\,n$?
Gruß,
Marcel
|
|
|
|
