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 Schulmathe
  Status Primarstufe
  Status Mathe Klassen 5-7
  Status Mathe Klassen 8-10
  Status Oberstufenmathe
    Status Schul-Analysis
    Status Lin. Algebra/Vektor
    Status Stochastik
    Status Abivorbereitung
  Status Mathe-Wettbewerbe
    Status Bundeswettb. Mathe
    Status Deutsche MO
    Status Internationale MO
    Status MO andere Länder
    Status Känguru
  Status Sonstiges

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
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenMathe Klassen 5-71-stellige Quersumme berechnen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Mathe Klassen 5-7" - 1-stellige Quersumme berechnen
1-stellige Quersumme berechnen < Klassen 5-7 < Schule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Mathe Klassen 5-7"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

1-stellige Quersumme berechnen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:28 Sa 25.08.2018
Autor: donp

Aufgabe
Für $n [mm] \in \IN^{+}$ [/mm] sei $q(n)$ die 1-stellige Quersumme von n zur Basis b.

Beweisen Sie:
[mm] $$q(n)=\begin{cases} b-1, & \mbox{für } n \equiv 0 \;(mod\; (b-1)) \\ n \;mod\; (b-1), & \mbox{sonst} \end{cases}$$ [/mm]



Hintergrund:
Es sollen z.B. 9 auf einem geschlossenen Band angeornete Elemente schrittweise vor einem Fenster vorbeiziehen, wobei immer nur eines im Fenster sichtbar ist. Bei n Schritten interessiert nur, welches Element schließlich im Fenster erscheint. Für große n ist es nicht effizient, alle Schritte tatsächlich auszuführen. Für z.B. n=9 muss gar kein Schritt ausgeführt werden, oder eben 9 Schritte.

Anscheinend entspricht die Anzahl auszuführender Schritte der 1-stelligen Quersumme von n, z.B. im Dezimalsystem für $n=12345 [mm] \Rightarrow [/mm] q(12345)=q(15)=q(1+5)=6$. Nun würde ich das gerne auch richtig beweisen.


Es ist klar, dass $$1 [mm] \,\le\, [/mm] q(n) [mm] \,<\, [/mm] b$$ gilt, im Dezimalsystem mit [m]b=10[/m] z.B. ist [m]q(n)[/m] eine der Zahlen $1 [mm] \dots [/mm] 9$.

Mir ist intuitiv auch klar, dass b-1 bzgl. der 1-stelligen Quersumme sozusagen das neutrale Element der Addition ist, weil im Dezimalsystem z.b [m]q(27)=q(18+9)=q(18-9)=9[/m] gilt.
Aber wie zeigt man das am besten?


Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

Danke und Gruß,
Don P

        
Bezug
1-stellige Quersumme berechnen: Tipp
Status: (Antwort) fertig Status 
Datum: 10:55 So 26.08.2018
Autor: HJKweseleit

Vielleicht hilft dieser Tipp ( dabei steht [mm] \equiv [/mm] für ... ist gleich ... mod (b-1)):

Für k [mm] \ge [/mm] 1 gilt:

[mm] a*b^k \equiv a*b^k [/mm] - [mm] a*b^{k-1}+a*b^{k-1} \equiv (b-1)a*b^{k-1}+a*b^{k-1} \equiv a*b^{k-1} [/mm] und somit

[mm] a*b^k \equiv a*b^{k-1} \equiv a*b^{k-2} \eqiv [/mm] ...  [mm] \equiv a*b^0 [/mm] = a

Falls du damit nicht klar kommst, melde dich noch mal.


Bezug
                
Bezug
1-stellige Quersumme berechnen: Inzwischen klar
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 19:09 Di 28.08.2018
Autor: donp


> Für k [mm]\ge[/mm] 1 gilt:
>  
> [mm]a*b^k \;\equiv\; a*b^k[/mm] - [mm]a*b^{k-1}+a*b^{k-1}[/mm]

Gut, beide Seiten sind gleich und somit kongruent bzgl. jedes Moduls [mm]m[/mm].

Und wegen [m](a*b^k - a*b^{k-1})=b*(a*b^{k-1})-1*(a*b^{k-1})= (b-1)*a*b^{k-1}[/m] sind wieder beide Seiten gleich und daher kongruent:
[mm] $$a*b^k \equiv (b-1)*a*b^{k-1}+a*b^{k-1}$$ [/mm] Den nächsten Schritt zu [mm] $$(b-1)*a*b^{k-1}+a*b^{k-1}\equiv a*b^{k-1}$$ [/mm] verstehe ich aber nicht auf Anhieb inzwischen auch [lichtaufgegangen]:

Setzen wir $$l = [mm] a*b^{k-1}$$ [/mm] $$m=(b-1)$$ dann hat [m]a*b^{k-1} + (b-1)*a*b^{k-1}[/m] die Form [m]l + m*l[/m], was die Kongruenz von [m]l[/m] bzgl. des Moduls [m]m[/m] zeigt.

Der Rest wäre dann auch klar:

> und somit [mm]a*b^k \equiv a*b^{k-1} \equiv a*b^{k-2} \eqiv \dots \equiv a*b^0 = a[/mm]

Somit hat sich diese Frage erledigt. Anscheinend kann ich sie nicht selber auf beantwortet setzen [keineahnung].

Vielen Dank für den Tipp,
Don P


Mein ursprünglicher Beweis geht so:

Es seien [mm](a,b,n) \in \IN_{+}^3[/mm] und [m]Q(n)[/m] die normale Quersumme von [m]n[/m] zur Basis [m]b[/m].

Mit [m]m=b-1[/m] sind die Zahlen $a [mm] \in \{1...m\}$ [/mm] Repräsentanten der Restklassen $a + m [mm] \mathbb{N}$ [/mm] (Äquivalenzklassen von a bezüglich der Kongruenz modulo m).

Definition der Restklasse $a + m [mm] \mathbb{Z}$ [/mm] nach Wikipedia: Sie besteht aus allen ganzen Zahlen c, die sich aus a durch die Addition ganzzahliger Vielfacher von m ergeben:
$$a + m [mm] \mathbb{Z} [/mm] = [mm] \{ c\mid c=a+km\ \, \mathrm{f\ddot ur\ ein}\ \, k\in\mathbb Z\} [/mm] = [mm] \{ c \mid c \equiv a \; ({\rm mod} \; m) \}$$ [/mm] Als Definition muss die Aussage wohl nicht extra bewiesen werden.

Denkt man sich die Repräsentanten $a [mm] \in \{1...m\}$ [/mm] kreisförmig angeordnet und den ganzen Zahlenstrang [mm] \IN^{+} [/mm] entsprechend spiralförmig, dann liegen konkruente Zahlen [m]\{ c \mid c \equiv_{m} a\}[/m] immer an Position [m]a[/m] im Kreis, für [m]m=9[/m] z.B. $$c=1 = 1 + 0*m [mm] \mbox [/mm] { an Position } a=1=Q(1) [mm] \;\dots$$ [/mm] $$c=9 = 9+0*m [mm] \mbox [/mm] { an Position } a=9=Q(9) [mm] \;\dots$$ [/mm] $$c=10 = 1+1*m [mm] \mbox [/mm] { an Position } a=1=Q(10) [mm] \;\dots$$ [/mm] $$c=18=9+1*m [mm] \mbox [/mm] { an Position } [mm] a=9=Q(18)\;\dots$$ [/mm] $$c=19=1+2*m [mm] \mbox [/mm] { an Position } a=1=Q(10)=Q(Q(19))$$ usw. Hier haben wir genau die für die Definition der Restklassen [m]a + m \mathbb{N}[/m] benutzte Addition ganzzahliger Vielfacher von [m]m[/m].

Aus dieser Anschauung ergibt sich $$n [mm] \equiv_{m} [/mm] a [mm] \equiv_{m} [/mm] Q(n) [mm] \Rightarrow [/mm] a [mm] \equiv_{m} [/mm] Q(Q(n)) [mm] \equiv_{m} [/mm] Q(Q(Q(n))) [mm] \;\dots \;\equiv_{m} [/mm] q(n)$$ und wegen [mm]1\le q(n)\le m[/mm] folgt für die 1-stellige Quersumme $$q(n) = a$$ w.z.b.w.

Das scheint mir zwar logisch, aber weil ich die ungewöhnliche Vorstellung des Zahlenstrangs als Spirale mit Umfang [m]m[/m] benötige, ist der Beweis wohl umständlich und nicht besonders mathematisch geführt. Das müsste doch besser gehen.

Bezug
                        
Bezug
1-stellige Quersumme berechnen: Frage geklärt
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 08:18 Mi 29.08.2018
Autor: donp

Leider Kann ich meine Frage hier nicht selber beantworten. Sie hat sich aber geklärt:

> Den nächsten Schritt zu [mm](b-1)*a*b^{k-1}+a*b^{k-1}\equiv a*b^{k-1}[/mm] verstehe ich aber nicht auf Anhieb.

Inzwischen schon [lichtaufgegangen]:

Setzen wir $$l = [mm] a*b^{k-1}$$ [/mm] $$m=(b-1)$$ dann hat [m]a*b^{k-1} + (b-1)*a*b^{k-1}[/m] die Form [m]l + m*l[/m], was die Kongruenz von [m]l[/m] bzgl. des Moduls [m]m[/m] zeigt.

Denn die Definition der Restklasse [m]a + m \mathbb{Z}[/m] ist ja: $$a + m [mm] \mathbb{Z} [/mm] = [mm] \{ c\mid c=a+km\ \, \mathrm{f\ddot ur\ ein}\ \, k\in\mathbb Z\} [/mm] = [mm] \{ c \mid c \equiv a \; ({\rm mod} \; m) \}$$ [/mm]
Vielen Dank für den Tipp,
Don P


Bezug
        
Bezug
1-stellige Quersumme berechnen: Stimmt's so?
Status: (Frage) beantwortet Status 
Datum: 23:09 Do 30.08.2018
Autor: donp

Aufgabe
Für $n [mm] \in \IN^{+}$ [/mm] sei $q(n)$ die 1-stellige Quersumme von n zur Basis b.

Beweisen Sie:
[mm] $$q(n)=\begin{cases} b-1, & \mbox{für } n \equiv 0 \;(mod\; (b-1)) \\ n \;mod\; (b-1), & \mbox{sonst} \end{cases}$$ [/mm]





Im Folgenden sei der Modul [m]m=b-1[/m] und [m]k \in \IN[/m].

Für eine natürliche Zahl [m]n[/m], dargestellt durch Ziffern in der Form [m]\mathbf{a}_k \ldots \mathbf{a}_2 \mathbf{a}_1 \mathbf{a}_0[/m], ist die Quersumme die Summe der Ziffernwerte [m]\mathbf{a}_i[/m] $$Q(n) = [mm] \sum_{i=0}^k a_i [/mm] = [mm] a_0 [/mm] + [mm] a_1 [/mm] + [mm] a_2 [/mm] + [mm] \dotsb [/mm] + [mm] a_k$$ [/mm] und es gilt [mm] $$n=\sum_{i=0}^k a_i \cdot b^i [/mm] = [mm] a_0 \cdot b^0 [/mm] + [mm] a_1 \cdot b^1 [/mm] + [mm] a_2 \cdot b^2 [/mm] + [mm] \dotsb [/mm] + [mm] a_k \cdot b^k$$ [/mm] Nach den Rechenregeln für Konguenzen gilt [mm] $$\text{(1)}\ [/mm] \ [mm] (a_1+a_2) \equiv_m (a_1\ [/mm] {mod}\ [mm] m+a_2\ [/mm] {mod}\ m)$$ und der Tipp von HJKweseleit zeigt [mm] $$\text{(2)}\ [/mm] \ a [mm] \equiv_m a*b^k$$ [/mm] Aus (1) und (2) folgt $$n [mm] \equiv_m [/mm] Q(n)$$ Falls [m]Q(n)[/m] mehr als eine Ziffer hat, gilt entsprechend [m]n \equiv_m Q(Q(n))[/m] usw. und für die 1-stellige Quersumme [m]Q_1(n)[/m] somit ebenfalls $$n [mm] \equiv_m Q_1(n)$$ [/mm] Für [m]n>0[/m] ist [m]1\le \,Q_1(n)\,\le m[/m] und mit [m]Q_1(n) \equiv_m 0 \equiv_m m[/m] ist [m]Z = \{1,2,\dots,m\}[/m] dann die Zielmenge. Daraus folgt für die 1-stellige Quersumme
[mm] $$q(n)=\begin{cases} m, & \mbox{für } n \equiv 0 \;(mod\; m) \\ n \;mod\; m, & \mbox{sonst} \end{cases}$$ [/mm] w.z.b.w.

Die Rechenregel (1) habe ich nicht bewiesen, was man streng genommen auch noch tun müsste.

Bin mir zwar ziemlich sicher, dass es so stimmt, würde mich trotzdem freuen, wenn es mir ein Mathematiker noch kurz bestätigen könnte.

Danke und Gruß,
Don P

Bezug
                
Bezug
1-stellige Quersumme berechnen: Antwort
Status: (Antwort) fertig Status 
Datum: 15:22 Fr 31.08.2018
Autor: HJKweseleit

Ja, das ist so richtig und auch sehr schön, kompakt und verständlich zusammengestellt.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Mathe Klassen 5-7"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


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