Warum gilt diese Kongruenz Umformung

Question

Sei a teilerfremd zu n

warum gilt dann, dass:

a^x kongrunet zu a mod(n)

ist äquivalent zu:

a^x-1 kongruent zu 1 mod(n)

Das hört sich sehr wie Fermats kleiner Satz, ist aber ein wenig anders. Vllt kann mir hier ja jdm kurz helfen.

Vielen Dank dann schonmal für die Hilfe! :)

Comments

a^(x-1) = a^x/a

Answer 1

Hallo

multipliziere a^x-1=1 mod n mit a

oder multipliziere a^x=a mod n mit dem Inversen von a also a^-1

Gruß lul

Comments

Vielen Dank!

Aber wenn n und a nicht teilerfremd wären, würde es dann auch klappen? Also stimmt die umformung immer?

---

Nein. Sie stimmt nicht immer.

Nimm \(n=6\) und \(a=3\)

---

Hallo

wenn n und a nicht tellerfremd sind muß a^-1 nicht existieren,

Beispiel 2^3=2 mod 6 inverses zu 2 existiert nicht! 2^2=-2mod 6

lul