Partner von azubiworld.com - Logo
 
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

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
mariem

mariem aktiv_icon

12:40 Uhr, 14.09.2021

Antworten
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 7k=(6+1)k=6k+k=23k+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?

Antwort
HAL9000

HAL9000 aktiv_icon

14:49 Uhr, 14.09.2021

Antworten
Kennst du Modulorechnung? Die Potenzen 2n 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 2n=232n-3=72n-3+2n-3 dann periodisch.

Summiert man nur zwei dieser Reste, bekommt man damit niemals 2n+2m0 mod 7 hin.
mariem

mariem aktiv_icon

00:28 Uhr, 15.09.2021

Antworten
Warum gucken wir die Potenzen 2n modulo 7 ?

Wir nehmen die gegebene Zahl,die ein Vielfaches von 7 ist, also in der Form x=7k.
Dann bildet der Rest der Division von x und 2i die binäre Darstellung, oder? Muss man dann nicht modulo 2i betrachten statt modulo 7 ?
Antwort
Ernst Hubert Wilfred

Ernst Hubert Wilfred aktiv_icon

02:55 Uhr, 15.09.2021

Antworten
Sei 0p:=k=0nak2k   mit ak{0,1}    0kn und n2.

7|p0=(k=0nak2k)mod7

=(k=0n((ak2k)mod7))mod7

=(k=0nak2(k  mod  3))mod7   (hat HAL oben erklärt)

=(s1+t2+u4)mod7   mit
s:=|{0kn:kmod3=0,ak=1}|,
t:=|{0kn:kmod3=1,ak=1}|,
u:=|{0kn:kmod3=2,ak=1}|
(und s+t+u3)

  k1,k2,k3N:0k1<k2<k3n,ak1=ak2=ak3=1.

Antwort
HAL9000

HAL9000 aktiv_icon

07:05 Uhr, 15.09.2021

Antworten
> Warum gucken wir die Potenzen 2n 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 2n.

Eine Binärdarstellung mit GENAU zwei Einsziffern entspricht 2n+2m mit nm.

Wenn man also zeigt, dass weder 2n (trivial) noch 2n+2m 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 2n+2m=2n(1+2m-n) der Faktor 2n ja gewiss nicht durch 7 teilbar, es muss also nur noch geprüft werden, ob 1+2r (mit r=m-n) durch 7 teilbar sein kann - was nicht der Fall ist, weil 1+2r modulo 7 nur die Reste 2,3,5 haben kann.
Antwort
Ernst Hubert Wilfred

Ernst Hubert Wilfred aktiv_icon

22:08 Uhr, 15.09.2021

Antworten
Das sei auch noch kurz formal geklärt:

(IV)  2kmod7=2(k  mod  3)    kN.

(IA)  k=0:20mod7=1=2(0  mod  3).

(IS)  (2k+1)mod7=(22k)mod7=(2(2kmod7))mod7

=(22(k  mod  3))mod7=(2((k+1)  mod  3))mod7=2((k+1)  mod  3).


Frage beantwortet
mariem

mariem aktiv_icon

07:26 Uhr, 16.09.2021

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