야코비 기호
야코비 기호(Jacobi Symbol) $\Bigg( \frac{a}{n} \Bigg)$의 정의는 다음과 같습니다.
홀수 $n$이 $n = {p_{1}}^{\alpha_1} {p_{2}}^{\alpha_2} \cdots {p_{k}}^{\alpha_k}$으로 소인수분해 될 때,
$$
\Bigg( \frac{a}{n} \Bigg) = \left( \frac{a}{p_1} \right)^{\alpha_1} \left( \frac{a}{p_2} \right)^{\alpha_2} \cdots \left(\frac{a}{p_k}\right)^{\alpha_k}
$$
이다. (좌변이 야코비기호, 우변은 르장드르 기호 )
보통 둘 다 괄호로 표기하기 때문에, 구분이 안 갈 것 같은 상황에서는 쓰는 사람이 무슨 기호인지 꼭 이름을 붙여줍니다.
아래에 나오는 괄호는 특별한 표기가 없으면 모두 야코비 기호입니다.
야코비 기호는 다음과 같은 성질이 성립합니다.
0. $\gcd(a, b)$는 최대공약수 표기
1. $\Bigg(\dfrac{1}{n}\Bigg) = 1$
2. $\Bigg(\dfrac{-1}{n}\Bigg) = {(-1)}^{\frac{n - 1}{2}}$
3. $\Bigg(\dfrac{2}{n}\Bigg) = {(-1)}^{\frac{n^{2} - 1}{8}}$
4. $\gcd(a, n) = \gcd(b, n) = 1$이면, $\Bigg(\dfrac{ab}{n}\Bigg) = \Bigg(\dfrac{a}{n}\Bigg) \Bigg(\dfrac{b}{n}\Bigg)$
5. $\gcd(a, n) = \gcd(b, n) = 1$이고, $a \equiv b \pmod{n}$이면, $\Bigg(\dfrac{ab}{n}\Bigg) = \Bigg(\dfrac{a}{n}\Bigg) \Bigg(\dfrac{b}{n}\Bigg)$
6. $\gcd(m, n) = 1$이면, $\Bigg(\dfrac{m}{n}\Bigg) \Bigg(\dfrac{n}{m}\Bigg) = {(-1)}^{\left(\frac{m - 1}{2}\right)\left(\frac{n - 1}{2}\right)}$ (우변의 $\left(\frac{m - 1}{2}\right)\left(\frac{n - 1}{2}\right)$는 그냥 괄호) / 야코비 기호에서의 이차상호법칙
야코비 기호를 일반화한 크로네커 기호가 존재합니다.
위 성질들을 기반으로 야코비 기호를 구하는 파이썬 코드를 만들면 다음과 같습니다.
pow는 파이썬 pow 함수 입니다.