78문풀 52번

[임용부시자!]

52번 풀이 중 마지막 부분에 대해 질문드립니다!
사진 풀이에서 형광펜 부분을 1) 과 2) 중 어떤 방법으로 이해하는 것이 맞을까요? 1) 이 논리적으로 더 옳은 것 같은데, 2)와 같이 직관적으로 생각하고 풀어도 오류가 없는지 궁금합니다.

[박정환]

1, 2 둘다 논리적으로 맞습니다. 2번도 gcd(4,23)=1이고 (4/23)=1이라 항상 해가 2개 존재하게 되어 충분한 설명이 되는데 어떤 부분에서 직관적이거나 오류가 있을거라고 생각하실까요. 그 부분을 메꾸시면 될 것 같아요. 제 경우 2번으로 적용하기 어려운 경우에만 1번으로 생각해줍니다.

[임용부시자!]

2)의 경우에서 르장드르값이 1이라 해를 항상 가진다는 것은 알겠으나, 단지 이차합동식이라 해를 2개 가진다고 보는 것인지, 아니라면 그 개수가 2개인 이유를 잘 모르겠습니다..!

[박정환]

(a/p)=1이면 x^2==a (mod p)의 해가 존재한다는 이야기인데, x_0가 해면 -x_0도 해가 되므로 항상 2개의 해를 갖습니다.