Alle Lösungen finden für 5x ≡ 7 mod 13

Question

Hallo ich habe folgendes Mathe-Problem. Hab da ein Ansatz, komme da aber einfach nicht weiter und wäre froh, wenn mir da jemand weiterhilft :)

Ich soll für

 5x ≡ 7 mod 13

alle Lösungen x ∈ ℤ_m finden.

mein Ansatz:

ggT(5,13)=1, dadurch gibt es eine Lösung

der euklidische Algorithmus:

5 = 0*13 +5

13=5*2 +3

5= 3*1 +2

3= 2*1 +1

2= 1*2 +0

Ich muss glaube ich das Inverse finden, verstehe nicht wie.

Answer 1

Mit dem erweiterten euklid. Alg. findest du

a und b mit 5a+13b=1

Dann ist das a das Inverse von 5 mod 13.

Gibt 5*8+13*(-3)=1  also a^(-1)=8

Dann die Gleichung mal 8

5x*8 ≡ 7*8 mod 13

  x ≡ 4 mod 13  denn 56=4*13+4

Du bekommst x=4 als einzige Lösung.