[Zahlentheorie] Teilbarkeit durch sieben

24/06/2009 - 19:16 von Markus Wichmann | Report spam
Hi all,

ich hatte da neulich ein "Problem", denn solange, dass es zu einem
ausgewachsen wàre, hat es nicht gedauert. Ich hatte einen seltsamen
Zàhler gegeben, der drei Tasten hat: Mit der ersten kann man den Zàhler
auf 0 zurücksetzen, mit der zweiten die momentane Zahl mit 10
multiplizieren und mit der dritten Taste mit 7 addieren. Die Anzeige hat
vier Stellen, d.h. es wird modulo 10000 gerechnet. Ich habe jetzt nach
einem Algorithmus gesucht, um eine beliebige Zahl in diesen Zàhler
einzutippen. Und auch schon gefunden: Ist die Zahl _nicht_ durch 7
teilbar, dann addiert man einfach solange 10000 zu ihr dazu, bis sie es
ist. Anschließend dividiert man durch sieben. Bei der entstehenden Zahl
fàngt man vorne an, drückt so oft auf den "+7"-Knopf, wie da steht,
anschließend einmal auf den "x10"-Knopf und geht so durch die Zahl
durch.

Nun hat die Sache einen Haken: Kann man zu einer beliebigen
vierstelligen Zahl einfach sooft 10000 dazu addieren, bis sie durch
sieben teilbar ist? Formal (die Behauptung):

∀ x ∊ N: x < 10000 -> ∃ m,n ∊ N ⋃ {0}: x + n*10000 = m*7

OK, dachte ich zunàchst, es ist ein Beweis über eine endliche Teilmenge
der natürlichen Zahlen, also kannst du es mit Induktion versuchen. Nur
blieb ich am Induktionsschritt hàngen:

Induktionsanfang:
x = 1
n = 5
m = 7143

(um zu dem Zàhler zurückzukommen: Wenn man jetzt

- 7-mal "+7"
- 1-mal "x10"
- 1-mal "+7"
- 1-mal "x10"
- 4-mal "+7"
- 1-mal "x10"
- 3-mal "+7"

drückt, dann steht "0001" auf dem Display. Wieso? Guckt euch m und dann
die Zahlenfolge der Tastendrücke an!)

Das Problem ist der Induktionsschritt. Die Behauptung gelte für x:
∃ m,n ∊ N ⋃ {0}: x + n*10000 = m*7 <-> x = 7m - 10000n

Dann gilt für x+1:
(x+1) + 10000p = 7q?

x einsetzen:
7m - 10000n + 1 + 10000p = 7q
10000(p - n) + 1 = 7(q - m)

Letzteres ist ja die Gleichung für x = 1. Dann wàre ja

p - n = 5
q - m = 7143

Öhm... tja, aber: für x = 2 gilt:
p = 3
q = 4286

p - n = 3 - 5 = -2 ≠ 5
q - m = 4286 - 7143 = -2857 ≠ 7143

Hrmpf... nun ist mir aufgefallen, dass die letzte Ungleichung zu einer
Gleichung wird, wenn man ein "mod 10000", bzw. ein "mod 7". Aber so
nicht.

Hat einer eine Idee? Denn letztlich habe ich den Computer bemüht, der
meinen Verdacht bestàtigte. Nur muss es doch irgendwie auch ohne Brute
Force gehen, oder?

Tschö,
Markus
GUI - ein Hintergrundbild und zwölf XTerms

vim -c "exec \"norm iwHFG#NABGURE#IVZ#UNPXRE\"|%s/#/ /g|norm g??g~~"
 

Lesen sie die antworten

#1 Jakob Creutzig
24/06/2009 - 20:14 | Warnen spam
Markus Wichmann writes:

Nun hat die Sache einen Haken: Kann man zu einer beliebigen
vierstelligen Zahl einfach sooft 10000 dazu addieren, bis sie durch
sieben teilbar ist?



Ja. Am leichtesten tut man sich meist, wenn man modulo-Rechnungen
in der enstprechenden Gruppe betrachtet. Hier hat man Z|7Z,
man startet mit einem Element x und addiert immer wieder 3
genauer die Restklasse von 3) hinzu. Man muss sich also irgendwann
wiederholen; wenn k und n gegeben sind mit x + 3n = x + 3k mod 7,
dann folgt aber sofort 7|3(n-k), und also 7|(n-k). Man wiederholt
sich also fruehestens nach 7 Schritten, d.h. es gibt mindestens
7 verschiedene Elemente in den Restklassen {x + 3*n : n \in |N}.
Es gibt aber nur 7 Elemente in Z|7Z, also kommen alle Restklassen
vor, insbesondere die Nullrestklasse. Und das heisst, es gibt ein
m (sogar ein m <= 6) mit x + 3*m = 0 mod 7.

[Das Ganze kann man auch ganz fein algebraisch machen:
{x + 3*n: n \in |N} = x + 3Z|7Z; 3Z|7Z ist Faktor eines Ideals, also
ein (nichttriviales) Ideal, aber Z|7Z ist Koerper, hat also
nur {0} und Z|7Z als Ideale. Damit ist 3Z|7Z = Z|7Z, und
{x + 3*n : n \in |N} = x + Z|7Z = Z|7Z.]

Ähnliche fragen