6. 이차잉여 (르장드르기호, 야코비기호)

Posted by Bitssam
2015. 7. 18. 17:52 전공수학/Number Theory

VI. 이차잉여


 이제 방정식을 풀기전 하나의 관문을 남겨두고 있다. 본 포스팅의 구성상 방정식의 풀이를 한꺼번에 다루기로 한 바 배경이 되는 개념을 먼저 제시한 후 종합적으로 방정식의 풀이를 제시할 것이다.

 이차잉여란 수가 제곱수인지 판별한다. 이는 이차합동방정식을 푸는데 필요한 개념이다. 실수계에서야 제곱을 그저 제곱근을 통해 역연산하면 그만이었지만. 정수방정식에서는 역연산이 안되는 경우가 더 많다. 그래서 제곱을 풀어주기전 이것이 제곱수인지를 체크하게 되는데 제곱수이면 이 수를 이차잉여라고 한다. 즉, 이차잉여이면 제곱은 풀릴 수 있으며 이차방정식의 풀이가 가능하다는 것이다. 이 장에서는 이차잉여와 이를 나타내는 기호인 르장드르기호, 야코비기호에 대해 알아볼 것이다.


1. 이차잉여


 위에서 설명하였듯이 이차잉여란 수가 제곱수여서 제곱이 풀리는 것을 의미한다. 그렇지 않으면 이차비잉여이다.


$m \ge 3$ , $a \in U(Z_m)$ 일 때

(1) d : 법 m에 관한 이차잉여

 $\Leftrightarrow \exists x \in Z\;s.t.\;{x^2} \equiv d$ (mod m)

(2) d : 법 m에 관한 이차비잉여

 $\Leftrightarrow \nexists x \in Z\;s.t.\;{x^2} \equiv d$ (mod m)



2. 르장드르 기호


페르마의 소정리를 살펴보면서 다음과 같은 정리를 보았을 것이다.

p : 홀수인 소수 ,  (a, p)=1일 때

${a^{\frac{{p - 1}}{2}}} \equiv 1$ , ${a^{\frac{{p + 1}}{2}}} \equiv - 1$ (mod p)중 꼭 하나만 만족한다.


왜냐하면 $0 \equiv {a^{p-1}} - 1 \equiv ({a^{\frac{{p - 1}}{2}}} - 1 ) ({a^{\frac{{p - 1}}{2}}} + 1 )$ (mod p)이므로

${a^{\frac{{p - 1}}{2}}} \equiv \pm 1$ (mod p)이 성립하나 $1 \equiv - 1$ (mod p)이려면 p|2 인 이는 모순이다.


위 정리에 따르면 $a^{\frac{p-1}{2}}$ 꼴의 수는 1 또는 -1과 합동이라는 것이다. 그렇다면 이차잉여인 수와 이차 비잉여인 수는 이러한 꼴에 대입하였을 때 1이 되는지 -1이 되는지 알아보자.


이차잉여인 수는 어떤수의 제곱꼴이다. 이를 $d \equiv a^2$이라 표현해보자. 그렇다면

$d^{\frac{p-1}{2}} \equiv a^{p-1} \equiv 1$


반대로 이차비잉여인 수는 어떤 수의 제곱꼴이 아니므로 -1이 된다. 이를 정리하면 다음과 같다.


 $p \ge 3$인 소수 p에 대하여

$a^{ \frac {{ p-1 } }{ 2 }}\equiv \begin{cases} 1\quad (mod\; p)\quad (a:\; 법\; p에\; 관한\; 이차잉여) \\ -1\quad (mod\; p)\quad (a:\; 법\; p에\; 관한\; 이차비잉여) \end{cases}$

       =: $\left( \frac { a }{ p }  \right)$ (르장드르 기호)


르장드르기호의 기본적인 연산은 다음과 같다.


$p:\; 홀수인\; 소수,\quad a \not\equiv 0\quad (mod\; p),\quad b \not\equiv 0\quad (mod\; p)$에 대하여


(1) $\left( \frac { a^{ 2 } }{ p }  \right) =1, \quad \left( \frac { 1 }{ p }  \right) =1 $ (제곱수는 반드시 이차잉여)

(2) $a\equiv b\; (mod\; p)\Rightarrow \left( \frac { a }{ p }  \right) =\left( \frac { b }{ p }  \right)$ (합동인수는 반드시 르장드르 기호값이 같다)

(3) $\left( \frac { ab }{ p }  \right) =\left( \frac { a }{ p }  \right) \left( \frac { b }{ p }  \right) , \quad \left( \frac { -a }{ p }  \right) =\left( \frac { -1 }{ p }  \right) \left( \frac { a }{ p }  \right)$ (곱셈은 분모는 두고 분자만 곱하면 된다.)

(4) $\left( \frac { 1 }{ p }  \right) +\left( \frac { 2 }{ p }  \right) +\cdots +\left( \frac { p-1 }{ p }  \right) =0$ (1부터 p-1까지의 이차잉여의 개수, 이차비잉여의 개수가 같으므로)


르장드르기호 중 a=-1, 2에 대한 연산은 결과값으로 알려져 있다.


 (1) $\left( \frac { -1 }{ p }  \right) =(-1)^{ { \frac { p-1 }{ 2 }  } }=\begin{cases} 1\quad \quad \quad \quad p\equiv 1\; (mod\; 4) \\ -1\quad \quad \quad p\equiv 3\; (mod\; 4) \end{cases}$

 (2) $\left( \frac { 2 }{ p }  \right) =(-1)^{ { \frac { p^{ 2 }-1 }{ 8 }  } }=\begin{cases} 1\quad \quad \quad \quad p\equiv \pm 1\; (mod\; 8) \\ -1\quad \quad \quad p\equiv \pm 3\; (mod\; 8) \end{cases}$


르장드르기호의 분모분자가 바뀌면 어떻게 될까? 이에 대한 법칙이 이차상반법칙(이차상호법칙)이다.


 $\left( \frac { q }{ p }  \right) =\left( \frac { p }{ q }  \right) (-1)^{ { { \frac { p-1 }{ 2 }  }\cdot \frac { q-1 }{ 2 }  } }=\begin{cases} -\left( \frac { p }{ q }  \right) \quad \quad p\equiv q\equiv 3\; (mod\; 4) \\ \left( \frac { p }{ q }  \right) \quad \quad \quad 그외의\; 경우 \end{cases}$


3. 야코비 기호


야코비 기호는 르장드르기호를 일반화하여 소수분모를 홀수분모로 확장하여 적용한 기호이다.


 $P=p_{ 1 }^{ e_{ 1 } }\cdots p_{ r }^{ e_{ r } }$ : 3이상의 홀수 p의 표준분해, $a \in U(Z_p)$일 때,

$\left( \frac { a }{ P }  \right) :=\left( \frac { a }{ p_{ 1 } }  \right) ^{ e_{ 1 } }\cdots \left( \frac { a }{ p_{ r } }  \right) ^{ e_{ r } }$ (a의 야코비 기호)


야코비기호와 르장드르기호의 연산법은 같다. (위에 있는 것 전부 적용 됨)

'전공수학 > Number Theory' 카테고리의 다른 글

8. 연분수  (0) 2015.07.18
7. 방정식의 풀이 (종합편)  (0) 2015.07.18
5. 원시근과 이산로그  (0) 2015.07.18
4. 페르마소정리, 오일러정리  (0) 2015.07.18
3. 합동식  (0) 2015.07.18