0 Daumen
2,7k Aufrufe


vielleicht kann mir ja jemand helfen?!
und zwar, wie berechne ich die kongruenz. genauer gesagt von  245x ≡ 1(352) ?? steh voll auf dem schlauch....:(
Avatar von
Kannst du vielleicht damit was machen?

https://www.mathelounge.de/99231/euklidischen-algorithmus-inverse

Alternative vielleicht: Rubrik 'ähnliche Fragen'.

2 Antworten

+1 Daumen
 
Beste Antwort

Das kannst du mit dem inversen Euklidischen Algorithmus berechnen:

 

352 : 245 = 1 R 1071 = 38*245 - 87*(352 - 1*245) = 125*245 - 87*352
245 : 107 = 2 R 311 = 38*(245 - 2*107) - 11*107 = 38*245 - 87*107
107 : 31 = 3 R 141 = 5*31 - 11*(107 - 3*31) = 38*31 - 11*107
31 : 14 = 2 R 31 = 5*(31 - 2*14) - 1*14 = 5*31 - 11*14
14 : 3 = 4 R 21 = 3 - 1*(14 - 4*3) = 5*3 - 1*14
3 : 2 = 1 R 11 = 3 - 1*2
2 : 1 = 2 R 0 

 

Es gilt also 

1 = 125*245 - 87*352

Die gesuchte Modular Inverse ist also 125

125*245 MOD 352 = 1

Avatar von 477 k 🚀
hallo Der_Mathecoach, wie kommt man dabei auf die rechte seite? im speziellen meine ich dabei die 38*245...
Die Tabelle verleitet leider eher von links nach rechts zu lesen das ist verkehrt.
Man rechnet die linke Seite von oben nach unten runter und dann die rechte von unten nach oben hoch. Dabei werden dann immer die Reste ersetzt.

Schau z.B. mal unter

https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus
+1 Daumen
Du musst glaube erst den ggT von 245 und 352 bestimmen (sollte 1 sein) und dann wieder rückwärts rechnen beginnend mit 1 = 3 - 2.

Wenn du dann wieder soweit bist, das 245 und 352 in der Gleichung vorkommen, dann ist der Faktor vor 245 dein gesuchter Wert.

(Falls du auch btu bist, einfach genau dasselbe wie in Aufgabe 1 & 2 machen)
Avatar von
irgendwelche tipps für aufgabe 2? ^^

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community