/206$5

Ganzzahlige Division und Kongruenzen

80/7 = 11 Rest 3

Satz: ∀ a∈ Z, d ∈ Z+   ∃! q∈Z, r ∈Z
        mit 0 ≤ r <d:

a = q * d +r

Beispiel:
a = 80
d = 7        (Teiler/Divisor)
q= 11
r= 3        (Rest)

0 ≤ 3 < 7

a=110
d=37
q=2
r=36

Beweis der Existenz:

Für q = 0 und r = a gilt

(1) a = q * d + r
(Ich nehme an a und d sind gegeben.)
M = {(q, r): a = q*d+r ^r ≥ 0}
(zur vereinfachung nehmen wir a ≥ 0 an)
M ≠ ∅
Sei (q*, r*) das Tupelpaar in M mit dem kleinsten Wert r. und r** < r* ⚡

z.z.:    0 ≤ r* < d
⚡ r* >= d

definiere r** = r* - d
          q** = q* + 1

Offensichtlich: (q**,r**) € M
            und r** < r*    ⚡

Eindeutigkeit

⚡
Sei (q,r) ≠ (q',r') zwei solche geordneten Paare.
        a = q * d + r
        a = q'* d + r'

=> 0 = (q-q') * d + (r-r')
Es gilt 0 ≤ r ≤ d-1
        d - 1 ≤ -r' ≤ 0
    => d - 1 ≤ r - r' ≤ d-1
    => |r-r'| < d (Betrag)
Wenn (q-q') ≠ 0
=> | d(q-q') | ≥ d
r - r' = (q'-q) * d
=> d > |r-r'| = |(q'-q) * d| ≥ d
=> q = q'
    r-r' = (q'-q)*d
         = 0
         => r = r' ⚡
                              °     °
                                 L
                             \       /
                              \_____/

Wir definieren ≡ ⊆ ZxZ = Z² wie folgt:
            a ≡ b mod d
        <=> a und b haben den selben Rest bei Division durch d (siehe letztes Theorem (anderes Wort für Satz))
        <=> d | (a*b)

Modulo

http://gpg4win.de/handbuecher/durchblicker_24.html

Satz: Rechnen mit Modulo.
    ≡ ist eine Äquivalenzrelation, die "verträglich" mit den Operationen * und + ist
    D.h. a≡a' mod d
    und b≡b' mod d
    dann gilt:
    a+b ≡ a'+ b' mod d
    a*b ≡ a'* b' mod d
    a-b ≡ a - b' mod d

71*73*75≡x mod 5
      x ≡0 mod 5
75/5 = 15 Rest 0
x≡0≡71*73*0 mod5

x=81        d=2
81*2=40 Rest 1
1/2=0 Rest 1

also:
81    ≡1 mod 2
83    ≡1 mod 2
81*83 ≡1 mod 2

11² ≡ 11*11 mod 7
    ≡ 4*4   mod 7
    ≡ 16    mod 7
    ≡ 2     mod 7

11^4 ≡ (11^2)^2 mod 7
     ≡ (2)^2    mod 7
     ≡ 4        mod 7

11^8 ≡ (11^4)^2 mod 7
     ≡ 4^2      mod 7
     ≡ 2        mod 7

11^11 ≡ 11^8*11^3 mod 7
      ≡ 2 * 4^3   mod 7
      ≡ 2 * 4^2*4 mod 7
      ≡ 1*2       mod 7
      ≡ 2         mod 7

10     ≡ 1     mod 3
100    ≡ 1     mod 3
10^37 ≡ 1     mod 3

Wann ist eine Zahl durch 3 teilbar?

Wenn bei der Division durch 3 kein Rest bleibt.

x ≡ 0 mod 3 <=> x ist durch 3 teilbar.

x * 10 + y *100 + z * 1000
≡ x+y+z mod 3

Sei x eine Zahl in Dezimalform gegeben.
Mit Ziffern: (an)(am), ... a0, dann ist der wert von x
a0 + a1*10+a2*10^2+a3*10^3 + .... + an*10^n
≡ a0+a1+.... +an mod 3

Spiel mit Münzen

Münzen werden an den Kopf gehalten und Kopf oder Zahl wird richtig erraten, nach bestimmten Regeln.

2 Protagonisten
- beide halten zufällig Kopf oder Zahl
- beide sehen nur die Münze des Anderen
- beide raten gleichzeitig ihre Münze und genau einer ist richtig.

Protagonist 1 sagt was er sieht und Protagonist 2 sagt das Gegenteil von dem was er sieht. Wenn beide Münzen das selbe anzeigen ist P1 richtig, sonst P2.

Ausdruck mit Modulo: "Zahl" soll 0 bedeuten und "Kopf" soll 1 bedeuten und x ist die Summe mod 2 der beiden gezeigten Münzen.
x ≡ 0 mod 2 genau dann, wenn die beiden Münzen das gleiche anzeigen.
x ≡ 0 mod 2 g.d.w die beiden Münzen unterschiedliches anzeigen.

BEISPIEL
mit 3 Personen und 3 Karten (Bube (0), Dame(1), König(2))
x = Karte 1 + Karte 2 + Karte 3 mod 3
Niemand kennt x :-(
Protagonisten i glaubt die Summe x ≡ i mod 3 (prot.0 denkt es er hat 0, prot.1 denkt er hat 1, ...)

einfach mal mitdenken! =D
wer mitdenkt, der brauch keine mitschriften.
Niemand hat die Absicht mitzudenken!
Niemand hat die Absicht mitzuschreiben.
Niemand hat die Absicht eine Mauer zu errichten.
Die ist ja auch schon weg. (auch wenn ihr sie nicht mehr erlebt habt^^)