Äquivalenz zeigen, ( mod n)

Question

Aufgabe:

Es sei n ∈ Z fest gewählt.

(a) Zeige, dass die beiden Aussagen
    (i) ∃b ∈ ℤ: a·b ≡ 1( mod n)     (ii) ggT(a,n) = ± 1
äquivalent sind.

(b) Finde ein b ∈ ℤ,sodass 63·b ≡ 1( mod 271).

Ich brauche dringend Hilfe bei diesen beiden Aufgabenstellungen. Danke.

Comments

Verwende ggT(a,b)=1 <=> Es gibt x,y ∈ℤ mit a*x+b*y=1

Und  Werte für x und y findest du mit dem erweiterten

euklid. Algorithmus. Gibt in deinem Fall

bei b) 63*(-43)=-2709≡1 mod 271