Ggt finden mit Gleichung

Question

Finden Sie mit Hilfe der Gleichung

111² ≡ 277² mod 8051 einen nichttrivialen Teiler der ganzen Zahl 8051

Die Lösung sagt mir hier dass ich den größten gemeinsamen Teiler von 111+277 = 388 und 8051 berechnen soll.

Kann mir bitte jemand erklären wieso 388? Was ist denn mit den "Quadraten" ?

Comments

Du hast

$$ 111^2 - 277^2 = (111+277)(111-277) \equiv 0 \mod (8051) $$

Das heißt \( (111+277)(111-277) \) ist ein ganzzahliges Vielfaches von 8051. Also

$$ 388 \cdot (-166) = k \cdot 8051 \text{  für ein } k \in \mathbb Z $$

Jetzt kann man schauen ob die beiden Faktoren 388 und 166 einen nichttrivialen gemeinsamen Teiler mit 8051 besitzen. z.B. indem man den größten gemeinsamen Teiler berechnet.

Answer 1

Nimm die 3. binomische Formel und

mache aus 111^2 ≡ 277^2

277^2 - 111^2  ≡ 0

(277-111)(277+111)≡ 0