Bestimmen von Lösungsmengen linearer Kongruenzen

Question

Kann mir jemand bei folgender Aufgabe helfen?

Es sollen die Lösungsmengen der nachfolgenden Kongruenzen bestimmt werden

a) 60x kongruent 18 mod 96

b)60x kongruent 18 mod 97

c) 60x kongruent 18 mod 66


Wichtig:
Die Lösungen sollen als Restklassen in modulo 96 (in a)), 97 (in b)) und 66 (in c)) angegeben werden.

Comments

Sicher,dass es 18 mod 96 und nicht 96 mod 18 ist ?

---

Jawohl. Die Teilaufgaben a,b,c unterscheiden sich nur durch die modulo-Angaben am Schluss,also 96,97 und 66.


Allerdings habe ich den Zusatz vergessen, dass eventuell keine Lösungen vorhanden sind (unter dem Punkt "Wichtig:"). Eventuell hilft das weiter...

Answer 1

Hinweis für b:

Wenn (a,m)=1 dann

$$a^{\phi(m)} \equiv 1 \mod m$$

97 ist eine Primzahl, also
$$\phi(97)=97-1=96$$


Also $$60^{96} \equiv 1 \mod{97}$$

Comments

Das kann ich nachvollziehen,aber wie hilft mir das bei der Lösung der anderen Teilaufgaben?

Bin im Moment noch ratlos

Answer 2

Hi, für lineare Kongruenzen gibt es sehr einfache Lösbarkeitsaussagen, die Du auch in den ersten vier Zeilen des folgenden Ausschnitts eines Wikipedia-Artikels (vermutlich aber auch in deinem Skript) findest:

Lösbarkeit von linearen Kongruenzen

(Eine deiner Gleichung hat keine Lösung, eine andere eine Lösung und eine weitere mehrere Lösungen.)