Wie man ein System der modularen Äquivalenz mit Parametern löst
Gegebenes System modularer Äquivalenzen. Finden Sie den kleinsten natürlichen Parameter$a$ Dieses System hat Lösungen
$$\begin{cases} x \equiv a \mod 140\\ x \equiv 3 \mod 91\\ x \equiv 2a \mod 39 \end{cases}$$
Natürlich wird die Lösung geschätzt, aber wenn Sie dies nicht lösen möchten, geben Sie mir bitte einen Hinweis, ich weiß nicht einmal, wie ich dieses Problem angehen soll
Antworten
Es ist keine Primfaktorisierung der Module erforderlich - nur schnelle gcds. Nach dem CRT-Lösbarkeitskriterium ist ein System lösbar, wenn es paarweise lösbar ist, wenn jedes Paar hinsichtlich seines Moduls gcd konsistent ist. Lassen Sie uns alle Paarkonsistenzen überprüfen. Für das erste Paar$\,1,2\,$ das Modul gcd ist $\,(140,91) = 7\,$ damit
$\qquad\qquad\begin{align} x&\equiv a\!\!\!\pmod{\!140}\\ x&\equiv 3\!\!\!\pmod{\!91}\end{align}\,$ $\Rightarrow\, \begin{align} x&\equiv a\!\!\!\pmod{\!7}\\ x&\equiv 3\!\!\!\pmod{\!7}\end{align}\,$ $\Rightarrow\, \color{#c00}{a\equiv 3}\pmod{\!\color{#c00}{7}}$
Für ein Paar $\,1,3\,$ die Module gcd $= (140,39)\!=\!1\,$so ist es immer lösbar. Für ein Paar$\,2,3,\,$ genau wie oben bekommen wir $\bmod \color{#0a0}{13}\!=\!(91,39)\!:\,\ 2a\equiv 3\!\!\underset{\times 7\!\!}\iff \color{#0a0}a\equiv 21\equiv \color{#0a0}8.\,$ Somit ist das System lösbar, wenn
$$\begin{align} \color{#c00}{a\equiv 3}&\!\!\pmod{\!\color{#c00}7}\\ \color{#0a0}{a\equiv 8}&\!\!\pmod{\color{#0a0}{\!13}}\end{align}\qquad\qquad$$
Mit Easy CRT ist die Lösung$\ a\equiv \color{#0a0}8+13\underbrace{\left[\dfrac{\color{#c00}3-\color{#0a0}8}{13}\bmod 7\right]}_{\!\!\!\large \color{#90f}{-5/(-1)}\ \bmod 7}\equiv 8+13[\color{#90f}5]\equiv 73\pmod{\!7\cdot 13}$
Anmerkung $ $Da diese Methode nur gcds (im Vergleich zu Primfaktoren) verwendet, kann sie effizient (maschinell oder von Hand) für große Module durchgeführt werden - was mit Primfaktoren nicht möglich wäre, da derzeit kein effizienter Algorithmus zur Berechnung von Primfaktoren bekannt ist es gibt einen für gcds - den euklidischen Algorithmus.
$$x\equiv a\pmod{4,7,5}$$
$$x\equiv3\pmod{7,13}$$
$$x\equiv2a\pmod{3,13}$$
Damit, $a\equiv3\pmod7\ \ (1)$
$$2a\equiv3\pmod{13}\equiv13+3$$
$\iff a\equiv8\pmod{13} \ \ (2)$
Wenden Sie den chinesischen Restsatz auf an $(1),(2)$
Schauen Sie sich den chinesischen Restsatz an
Für Ihren Fall können x = 3 mod 91 = 3Sie also sehen:
3 = a mod 140
3 = 2a mod 39
Von wo Sie bekommen:
a = 3 + 140 * k1
a = (3 + 39 * k2 ) / 2
Jetzt sieht das Problem einfacher aus, da Sie nur das kleinere Paar (k1, k2) finden müssen, für das:
3 + 140 * k1 = (3 + 39 * k2 ) / 2
Durch Lösen können Sie erhalten:
k1 = 33
k2 = 237
a = 4623
PD: Entschuldigung für die Formatierung, ich lerne immer noch, wie ich es mache
Wenn das System konsistent ist, hat es Lösungen.
Schon seit $140=4\cdot 5\cdot 7$ dann ist das erste System äquivalent zu $$x \equiv a \pmod {4, 5, 7}$$
und ähnlich für die anderen Kongruenzen, die wir haben $x \equiv 3 \pmod{7, 13}$ und $x\equiv 2a \pmod{3,13}$.
Von Anfang an haben wir $x\equiv a \pmod{7}$ und von der zweiten $x\equiv 3 \pmod{7}$. Damit das System konsistent ist, müssen wir es haben$a\equiv 3 \pmod{7}$.
Ähnlich sehen wir das aus der zweiten und dritten Kongruenz $a$ muss auch befriedigen $2a\equiv 3\pmod {13}.$ Dann seit $2^{-1} \equiv 7 \pmod{7}$multiplizieren wir die Kongruenz mit $7$ und erhalten Sie das $$14a\equiv a \equiv21\equiv8 \pmod{13}$$
Damit das System konsistent ist, muss es also erfüllen $$a\equiv 3 \pmod{7}\space(1)$$ $$a \equiv8 \pmod{13}\space(2)$$
Schon seit $7$ und $13$ Sind Co-Prime, gibt es Lösungen Modulo $7\times13=91$von der CRT .
Von $(2)$ Wir wissen das $a=8+13k_1$ zum $k_1\in\mathbb Z$ und Ersetzen in die ersten gibt $$8+13k_1\equiv 3 \pmod{7}$$ $$13k_1\equiv 2 \pmod{7}$$
Damit $$13\times 6 k_1\equiv k_1\equiv 12\equiv 5 \pmod{7}$$
So $k_1=5+7k_2$ zum $k_2\in\mathbb Z$ und daher haben wir $a=8+13k_1=8+13(5+7k_2)=73+91k_{2}.$
Daher $a\equiv 73 \pmod {91}$ und der kleinste natürliche Parameter von $a$ ist $73$.