Matroids Matheplanet Forum Index
Moderiert von Wauzi
Teilbarkeit » Kongruenzen » Kongruent modulo p und q impliziert kongruent modulo n
Autor
Ausbildung Kongruent modulo p und q impliziert kongruent modulo n
nojoker
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.11.2021
Mitteilungen: 4
  Themenstart: 2021-11-11

In dem Beweis für das RSA Verfahren steht bei uns: \(𝑧_𝑎 ≡ 𝑧_𝑎^{𝑐∗𝑑}𝑚𝑜𝑑 (𝑝)\) und \(𝑧_𝑎 ≡ 𝑧_𝑏^{𝑐∗𝑑} 𝑚𝑜𝑑 (𝑞)\) impliziert auch \(𝑧_𝑎 ≡ 𝑧_𝑏^{𝑐∗𝑑} 𝑚𝑜𝑑 (p*q)\) Irgendwie kenne ich keine Begründung, wieso das für die Multiplikation auch gilt. Kennt ihr eine anschauliche Begründung? Vielen Dank!!


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7862
Wohnort: Milchstraße
  Beitrag No.1, eingetragen 2021-11-11

Hallo nojoker, allgemein gilt \(a\equiv b\mod m\wedge a\equiv b\mod n\implies a\equiv b\mod kgV(m,n)\) Das lässt sich einfach mit der Definition von mod beweisen.


   Profil
nojoker
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.11.2021
Mitteilungen: 4
  Beitrag No.2, vom Themenstarter, eingetragen 2021-11-11

Ich verstehe eben nicht, wieso der kgV auch kongruent sein muss. Welche Definition verwendest du?


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 3960
  Beitrag No.3, eingetragen 2021-11-11

$a\equiv b\pmod m$ bedeutet, dass $a-b$ ein Vielfaches von $m$ ist. Wenn nun auch noch $a\equiv b\pmod n$ ist, ist $a-b$ ein gemeinsames Vielfache von $m$ und $n$. Und alle gemeinsamen Vielfache von $m$ und $n$ sind Vielfache des kleinsten gemeinsamen Vielfachen von $m$ und $n$. --zippy


   Profil
Zwerg_Allwissend
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 02.12.2013
Mitteilungen: 284
  Beitrag No.4, eingetragen 2021-11-11

\quoteon(2021-11-11 09:02 - nojoker im Themenstart) In dem Beweis für das RSA Verfahren steht bei uns: \(𝑧_𝑎 ≡ 𝑧_𝑎^{𝑐∗𝑑}𝑚𝑜𝑑 (𝑝)\) und \(𝑧_𝑎 ≡ 𝑧_𝑏^{𝑐∗𝑑} 𝑚𝑜𝑑 (𝑞)\) impliziert auch \(𝑧_𝑎 ≡ 𝑧_𝑏^{𝑐∗𝑑} 𝑚𝑜𝑑 (p*q)\) Irgendwie kenne ich keine Begründung, wieso das für die Multiplikation auch gilt. Kennt ihr eine anschauliche Begründung? Vielen Dank!! \quoteoff Falls p und q Primzahlen sind, so gilt (*) ∀ p, q, x, y : ℕ ℙ(p) ∧ ℙ(q) ∧ p ≠ q ∧ [x ≡ y] mod p ∧ [x ≡ y] mod q → [x ≡ y] mod p * q Mit (1) ∀ n, m : ℕ n ≠ 0 ∧ ℙ(m) ∧ n | m → n = 1 ∨ n = m und (2) ∀ n, y, x : ℕ ℙ(n) ∧ n | x * y → n | x ∨ n | y [Euclid] beweist man (3) ∀ m, n, x : ℕ ℙ(n) ∧ ℙ(m) ∧ n ≠ m ∧ n | x ∧ m | x → m | (x / n) damit dann (4) ∀ m, n, x : ℕ ℙ(n) ∧ ℙ(m) ∧ n ≠ m ∧ n | x ∧ m | x → n * m | x und mit (4) schließlich (*).


   Profil
nojoker hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]