Question

was ist d bei 33*d kongruent zu 1 mod 40

Ich würde es gern mit Hilfe des euklidischen Algorithmus lösen und ein Vollständiger Lösungsweg wäre nicht schlecht.

Answer 1

(1)  40:33 = 1  Rest  7
⇔ 7 = 40 - 1·33

(2)  33:7 = 4  Rest  5
⇔ 5 = 33 - 4·7 = 33 - (40 - 1·33)·4 = 5·33 - 4·40

(3)  7:5 = 1  Rest  2
⇔ 2 = 7 - 1·5 = (40 - 1·33) - 1·(5·33 - 4·40) = 5·40 - 6·33

(4)  5:2 = 2  Rest  1
⇔ 1 = 5 - 2·2 = (5·33 - 4·40) - 2·(5·40 - 6·33) = 17·33 - 14·40.

Demnach ist  17·33 = 1 + 14·40 ≡ 1  mod  40, also  d = 17.