# Diskrete Mathematik - Lab 1 - Modulares rechnen

* Gruppe Nummer 12: Schupp, Sybille; Pfeiffer, Felix; Bubeck, Jannik

## Laboraufgabe 1

### 1.1 $ggT(24140,16762)$

$24140 = 1 \cdot 16762 + 7378$
$16762 = 2 \cdot 7378 + 2006$
$7378 = 3 \cdot 2006 + 1360$
$2006 = 1 \cdot 1360 + 646$
$1360 = 2 \cdot 646 + 68$
$646 = 9 \cdot 68 + 34$
$68 = 2 \cdot 34 + 0$

$ggT(24140,16762) = 34$

### 1.2 $ggT(4655,12075)$ als Linearkombination

#### ggT mit Euklidischem Algorithmus berechnen

$12075 = 2 \cdot 4655 + 2765$
$4655 = 1 \cdot 2765 + 1890$
$2765 = 1 \cdot 1890 + 875$
$1890 = 2 \cdot 875 + 140$
$875 = 6 \cdot 140 + 35$
$140 = 4 \cdot 35 + 0$

$ggT(4655,12075) = 35$

#### Rückrechnung

$35 = 875 - 6 \cdot 140 = 875 - 6\cdot (1890 - 2 \cdot 875)$
$~~~~ = -6 \cdot 1890 + 13 \cdot 875 = -6 \cdot 1890 + 13 \cdot (2765 - 1 \cdot 1890)$
$~~~~ = 13 \cdot 2765 - 19 \cdot 1890 = 13 \cdot 2765 - 19 \cdot (4655 - 1 \cdot 2765)$
$~~~~ = -19 \cdot 4655 + 32 \cdot 2765 = -19 \cdot 4655 + 32 \cdot (12075 - 2 \cdot 4655)$
$~~~~ = 32 \cdot 12075 - 83 \cdot 4655$

$ggT(4655,12075) = 35 = 32 \cdot 12075 - 83 \cdot 4655$

### 1.3

**a)** $7 \cdot 4 - 21 \cdot 6 \equiv 2 \cdot 4 + 4 \cdot 1 = 8 + 4 \equiv 3 + 4 = 7 \equiv 2 \mod 5$

**b)** $17 \cdot 5 + 13 \cdot 11 \equiv 8 \cdot 5 + 4 \cdot 2 = 40 + 8 \equiv 4 + 8 = 12 \equiv 3 \mod 9$

**c)** $6 \cdot 14 - 9 \cdot 7 \equiv 6 \cdot 3 - 9 \cdot 7 = 18 - 63 \equiv 7 + 3 = 10 \mod 11$

### 1.4

#### a) $18 \mod 49

##### Schritt 1: ggT(18,49) berechnen

$49 = 2 \cdot 18 + 13$
$18 = 1 \cdot 13 + 5$
$13 = 2 \cdot 5 + 3$
$5 = 1 \cdot 3 + 2$
$3 = 1 \cdot 2 + 1$
$2 = 2 \cdot 1 + 0$

$ggT(18,49) = 1$

##### Schritt 2: Rückrechnung für Vielfachsumme

$1 = 3 - 1 \cdot 2 = 3 - 1 \cdot (5 - 1 \cdot 3)$
$~~= -1 \cdot 5 + 2 \cdot 3 = 1 \cdot 5 + 2 \cdot (13 - 2 \cdot 5)$
$~~= 2 \cdot 13 - 5 \cdot 5 = 2 \cdot 13 - 5 \cdot (13 - 1 \cdot 13)$
$~~= -5 \cdot 18 + 7 \cdot 13 = -5 \cdot 18 + 7 \cdot (49 - 2 \cdot 18)$
$~~= 7 \cdot 49 - 19 \cdot 18$

$a=18 ,n=49$
$\alpha = -19, \beta = 7$

##### Schritt 3: Inverse berechnen

$\alpha = -19 < 0$
--> $a' = \alpha + n = -19 + 49 = 30$

#### b) $3 \mod 101$

##### Schritt 1: ggT(3,101) berechnen

$101 = 33 \cdot 3 + 2$
$~~~~~~= 1 \cdot 2 + 1$
$~~~~~~= 2 \cdot 1 + 0$

$ggT(3,101) = 1$

##### Schritt 2: Rückrechnung für Vielfachsumme

$1 = 3 - 1 \cdot 2 = 3 - 1 \cdot (101 - 33 \cdot 3)$
$~~ = -1 \cdot 101 + 34 \cdot 3$

$a= 3, n = 101$
$\alpha = 34, \beta = -1$

##### Schritt 3: Inverse berechnen

$\alpha = 34 > 0$
--> $a' = \alpha = 34$

#### c) $126 \mod 239$

##### Schritt 1: ggT(126,239) berechnen

$239 = 1 \cdot 126 + 113$
$126 = 1 \cdot 113 + 13$
$113 = 8 \cdot 13 + 9$
$13 = 1 \cdot 9 + 4$
$9 = 2 \cdot 4 + 1$
$4 = 4 \cdot 1 + 0$

$ggT(126,239) = 1$

##### Schritt 2: Rückrechnung für Vielfachsumme

$1 = 9 - 2 \cdot 4 = 9 - 2 \cdot (13 - 1 \cdot 9)$
$~~= -2 \cdot 13 + 3 \cdot 9 = -2 \cdot 13 + 3 \cdot (113 - 8 \cdot 13)$
$~~= 3 \cdot 113 - 26 \cdot 113 = 3 \cdot 113 - 26 \cdot (126 - 1 \cdot 13)$
$~~= -26 \cdot 126 + 29 \cdot 113 = 26 \cdot 126 + 29 \cdot (239 -1 \cdot 126)$
$~~=29 \cdot 239 - 55 \cdot 126$

$a = 126, n = 239$
$\alpha = -55, \beta = 29$

##### Schritt 3: Inverse berechnen

$\alpha = -55 < 0$
-->$a' = \alpha + n = -55 + 239 = 184$

## Laboraufgabe 2

### 2.1 Restklassenkonstruktion

#### a,b) Restklassen $Z_4, Z_5, Z_7$

$Z_4$:


$Z_5$:


$Z_7$:


#### c) Anzahl Restklassen

**Hinweis:** Jede Division ist als Ganzzahldivision zu verstehen.

| $n = 4$ | $[0]_4$ | $[1]_4$ | $[2]_4$ | $[3]_4$ |
| -------- | -------- | -------- | -------- | -------- |
| -10 bis 10 | 5 | 5 | 6 | 5 |
| -20 bis 20 | 11 | 10 | 10 | 10 |
| -z bis z | $\frac{z*2}{n} \pm x, x \in \{0,1\}$ | $\frac{z*2}{n} \pm x, x \in \{0,1\}$ | $\frac{z*2}{n} \pm x, x \in \{0,1\}$ | $\frac{z*2}{n} \pm x, x \in \{0,1\}$ |

| $n = 5$ | $[0]_5$ | $[1]_5$ | $[2]_5$ | $[3]_5$ |$[4]_5$ |
| -------- | -------- | -------- | -------- | -------- | - |
| -10 bis 10 | 5 | 4 | 4 | 4 |4
| -20 bis 20 | 9 | 8 | 8 | 8 |8
| -z bis z | $\frac{z*2}{n} \pm x, x \in \{0,1\}$ | $\frac{z*2}{n} \pm x, x \in \{0,1\}$ | $\frac{z*2}{n} \pm x, x \in \{0,1\}$ |$\frac{z*2}{n} \pm x, x \in \{0,1\}$| $\frac{z*2}{n} \pm x, x \in \{0,1\}$ |

| $n = 7$ | $[0]_7$ | $[1]_7$ | $[2]_7$ | $[3]_7$ | $[4]_7$ | $[5]_7$ | $[6]_7$
| -------- | -------- | -------- | -------- | -------- | -------- | -------- | - |
| -10 bis 10| 3 | 3 | 3 | 3 | 3 | 3 | 3
| -20 bis 20 | 5 | 6 | 6 | 6 | 6 | 6 |6
| -z bis z | $\frac{z*2}{n} \pm x, x \in \{0,1\}$ | $\frac{z*2}{n} \pm x, x \in \{0,1\}$ | $\frac{z*2}{n} \pm x, x \in \{0,1\}$ | $\frac{z*2}{n} \pm x, x \in \{0,1\}$ | $\frac{z*2}{n} \pm x, x \in \{0,1\}$ | $\frac{z*2}{n} \pm x, x \in \{0,1\}$ | $\frac{z*2}{n} \pm x, x \in \{0,1\}$ |

### 2.2 Repräsentantensystem

#### a,b) Repräsentantensystem von $Z_4$


#### c) Repräsentantensystem $Z_7$

$\{−23, −6, −3, 2, 7, 10\}$ ist kein Repräsentantensystem von $Z_7$, da es nur 6 Elemente hat, ein Repräsentantensystem von $Z_7$ benötigt aber genau 7 Elemente. $\{-23, -6 -3, 2, 7, 10, 20\}$ wäre ein Repräsentantensystem von $Z_7$.

$\{−16, −9, −2, 5, 12, 19, 26\}$ - Dies ist kein Repräsentantensystem sondern die Restklasse $[5]_7$, da alle Elemente in der Division mit 7, Rest 5 ergeben. Da bereits mehrere Elemente Rest 5 ergeben lässt sich kein gültiges Repräsentantensystem mehr bilden.

#### d) Repräsentantensystem $Z_5$

$\{-1, -2, 2, 6, 10\}$

Nachweis: Wir brauchen Zahlen, die Reste von 0-4 liefern.
- -1 --> Rest 4
- -2 --> Rest 3
- 2 --> Rest 2
- 6 --> Rest 1
- 10 --> Rest 0
Das ist bei uns gegeben --> es handelt sich um ein Repräsentantensystem.

#### 2.3 Programm

from funktionen import inverse

print("Gebe a an:")
a = int(input())
print("Gebe b an:")
b = int(input())
print("Gebe n an:")
n = int(input())
print(f"Teiler: {n}")

z1, z2, z3, z4 = a + b, a - b, a * b, a / b if b != 0 else None
r1, r2, r3, r4 = z1 % n, z2 % n, z3 % n, z4 % n if z4 else None

print(f"a + b = {a + b}, a - b = {a - b}, a * b =  {a * b}" + f", a / b = /
{a / b}" if z4 else "")
restklassen = [[] for x in range(n)]
restklassen[0].append(0)
for x in range(1, 100):
    restklassen[x % n].append(x)
    restklassen[-x % n].append(-x)

for p in range(len(restklassen)):
    restklassen[p].sort()

print(f"Restklasse für a + b mod n = {z1} mod {n} = {r1}: [{','.join(str(x)/
for x in restklassen[r1])}]")
print(f"Restklasse für a - b mod n = {z2} mod {n} = {r2}: [{','.join(str(x)/ 
for x in restklassen[r2])}]")
print(f"Restklasse für a * b mod n = {z3} mod {n} = {r3}: [{','.join(str(x)/ 
for x in restklassen[r3])}]")

inv = inverse(a, n)
r4 = (b*inv) % n
if inv:
    print(f"Restklasse für a / b mod n = a * inv mod n => {b*inv} mod {n} =/
    {r4}: [{','.join(str(x) for x in restklassen[r4])}]")
else:
    print("Restklasse für a/b nicht möglich")```

# funktionen.py
def ggT(z1, z2):
    groessere_Zahl, kleinere_Zahl = z1 if z1 > z2 else z2, z1/
    if z1 < z2 else z2

    b = kleinere_Zahl
    a = groessere_Zahl
    rest = a % b
    while rest != 0:
        a = b
        b = rest
        rest = a % b

    return b


def vielfachsumme(a, b):
    g, k = a if a > b else b, a if a < b else b

    faktor_g1, faktor_k1 = _vielfachsumme_berechnen(g, k)
    faktor_k2, faktor_g2 = _vielfachsumme_berechnen(k, g)

    if faktor_g1 + faktor_k1 < faktor_g2 + faktor_k2:
        return faktor_g1, faktor_k1 * -1
    else:
        return faktor_g2 * -1, faktor_k2


def _vielfachsumme_berechnen(a, b) -> (int, int):
    faktor_a, faktor_b = 1, 1

    while faktor_a * a - faktor_b * b != 1:
        if faktor_a * a - faktor_b * b < 1:
            faktor_a += 1
        else:
            faktor_b += 1
    # print(f"{a}*{faktor_a} - {b}*{faktor_b}")
    # print("Ergebnis: " + str(faktor_a * a - faktor_b * b))
    return faktor_a, faktor_b


def inverse(a, n):
    inverted = n > a
    if inverted:
        a, n = n, a
    ggt = ggT(a, n)

    if ggt != 1:
        return None

    alpha, beta = vielfachsumme(a, n)

    if inverted:
        n, a = a, n
        alpha, beta = beta, alpha
    return alpha % n


if __name__ == "__main__":
    print(inverse(126, 239))  # 184
    print("----")
    print(inverse(3, 101))  # 34
    print("----")
    print(inverse(18, 49))  # 30