Zeigen Sie, dass ggT (a+b,n) ein nichttrivialer Teiler von n ist, wenn a≡(gleich ist Durchgestrichen) ±b mod n

Question

Es seien a,b,n ∈ ℤ mit a^2 ≡b^2 mod n gegeben.

Zeigen Sie, dass ggT (a+b,n) ein nichttrivialer Teiler von n ist, wenn a≡(gleich ist Durchgestrichen) ±b mod n

Finden Sie einen nichttrivialen Teiler von 8051 mithilfe der Gleichung 111²≡277² Mod 8051

Kann mir jemand hierbei helfen?

Answer 1

Hallo

benutze  a^2 ≡b^2 mod n folgt  a^2-b^2=k*n. k ganz

daraus (a+b)*(a-b)=k*n

wegen a-b≠ m*n folgt (a+b) teilt n

lu