이차잉여: 두 판 사이의 차이

2015년 12월 3일 (목) 05:05 판

정의

3 이상의 정수 \(m\)과 \((a,m)=1\)인 정수 \(a\)가 주어졌을 때, 법 \(m\)에 대한 합동식

[math]\displaystyle{ x^2\equiv a\pmod m }[/math]

의 해가 존재하면 \(a\)를 법 \(m\)에 대한 이차잉여(quadratic residue)라고 한다. 합동식의 해가 존재하지 않으면 \(a\)를 법 \(m\)에 대한 이차비잉여(quadratic nonresidue)라고 한다.

예시

\(m=11\)이라 가정하자. 그럼,

[math]\displaystyle{ 1^2\equiv\left(-1\right)^2\equiv10^2\equiv1\pmod{11} }[/math]

[math]\displaystyle{ 2^2\equiv\left(-2\right)^2\equiv9^2\equiv4\pmod{11} }[/math]

[math]\displaystyle{ 3^2\equiv\left(-3\right)^2\equiv8^2\equiv9\pmod{11} }[/math]

[math]\displaystyle{ 4^2\equiv\left(-4\right)^2\equiv7^2\equiv5\pmod{11} }[/math]

[math]\displaystyle{ 5^2\equiv\left(-5\right)^2\equiv6^2\equiv3\pmod{11} }[/math]

이므로, 1, 3, 4, 5, 9는 법 11에 관한 이차잉여가 된다. 2, 6, 7, 8, 10은 법 11에 관한 이차비잉여이다.

여기서 주의깊게 봐야할 점은, 11이 소수라는 것과 정확히 5개의 이차잉여와 5개의 이차비잉여가 있다는 점이다. 이는 모든 소수에대해 성립하며, 증명은 바로 아랫 문단의 성질을 참고하자.

성질

\(p\)는 홀수인 소수, \(a\)는 \(p\)와 서로소인 정수, \(r\)은 \(p\)의 원시근이라 가정하자.

[math]\displaystyle{ x^2\equiv a\pmod p }[/math]는 근을 가지지 않거나 정확히 두 개의 근을 가진다.
주어진 합동식이 근을 가지지 않으면 명제는 자연히 참이다. 만약 \(x_0\)이 주어진 합동식의 한 근이라면, \(-x_0\)도 근이 된다. 또한, \(p\)는 홀수이므로, [math]\displaystyle{ x_0\equiv-x_0\pmod p }[/math] (기우성이 다르다). 이제 \(y\)가 합동식의 또다른 근이라고 가정하자. 그럼 [math]\displaystyle{ y^2\equiv a\equiv {x_0}^2\equiv p }[/math]이고, [math]\displaystyle{ \left(y-x_0\right)\left(y+x_0\right)\equiv0\pmod p }[/math]이다. 이는 곧 [math]\displaystyle{ p\mid\left(y-x_0\right)\left(y+x_0\right) }[/math]임을 의미하고, \(p\)가 소수이므로 [math]\displaystyle{ p\mid y-x_0 }[/math] 혹은 [math]\displaystyle{ p\mid y+x_0 }[/math]이다. 어느쪽이든, [math]\displaystyle{ y\equiv\pm x_0\pmod p }[/math]이다. 즉, 주어진 합동식은 정확히 두 개의 근만을 가진다.
법 \(p\)에 대해 정확히 [math]\displaystyle{ \frac{p-1}{2} }[/math]개의 이차잉여와 이차비잉여가 존재한다.
바로 위 성질의 따름정리. 증명은 생략.
\(a\)가 법 \(p\)에 대한 이차잉여라면, [math]\displaystyle{ \operatorname{ind}_ra }[/math]는 짝수이다. 역도 성립한다.
[math]\displaystyle{ \operatorname{ind}_ra }[/math]가 짝수라 가정하자. 그럼, [math]\displaystyle{ a\equiv r^{\operatorname{ind}_ra}\equiv r^{\left(\frac{\operatorname{ind}_ra}{2}\right)2}\equiv\left(r^{\frac{\operatorname{ind}_ra}{2}}\right)^2\pmod p }[/math]이다. 따라서, \(a\) 는 법 \(p\)에 대한 이차잉여이다. 역으로, [math]\displaystyle{ x^2\equiv a\pmod p }[/math]의 해가 존재한다고 가정하자. 그럼, 한 해 \(x_0\)에 대해 [math]\displaystyle{ {x_0}^2\equiv a\pmod p }[/math]이고, 양변에 이산로그를 씌우면 [math]\displaystyle{ 2\operatorname{ind}_r{x_0}\equiv\operatorname{ind}_ra\pmod{p-1} }[/math]이다. 따라서, 적당한 정수 \(k\)에 대해 [math]\displaystyle{ \operatorname{ind}_ra=2\operatorname{ind}_r{x_0}+k\left(p-1\right) }[/math]이고, \(p-1\)은 짝수이므로 [math]\displaystyle{ \operatorname{ind}_ra }[/math]도 짝수이다.
원시근은 이차비잉여이다.
[math]\displaystyle{ \operatorname{ind}_rr=1 }[/math]은 홀수이므로 위 성질에 의해 \(r\)은 이차비잉여이다.

르장드르 기호를 사용하면 더 많은 성질을 알 수 있다. 르장드르 기호에 관련된 것은 항목 참조.

@@ 1번째 줄: / 1번째 줄: @@
 {{학술}}
-{{토막글}}
 == 정의 ==
 이상의 [[정수]] \(m\)과 \((a,m)=1\)인 정수 \(a\)가 주어졌을 때, 법 \(m\)에 대한 합동식
-: <math>x^2\equiv a \pmod m</math>
+:<math>x^2\equiv a\pmod m</math>
 의 해가 존재하면 \(a\)를 법 \(m\)에 대한 '''이차잉여(quadratic residue)'''라고 한다. 합동식의 해가 존재하지 않으면 \(a\)를 법 \(m\)에 대한 '''이차비잉여(quadratic nonresidue)'''라고 한다.
+== 예시 ==
+\(m=11\)이라 가정하자. 그럼,
+:<math>1^2\equiv\left(-1\right)^2\equiv10^2\equiv1\pmod{11}</math>
+:<math>2^2\equiv\left(-2\right)^2\equiv9^2\equiv4\pmod{11}</math>
+:<math>3^2\equiv\left(-3\right)^2\equiv8^2\equiv9\pmod{11}</math>
+:<math>4^2\equiv\left(-4\right)^2\equiv7^2\equiv5\pmod{11}</math>
+:<math>5^2\equiv\left(-5\right)^2\equiv6^2\equiv3\pmod{11}</math>
+이므로, 1, 3, 4, 5, 9는 법 11에 관한 이차잉여가 된다. 2, 6, 7, 8, 10은 법 11에 관한 이차비잉여이다.
+여기서 주의깊게 봐야할 점은, 11이 [[소수]]라는 것과 정확히 5개의 이차잉여와 5개의 이차비잉여가 있다는 점이다. 이는 모든 소수에대해 성립하며, 증명은 바로 아랫 문단의 성질을 참고하자.
+== 성질 ==
+\(p\)는 홀수인 [[소수]], \(a\)는 \(p\)와 [[서로소]]인 정수, \(r\)은 \(p\)의 [[원시근 (정수론)|원시근]]이라 가정하자.
+#<math>x^2\equiv a\pmod p</math>는 근을 가지지 않거나 정확히 두 개의 근을 가진다.
+#:주어진 [[합동식]]이 근을 가지지 않으면 명제는 자연히 참이다. 만약 \(x_0\)이 주어진 합동식의 한 근이라면, \(-x_0\)도 근이 된다. 또한, \(p\)는 홀수이므로, <math>x_0\equiv-x_0\pmod p</math> ([[기우성]]이 다르다). 이제 \(y\)가 합동식의 또다른 근이라고 가정하자. 그럼 <math>y^2\equiv a\equiv {x_0}^2\equiv p</math>이고, <math>\left(y-x_0\right)\left(y+x_0\right)\equiv0\pmod p</math>이다. 이는 곧 <math>p\mid\left(y-x_0\right)\left(y+x_0\right)</math>임을 의미하고, \(p\)가 소수이므로 <math>p\mid y-x_0</math> 혹은 <math>p\mid y+x_0</math>이다. 어느쪽이든, <math>y\equiv\pm x_0\pmod p</math>이다. 즉, 주어진 합동식은 정확히 두 개의 근만을 가진다.
+#법 \(p\)에 대해 정확히 <math>\frac{p-1}{2}</math>개의 이차잉여와 이차비잉여가 존재한다.
+#:바로 위 성질의 따름정리. 증명은 생략.
+#\(a\)가 법 \(p\)에 대한 이차잉여라면, <math>\operatorname{ind}_ra</math>는 짝수이다. 역도 성립한다.
+#:<math>\operatorname{ind}_ra</math>가 짝수라 가정하자. 그럼, <math>a\equiv r^{\operatorname{ind}_ra}\equiv r^{\left(\frac{\operatorname{ind}_ra}{2}\right)2}\equiv\left(r^{\frac{\operatorname{ind}_ra}{2}}\right)^2\pmod p</math>이다. 따라서, \(a\) 는 법 \(p\)에 대한 이차잉여이다. 역으로, <math>x^2\equiv a\pmod p</math>의 해가 존재한다고 가정하자. 그럼, 한 해 \(x_0\)에 대해 <math>{x_0}^2\equiv a\pmod p</math>이고, 양변에 [[이산로그]]를 씌우면 <math>2\operatorname{ind}_r{x_0}\equiv\operatorname{ind}_ra\pmod{p-1}</math>이다. 따라서, 적당한 [[정수]] \(k\)에 대해 <math>\operatorname{ind}_ra=2\operatorname{ind}_r{x_0}+k\left(p-1\right)</math>이고, \(p-1\)은 짝수이므로 <math>\operatorname{ind}_ra</math>도 짝수이다.
+#[[원시근 (정수론)|원시근]]은 이차비잉여이다.
+#:<math>\operatorname{ind}_rr=1</math>은 홀수이므로 위 성질에 의해 \(r\)은 이차비잉여이다.
+[[르장드르 기호]]를 사용하면 더 많은 성질을 알 수 있다. [[르장드르 기호]]에 관련된 것은 항목 참조.
+== 관련 항목 ==
+*[[모듈러산술]]
+*[[이산로그]]
+*[[르장드르 기호]]
 [[분류:정수론]]