Lineare Kongruenzen

29.05.2022, 14:52

Mathekerl

Lineare Kongruenzen

Ich denke a ist vier, denn ggt(4, 12)= 4 lautet und damit wird die allgemeine Formel von x=3x+2 produziert und daraus 4 Lösungen,
jeweils 2, 5, 8, 11 in Z12

Habe ich dieses Problem richtig gelöst?

Ich brauche eure Hilfe! :=)
Danke sehr!

29.05.2022, 17:21

HAL 9000

Auf diesen Beitrag antworten »

Das "x=3x+2" verbuche ich mal unter Schreibfehler...

$\begin{eqnarray*} a=4 \end{eqnarray*}$ ist eine mögliche Lösung, ja: $\begin{eqnarray*} 4x\equiv 8\bmod 12 \end{eqnarray*}$ ist nach Division durch 4 äquivalent zu $\begin{eqnarray*} x\equiv 2\bmod 3 \end{eqnarray*}$ , was modulo 12 dann den Resten 2,5,8,11 entspricht, wie von dir richtig beschrieben.

Genausogut wäre aber auch $\begin{eqnarray*} a=8 \end{eqnarray*}$ möglich, dann mit $\begin{eqnarray*} 8x\equiv 8\bmod 12 \end{eqnarray*}$ und in der Folge $\begin{eqnarray*} x\equiv 1\bmod 3 \end{eqnarray*}$ , und den Resten 1,4,7,10 modulo 12.

29.05.2022, 18:25

Finn_

Auf diesen Beitrag antworten »

Sei $\begin{eqnarray*} a'\in\mathbb Z \end{eqnarray*}$ beliebig und sei $\begin{eqnarray*} a\in\mathbb Z_m. \end{eqnarray*}$

Allgemeine Gesetzmäßigkeit: Wenn $\begin{eqnarray*} a'\equiv a \end{eqnarray*}$ modulo $\begin{eqnarray*} m \end{eqnarray*}$ ist, muss $\begin{eqnarray*} a'x\equiv ax \end{eqnarray*}$ modulo $\begin{eqnarray*} m \end{eqnarray*}$ sein.

Weil die $\begin{eqnarray*} a \end{eqnarray*}$ als Restklassen betrachtet eine Zerlegung von $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ bilden, genügt die Bestimmung von $\begin{eqnarray*} a \end{eqnarray*}$ mit der in der Aufgabenstellung geforderten Eigenschaft. Die allgemeine Lösungsmenge zu $\begin{eqnarray*} a \end{eqnarray*}$ besteht aus den $\begin{eqnarray*} a'=a+km \end{eqnarray*}$ per $\begin{eqnarray*} k\in\mathbb Z \end{eqnarray*}$ parametrisiert, weil wie gesagt die Rechnung

$\begin{eqnarray*} (a+km)x = ax+kxm \equiv ax \end{eqnarray*}$ modulo $\begin{eqnarray*} m \end{eqnarray*}$

gilt. Nun gibt es nur noch endlich viele Kandidaten. Anstelle die im Artikel Lineare Kongruenz aufgezeigte Theorie zur Anwendung zu bringen, kann man auch einfach naive erschöpfende Suche rechnen lassen:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:

def solve_linear_cong(a, b, m):
    return [x for x in range(m) if (a*x)%m == b]

def solutions_by_count(b, m):
    it = ((a, solve_linear_cong(a, b, m)) for a in range(m))
    return sorted(it, key = lambda t: len(t[1]))

for a, s in solutions_by_count(8, 12):
    print("a = {:2} | {} | {}".format(a, len(s), s))

Ausgabe:
a =  0 | 0 | []
a =  3 | 0 | []
a =  6 | 0 | []
a =  9 | 0 | []
a =  1 | 1 | [8]
a =  5 | 1 | [4]
a =  7 | 1 | [8]
a = 11 | 1 | [4]
a =  2 | 2 | [4, 10]
a = 10 | 2 | [2, 8]
a =  4 | 4 | [2, 5, 8, 11]
a =  8 | 4 | [1, 4, 7, 10]

Neue Frage »

Antworten »

Lineare Kongruenzen

Verwandte Themen