> Chinesischer Restsatz, Beispiel - YouTube
Operation, siehe Multiplikations-Invers-Element-Lösung). Das heißt: 15 ÷ 7 = 2 …… verbleibende 1, 21 ÷ 5 = 4 …… verbleibende 1, 70 ÷ 3 = 23 …… verbleibende 1. Verwenden Sie dann die drei kleineren Zahlen, um die erforderliche Zahl mit 7 zu multiplizieren. Chinesischer Restsatz und RSA - Wikimho. Das Produkt von dem durch Teilen erhaltenen Rest werden 5 und 3 kontinuierlich addiert, 15 × 2 + 21 × 3 + 70 × 2 = 233. Schließlich wird 233 durch das kleinste gemeinsame Vielfache der drei Teiler von 3, 5 und 7 geteilt. 233 ÷ 105 = 2...... Der Rest ist 23, dieser Rest 23 ist die kleinste Zahl, die die Bedingungen erfüllt. Erweitern Sie auf die allgemeine Situation: Unter der Annahme, dass die ganzen Zahlen m1, m2, …, mn gegenseitig Primzahlen sind, gilt für jede ganze Zahl: a1, a2, … ein Gleichungssystem: Es gibt ganzzahlige Lösungen, und wenn X, Y das Gleichungssystem erfüllen Es muss X ≡ Y (mod N) sein, wobei: Die Formel lautet wie folgt: Ich möchte wirklich nicht auf die Formelsymbole im Lehrbuch schauen. Nehmen wir die Hausaufgaben und geben zwei Beispiele.
Das Produkt M M stimmt hier wegen der Teilerfremdheit mit dem kgV überein. Finden einer Lösung Eine Lösung x x kann man wie folgt ermitteln. Für jedes i i sind die Zahlen m i m_i und M i: = M / m i M_i:= M / m_i teilerfremd, also kann man z. B. mit dem erweiterten euklidischen Algorithmus zwei Zahlen r i r_i und s i s_i finden, so dass r i ⋅ m i + s i ⋅ M i = 1 r_i \cdot m_i + s_i \cdot M_i = 1. Chinesischer restsatz rechner grand rapids mi. Setzen wir e i: = s i ⋅ M i e_i:= s_i \cdot M_i, dann gilt e i ≡ 1 m o d m i e_i \equiv 1 \mod m_i e i ≡ 0 m o d m j, j ≠ i e_i \equiv 0 \mod m_j, \ j \neq i. Die Zahl x: = ∑ i = 1 n a i e i x:= \sum\limits_{i=1}^n a_i e_i ist dann eine Lösung der simultanen Kongruenz. Beispiel Gesucht sei eine ganze Zahl x x mit der Eigenschaft x ≡ 2 ( m o d 3) x ≡ 3 ( m o d 4) x ≡ 2 ( m o d 5) \array{ {x \equiv 2 {\pmod 3}} {x \equiv 3 {\pmod 4}} {x \equiv 2 {\pmod 5}}} Hier ist M = 3 ⋅ 4 ⋅ 5 = 60, M 1 = M / 3 = 20, M 2 = M / 4 = 15, M 3 = M / 5 = 12 M = 3 \cdot 4 \cdot 5 = 60, \ M_1 = M/3 = 20, \ M_2 = M/4 = 15, \ M_3 = M/5 = 12.
Entfernen Sie zuerst die Koeffizienten: x ≡ 46 (mod 99) x ≡ 98 (mod 101) 求解方法很多,这里列举利用二元一次不定方程方法: 13x ≡ 4 (mod 99) 转化为 13x-99y = 4 然后用拓展欧几里德: 13×46-99×6 = 4 x=46, y=6 所以不定方程13x-99y = 4 的所有解为 x=46 + 99t y=6+13t 所以原同余方程解为:x ≡ 46 (mod 99) Eliminiere x, um zu erhalten: 99a-101b = 52 Erweitern Sie Euklidisch, um Sie zu begleiten: x = 7471 (mod 9999) x = 9999 n + 7471 (n ∈ Z)