[대학교이상] 합동식을 이용한 소인수분해 질문.

[익명(119.196)]

소수 p, q에 대하여 정수 n = pq일 때,

x^2 ≡ y^2 (mod n)이고 x ≢ ±y (mod n)을 만족하는 x, y를 찾으면 d=gcd(x-y, n) 또는 d=gcd(x+y,n)에 대하여 d ≠ pq = n임을 보인 것 같은데
d ≠ 1임은 어떻게 알 수 있나요?

[익명(119.196)]

(p | x-y or p | x+y) and (q | x-y or q | x+y)이므로, gcd(x-y, n)>1이나 gcd(x+y, n)>1일 수 밖에 없음