0 Daumen
784 Aufrufe
hallo,

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

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

Alternative vielleicht: Rubrik 'ähnliche Fragen'.

2 Antworten

+1 Punkt
 
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

Beantwortet von 262 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

http://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus
danke! hat mir sehr geholfen :)
+1 Punkt
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)
Beantwortet von
irgendwelche tipps für aufgabe 2? ^^

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...