Zahlentheorie Modulo. 39 * x = 4 (mod 35)

Question

ich komme bei einer Aufgabe nicht weiter.

Die Aufgabe lautet: 39 * x = 4 (mod 35)

Als Hinweis ist der erweiterte Euklid genannt. Allerdings komme ich immer auf ein Ergebnis vom x = 7, und das passt bei der Probe nicht.

Danke fürneure Hilfe

Answer 1

39 * x = 4 (mod 35)

es ist 39 = 35 + 4 also 39 ≡ 4 (mod 35)

Damit ist die Gl. äquivalent zu

  4 * x = 4 (mod 35)

also jedenfalls 1 eine Lösung.

oder wenn " beim normalen Rechnen"
4*x = 4+35 = 39   herauskäme, geht aber nicht
4*x = 4+2*35 = 74   herauskäme, geht aber nicht
4*x = 4+3*35 = 109   herauskäme, geht aber nicht
4*x = 4+4*35 = 144   herauskäme, geht mit x=36 , das ist aber wieder =1
etc.

also ist  x=1 die einzige Lösung.