Kongruenz berechnen 245x ≡ 1(352). Modulo 352. Vorgehensweise?

Question

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

Comments

Kannst du vielleicht damit was machen?

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

Alternative vielleicht: Rubrik 'ähnliche Fragen'.

Answer 1

Das kannst du mit dem inversen Euklidischen Algorithmus berechnen:

 

352 : 245 = 1 R 107	1 = 38*245 - 87*(352 - 1*245) = 125*245 - 87*352
245 : 107 = 2 R 31	1 = 38*(245 - 2*107) - 11*107 = 38*245 - 87*107
107 : 31 = 3 R 14	1 = 5*31 - 11*(107 - 3*31) = 38*31 - 11*107
31 : 14 = 2 R 3	1 = 5*(31 - 2*14) - 1*14 = 5*31 - 11*14
14 : 3 = 4 R 2	1 = 3 - 1*(14 - 4*3) = 5*3 - 1*14
3 : 2 = 1 R 1	1 = 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

Comments

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

Answer 2

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)

Comments

irgendwelche tipps für aufgabe 2? ^^