Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Teilbarkeit durch 7

Teilbarkeit durch 7

Universität / Fachhochschule

Folgen und Reihen

Tags: Folgen, Reihen

spectre210 aktiv_icon

14:47 Uhr, 12.12.2010

geg. sei eine Folge

b_{n} (n) = {1, 3, 2, - 1, - 3, - 2, 1, 3, 2, - 1, - 3, - 2, . . .}

und eine beliebige Zahl.
Die gewichtete Quersumme berechnet man, indem man angefangen von der letzten Ziffer der Zahl x bis zur ersten Ziffer mit dem ersten Glied der Folge b_n bis zum letzten Glied multipliziert und addiert.
Also x sei

12345

.
So rechnet man

b (0) \cdot 5 + b (1) \cdot 4 + b (2) \cdot 3 + b (3) \cdot 2 + b (4) \cdot 1 = 1 \cdot 5 + 3 \cdot 4 + 2 \cdot 3 - 1 \cdot 2 - 3 \cdot 1 = 18

Man soll induktiv zeigen, dass diese gewichtete Methode eine Teilbarkeitsregel für die Zahl 7 liefert.
Habe mich auch schon unter wiki informiert, jedoch weiß ich immer noch nicht daraus wie man das beweist.
Mein Ansatz:
I.A.:
gilt für

n = 0

;
d.h. Zahl hat nur eine Ziffer und

b (0) = 1

, so ist die gewichtete Quersumme die Zahl selber und die gew. Quersumme ist durch

7

teilbar, wenn nur die Ziffer

7

da steht:

7 \cdot 1 = 7

Somit ist diese Zahl durch 7 teilbar.

□

(Ist ja eindeutig).
Jetzt komme ich nicht weiter:
I.V.:
Eine Zahl ist mit

n = n

Ziffern teilbar.
I.S.:
So ist auch eine Zahl mit

n = n + 1

Ziffern durch Sieben teilbar????
Wie gehe ich hier vor?
Vielen Dank im Vorraus.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

michaL aktiv_icon

15:28 Uhr, 12.12.2010

Hallo,

schön, dazu mal eine Aufagbe zu lesen. Darf ich fragen, was du studierst? Info: mit der gewichteten Quersumme habe ich vor ein paar Tagen meine 5.-Klässler genervt (auf einer anderen Ebene).

Zum Beweis: Diese gewichtete Quersumme berechnet sozusagen von jeder Stelle einer Zahl im Stellenwertsystem den Rest modulo 7 (in diesem Fall).
Der Beweis beschränkt sich darauf, diese Reste herauszufinden. Ich mache das mal an einem Beispiel, etwa der Zahl

3 5 7 8 9 2 (also Dreihundertsiebenundfünfzigtausendachthundertzweiundneunzig).

Die Zahl hat zwei Einer (E), neun Zehner (Z), acht Hunderter (H), sieben Tausender (T), fünf Zehntausender (Zt) und 3 Hunderttausender (Ht).

Zunächst berechnet man die Reste all dieser Stellen (also für einen(!) E, einen Z, einen T usw.) modulo 7.
Das kannst du mal selber machen, es ergeben sich (nicht von ungefähr) die Zahlen:

Ht Zt T H Z E
-2 -3 -1 2 3 1

Klar, denn die nächste, durch 7 teilbare Zahl bei 1 (E) ist 0, also Rest 1. Bei 10 ist es 7, also Rest 3, bei 100 (H) ist es 98 also Rest 2, bei 1000 (T) ist es 1001, also Rest -1 usw.

Nun zurück zum Beispiel (3 5 7 8 9 2): Man denkt sich, dass ein (!) Einer den Rest 1 lässt, also lassen zwei davon den Rest 2. Ein Zehner lässt den Rest 3, also lassen neun davon den Rest 9*3=27. Klar, wie die "Gewichtung" dabei eine Rolle spielt?
Nun würde man also folgendes Schema ausrechnen:
Ht Zt T H Z E

3 5 7 8 9 2

-2-3 -1 2 3 1
----------------
-6-15-7+16+27+2=17
d.h. die Zahl ist NICHT durch 7 teilbar, weil sie den Rest 3 modulo 7 lässt.

Nun zum Beweis der Zahlen: Von einer Zehnerpotenz zur nächsten kommt man durch das Multiplizieren mit 10, d.h. es gilt

1 0^{n + 1} = 10 \cdot 1 0^{n}

. Du wirst feststellen, dass

1 0^{6} \equiv 1

mod 7 gilt, d.h. für die Folgeglieder

b_{n}

gilt:

b_{n} = min {k \in {- 3, - 2, - 1, 0, 1, 2, 3} ∣ 7 ∣ (1 0^{n} - k)}

So eine Formel musst du dir verschaffen (ich bin mit der angegebenen nicht so zufrieden) und dann induktiv beweisen.
Vielleicht gehst du so vor, dass du beweist, dass

1 0^{n} - b_{n}

stets durch 7 teilbar ist (das sollte reichen). Anschließend zerlegst du deine Zahl

\sum a_{k} \cdot 1 0^{k}

(\sum a_{k} \cdot (1 0^{k} - b_{k})) + \sum a_{k} b_{k}

.

Noch Fragen?

Mfg Michael

PS: Sorry, ein bisschen wirr. Wurde erst hochschulniveau während des Schreibens.

spectre210 aktiv_icon

17:54 Uhr, 12.12.2010

Vielen Dank für deine Antwort.
Ich studiere Informatik.
Ich habe noch ein paar Fragen.
1.) Warum legt man bei

1000 % 7

oder auch

1000 m o d 7 = - 1

fest und nicht Rest

6

.
2.) Du hast eine Menge angegeben:

b_{n} = m i n {k \in {- 3, - 2, - 1, 0, 1, 2, 3} ∣ 7 ∣ (1 0^{n} - k)}

Wobei sicherlich

7 ∣ (1 0^{n} - k)

die Bedingung ist und

k \in {- 3, - 2, - 1, 0, 1, 2, 3}

die Funktion.
Oder hab ich das falsch verstanden?
Denn ich weiß nicht, warum du das

m i n

verwendest.
Vielleicht übersehe ich was und du könntest mir ein Gegenbeispiel zeigen.
3.)
Mein Induktion wäre jetzt:
I.A.:
Gilt für Zahl mit

n = 1

Ziffern:
Diese Ziffer steht an

1 0^{0}

Stelle im Zehnersystem und hinterlässt bei

1 m o d 7

den Rest

1

. Die gewichtete Quersumme wäre dann durch 7 teilbar, wenn sie siebenmal oder 0 mal den Rest hinterlässt.

7 ∣ 7 \cdot 1

7 ∣ 0 \cdot 1 □

I.V.:
Gilt für Zahl mit

n = n

Ziffern.
I.S.:
Nach Induktionsvoraussetzung gilt, dass die Zahl mit n Ziffern durch 7 teilbar ist.
Dass heißt, dass als gewichtete Quersumme der Rest:

k * 7 k \in N_{0}

auftritt.
Die Zahl ist mit

n = n + 1

Ziffern genau dann durch 7 teilbar, wenn durch ihre ihre Erweiterung um eine Ziffer wieder ein Rest mit

k * 7 k \in N_{0}

entsteht.
Somit entsteht durch die Quersumme:

k \cdot 7 + k \cdot 7 = 2 k \cdot 7 k \in N_{0}

welche wieder nach Induktionsvoraussetzung durch

7

teilbar ist.
Ist das so richtig?

michaL aktiv_icon

18:12 Uhr, 12.12.2010

Hallo,

zu deinen Fragen:
1.) Geschmackssache, im Sinne von: ginge auch mit Rest 6. Der Vorteil:

∣ - 1 ∣ < ∣ 6 ∣

, d.h. das Multiplizieren ist einfacher. Außerdem fällt dir so sicher die "Symmetrie" auf, gell?

2.) Würde ich nicht festlegen, dass

b_{n} \in {- 3, - 2, - 1, 0, 1, 2, 3}

liegt, dann wären auch andere "Reste" denkbar, etwa dein Rest 6 in Frage 1.). An der Stelle war ich aber selber mit meiner Formulierung nicht zufrieden.

3.) Ich würde, wie gesagt, zunächst feststellen, dass

1 0^{6} \equiv 1

mod 7 gilt. Danach kannst du beweisen, dass

1 0^{n} - b_{n}

durch 7 teilbar ist. Eigentlich musst du das nämlich explizit nur für 6 Zahlen (

1 0^{0}, 1 0^{1}, \dots, 1 0^{5}

) machen, da sich die "Sache" ab

1 0^{6}

wiederholt. Soll heißen, dein Induktionsanfang besteht darin, für

n \in {0, 1, 2, 3, 4, 5}

zu zeigen (explizit), dass

7 ∣ (1 0^{n} - b_{n})

gilt.
Der Induktionsschritt reduziert sich wegen

1 0^{6} \equiv 1

mod 7 auf

n \to n + 6

und nicht

n \to n + 1

. Das ist der Clou.

Wenn du diese Induktion hast, verwendest du die einfache Identität:

\sum a_{k} \cdot 1 0^{k} = (\sum a_{k} \cdot (1 0^{k} - b_{k})) + \sum a_{k} b_{k}

. Links ist du auf Teilbarkeit zu untersuchende Zahl

z

, der erste Summand rechts ist stets durch 7 teilbar (nach Induktion) und der zweite ist die gewichtete Quersumme.
Klar, dass dann gilt:

7 ∣ z \overset{}{\Leftrightarrow} 7 ∣

gewichtete Quersumme, gell?

Mfg Michael

spectre210 aktiv_icon

19:01 Uhr, 12.12.2010

Ok.
Was mir noch ein bisschen unklar ist:

\sum_{K = 0}^{n} a_{k} \cdot 1 0^{k} = \sum_{k = 0}^{n} a_{k} \cdot (1 0^{k} - b_{k}) + \sum_{k = 0}^{n} a_{k} b_{k}

Was ich daraus erkenne ist, dass du Ziffernweise summierst.
Warum ist der erste Summand immer durch sieben teilbar?
Oder meinst du damit die Induktionsvoraussetzung, wo wir festgelegt haben dass die Zahl für n=n Ziffern durch sieben teilbar ist?
Der zweite Summand soll die gewichtete Summe sein. Aber ist denn nicht die gewichtete Quersumme die Summe aus Summand eins und zwei.
Ist hier Summand 1:

\sum_{k = 0}^{n} a_{k} b_{k}

Und Summand2:

a_{n + 1} b_{n + 1}

?
Danke für deine Geduld.

spectre210 aktiv_icon

16:06 Uhr, 19.12.2010

Vielen Dank michaL,
Ich habe es nun verstanden.

834670

832114

	Status: nicht eingeloggt	Noch nicht registriert?