Euklidischen Algorithmus. Zeigen, dass 261 und 2014 teilerfremd. Multiplikatives Inverses von 261 modulo 2014?

Question

Verizieren Sie mit Hilfe des Euklidischen Algorithmus, dass 261 und 2014 teilerfremd sind, und berechnen Sie das multiplikativ Inverse von 261 modulo 2014 (als Element von {0,1,...,2013}).

Comments

also ich kann dir hierzu sagen, dass

261 modulo 2014 = 261 ergibt. 261 ist der Restwert.

Also 261 = (0*2014) + 261

Answer 1

(1)  2014 : 261 = 7 Rest 187
⇔ 187 = 2014 - 7·261.

(2)  261 : 187 = 1 Rest 74
⇔ 74 = 261 - 1·187 = 261 - 1·(2014 - 7·261) = -2014 + 8·261.

(3)  187 : 74 = 2 Rest 39
⇔ 39 = 187 - 2·74 = (2014 - 7·261) - 2·(-2014 + 8·261) = 3·2014 - 23·261.

(4)  74 : 39 = 1 Rest 35
⇔ 35 = 74 - 1·39 = (-2014 + 8·261) - 1·(3·2014 - 23·261) = -4·2014 + 31·261.

(5)  39 : 35 = 1 Rest 4
⇔ 4 = 39 - 1·35 = (3·2014 - 23·261) - 1·(-4·2014 +31·261) = 7·2014 - 54·261.

(6)  35 : 4 = 8 Rest 3
⇔ 3 = 35 - 8·4 = (-4·2014 + 31·261) - 8·(7·2014 - 54·261) = -60·2014 + 463·261.

(7)  4 : 3 = 1 Rest 1
⇔ 1 = 4 - 1·3 = (7·2014 - 54·261) - 1·(-60·2014 + 463·261) = 67·2014 - 517·261.

D.h. es ist  ggT(2014,261) = 1, und das Inverse modulo 2014 von 261 ist -517, bzw. 1497.

Answer 2

Hallo nochmal,

weiter habe ich dazu:

ggt(261,2014) = 1 = x * 261 + y * 2014

2014 = 261 * q₁ + r₂

⇒ 2014 = 261 * 7 + 187

261 = 187 * 1 + 74

187 = 74 * 2 + 39

74 = 39 * 1 + 35

39 = 35 * 1 + 4

35 = 4 * 8 + 3

4 = 3 * 1 + 1

3 = 1 * 3