Zeigen Sie: Für jedes 0 p existieren ganze Zahlen s, t ∈ ℤ, sodass as + pt = 1.

Question

Aufgabe:

a) Sei p eine Primzahl. Zeigen Sie: Für jedes 0 < a < p existieren ganze Zahlen s, t ∈ ℤ, sodass as + pt = 1. Folgern Sie daraus die Invertierbarkeit von a ∈ ℤ_p.

b) Zeigen Sie: Angenommen p ∈ ℤ ist keine Primzahl, dann existiert ein a ∈ ℤ_p, welches kein multiplikatives Inverses hat.

Problem/Ansatz:

Mir ist der erweiterte euklidische Algorithmus und seine Funktion klar, allerdings komme ich nicht drauf, wie man dies allgemein zeigen kann.

Answer 1

Hallo

da a und p teilerfremd  folgt aus dem erweiterten Euklidischen Alg. direkt dass man den ggT(a,p)=1 als  as+pt schreiben kann.Ich denke nicht das man dass für jeden einzelnen fall neu beweisen muss. denn dass man mit a<p mit maximal (p-1)/2 schritten bei 1 ankommt ist klar.

b) benutze dass  es mindestens ein a gibt mit r ggT(p,a)>1, d.h man kann a nicht wie in a) darstellen.  Oder p=q*r , q prim  dann ergibt q*r=0 mod p  also q und r haben kein Inverses,

lul