Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Binäre Darstellung entählt min 7 "1"

Binäre Darstellung entählt min 7 "1"

Universität / Fachhochschule

Sonstiges

Tags: binär, Binärsystem, Darstellung, Sonstig

mariem aktiv_icon

12:40 Uhr, 14.09.2021

Hallo,

Ich will zeigen dass alle positive ganze Zahlen die ein Vielfaches von 7 sind, haben mindestens 3 Ziffern “1” in deren binären Darstellung.

Eine Zahl, Vielfaches von 7 ist in der Form

7 k = (6 + 1) k = 6 k + k = 2 \cdot 3 \cdot k + k

.
Um die binäre Darstellung zu bekommen wenden wir die Euklidische Division an. Die Reste der Divisionen bilden die Darstellung.

Muss man also Fallunterscheidung machen, ob

k

gerade oder ungerade ist?

HAL9000

14:49 Uhr, 14.09.2021

Kennst du Modulorechnung? Die Potenzen

2^{n}

besitzen modulo 7 für

n = 0, 1, 2

die Reste 1,2 oder 4, für größere

n

wiederholt sich das ganze wegen

2^{n} = 2^{3} \cdot 2^{n - 3} = 7 \cdot 2^{n - 3} + 2^{n - 3}

dann periodisch.

Summiert man nur zwei dieser Reste, bekommt man damit niemals

2^{n} + 2^{m} \equiv 0 mod 7

hin.

mariem aktiv_icon

00:28 Uhr, 15.09.2021

Warum gucken wir die Potenzen

2^{n}

modulo 7 ?

Wir nehmen die gegebene Zahl,die ein Vielfaches von 7 ist, also in der Form

x = 7 k

.
Dann bildet der Rest der Division von

x

und

2^{i}

die binäre Darstellung, oder? Muss man dann nicht modulo

2^{i}

betrachten statt modulo 7 ?

Kartoffelchipsman aktiv_icon

02:55 Uhr, 15.09.2021

Sei

0 \neq p := \sum_{k = 0}^{n} a_{k} \cdot 2^{k}

mit

a_{k} \in {0,1} \forall 0 \leq k \leq n

und

n \geq 2

7 | p \Leftrightarrow 0 = (\sum_{k = 0}^{n} a_{k} \cdot 2^{k}) mod 7

= (\sum_{k = 0}^{n} ((a_{k} \cdot 2^{k}) mod 7)) mod 7

= (\sum_{k = 0}^{n} a_{k} \cdot 2^{(k mod 3)}) mod 7

(hat HAL oben erklärt)

= (s \cdot 1 + t \cdot 2 + u \cdot 4) mod 7

mit

s := | {0 \leq k \leq n : k mod 3 = 0, a_{k} = 1} |,

t := | {0 \leq k \leq n : k mod 3 = 1, a_{k} = 1} |,

u := | {0 \leq k \leq n : k mod 3 = 2, a_{k} = 1} |

(und

s + t + u \geq 3)

\Rightarrow \exists k_{1}, k_{2}, k_{3} \in N : 0 \leq k_{1} < k_{2} < k_{3} \leq n, a_{k_{1}} = a_{k_{2}} = a_{k_{3}} = 1

HAL9000

07:05 Uhr, 15.09.2021

> Warum gucken wir die Potenzen

2^{n}

modulo 7 ?

Viele Gedanken hast du dir aber noch nicht über Binärdarstellungen gemacht, oder?

Eine Binärdarstellung mit GENAU einer Einsziffer entspricht einer Zweierpotenz

2^{n}

.

Eine Binärdarstellung mit GENAU zwei Einsziffern entspricht

2^{n} + 2^{m}

mit

n \neq m

.

Wenn man also zeigt, dass weder

2^{n}

(trivial) noch

2^{n} + 2^{m}

jemals durch 7 teilbar sein kann, ist man fertig: Denn da in diesen beiden Kategorien keine durch 7 teilbaren Zahlen zu finden sind, müssen alle durch 7 teilbaren positiven ganzen Zahlen MINDESTENS drei Einsziffern aufweisen - einfache Logik!

Man kann die Idee noch so variieren: Sei

n < m

, dann ist in

2^{n} + 2^{m} = 2^{n} \cdot (1 + 2^{m - n})

der Faktor

2^{n}

ja gewiss nicht durch 7 teilbar, es muss also nur noch geprüft werden, ob

1 + 2^{r}

(mit

r = m - n

) durch 7 teilbar sein kann - was nicht der Fall ist, weil

1 + 2^{r}

modulo 7 nur die Reste 2,3,5 haben kann.

Kartoffelchipsman aktiv_icon

22:08 Uhr, 15.09.2021

Das sei auch noch kurz formal geklärt:

(I V) 2^{k} mod 7 = 2^{(k mod 3)} \forall k \in N

(I A) k = 0 : 2^{0} mod 7 = 1 = 2^{(0 mod 3)}

(I S) (2^{k + 1}) mod 7 = (2 \cdot 2^{k}) mod 7 = (2 \cdot (2^{k} mod 7)) mod 7

= (2 \cdot 2^{(k mod 3)}) mod 7 = (2^{((k + 1) mod 3)}) mod 7 = 2^{((k + 1) mod 3)}

mariem aktiv_icon

07:26 Uhr, 16.09.2021

Danke für eure Hilfe!! Habe das jetzt verstanden!! :-)

1541626

1541547

	Status: nicht eingeloggt	Noch nicht registriert?