크로네커 기호

다른 뜻에 대해서는 크로네커 델타 문서를 참고하십시오.

수론에서, 크로네커 기호(영어: Kronecker symbol)는 야코비 기호를 임의의 정수로 확장한 함수이다. 기호는 ${\displaystyle \left({\frac {a}{n}}\right)}$ 또는 ${\displaystyle (a|n)}$.

정의

임의의 정수 ${\displaystyle a\in \mathbb {Z} }$가 주어졌다고 하자. 크로네커 기호

${\displaystyle \left({\frac {a}{\cdot }}\right)\colon \mathbb {Z} \to \{-1,0,1\}}$

는 다음과 같다.

1. ${\displaystyle \left({\frac {a}{0}}\right)={\begin{cases}1&a=\pm 1\\0&a\neq \pm 1\end{cases}}}$
2. ${\displaystyle \left({\frac {a}{-1}}\right)={\begin{cases}1&a\geq 0\\-1&a<0\end{cases}}}$
3. ${\displaystyle \left({\frac {a}{2}}\right)={\begin{cases}0&2\mid a\\1&a\equiv 1,7{\pmod {8}}\\-1&a\equiv 3,5{\pmod {8}}\end{cases}}}$
4. 홀수 소수 ${\displaystyle p}$에 대하여, ${\displaystyle \left({\frac {a}{p}}\right)}$는 르장드르 기호와 같다.
5. 0이 아닌 정수 ${\displaystyle n}$에 대하여, 그 소인수 분해가 ${\displaystyle n=u\prod _{p}p^{n_{p}}}$라고 하였을 때 (${\displaystyle u\in \{-1,1\}}$), $${\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {a}{u}}\right)\prod _{p}\left({\frac {a}{p}}\right)^{n_{p}}}$$

일부 저자는 ${\displaystyle a}$가 ${\displaystyle a\equiv 0,1\!\!\!{\pmod {4}}}$인 제곱 인수가 없는 정수인 경우에만 크로네커 기호를 정의한다. 일부 저자는 ${\displaystyle a}$가 기본 판별식인 경우에만 크로네커 기호를 정의한다.

성질

디리클레 지표와의 관계

임의의 정수 ${\displaystyle a\in \mathbb {Z} }$에 대하여, 다음 두 조건이 서로 동치이다.

• ${\displaystyle \left({\frac {a}{\cdot }}\right)}$는 디리클레 지표이다.
• ${\displaystyle a\not \equiv 3{\pmod {4}}}$

만약 ${\displaystyle a}$가 기본 판별식이라면, ${\displaystyle \left({\frac {a}{\cdot }}\right)}$는 원시 ${\displaystyle a}$-디리클레 지표이다.

주기성

크로네커 기호는 다음과 같은 주기를 갖는다.

• 만약 ${\displaystyle a\equiv 0,1{\pmod {4}}}$라면, ${\displaystyle \left({\frac {a}{\cdot }}\right)}$는 주기 함수이며, 주기 ${\displaystyle |a|}$를 갖는다. (이는 최소 주기가 아닐 수 있다.)
• 만약 ${\displaystyle a\equiv 2{\pmod {4}}}$라면, ${\displaystyle \left({\frac {a}{\cdot }}\right)}$는 주기 함수이며, 주기 ${\displaystyle 4|a|}$를 갖는다. (이는 최소 주기가 아닐 수 있다.)
• 만약 ${\displaystyle a\equiv 3{\pmod {4}}}$라면, ${\displaystyle \left({\frac {a}{\cdot }}\right)}$는 주기 함수가 아니지만,^{[1]:365, Theorem 3.2} 퇴플리츠 열(영어: Toeplitz sequence)을 이룬다.^{[1]:366, Remark 3.4}

이차 상호 법칙

임의의 두 0이 아닌 정수 ${\displaystyle m,n\in \mathbb {Z} \setminus \{0\}}$에 대하여, 다음과 같은 항등식이 성립한다 (이차 상호 법칙).^{[1]:364[2]:43, Exercise 19}

${\displaystyle \left({\frac {m}{n}}\right)=\sigma (m,n)(-1)^{(m'-1)(n'-1)/4}\left({\frac {n}{m}}\right)}$

여기서

• ${\displaystyle \sigma (m,n)={\begin{cases}1&m>0\lor n>0\\-1&m,n<0\end{cases}}}$
• ${\displaystyle m'}$과 ${\displaystyle n'}$은 각각 ${\displaystyle m}$과 ${\displaystyle n}$의 최대 홀수 양의 약수이다.

계산 복잡도

절댓값이 ${\displaystyle n}$ 이하인 두 정수의 크로네커 기호의 계산 복잡도는

${\displaystyle O(\ln ^{2}n)}$

이다.^[2]:31