제곱잉여

1801년 칼 프리드리히 가우스(1777-1855)는 현대 정수론의 토대를 놓은 『Disquisitiones Arithmeticae』를 출간했으며, 이 책은 오늘날까지도 읽히고 있다. 이 책에서 자주 다루어지는 주제 중 하나가 바로 제곱잉여(quadratic residue)이다.

소수 $p$와 $a \not\equiv 0 \pmod{p}$인 정수 $a$가 주어진다. $a$가 $p$에 대한 제곱잉여이려면, 다음을 만족하는 정수 $x$가 존재해야 한다.

$x^2 \equiv a \pmod{p}$

르장드르(1752-1833)는 아래와 같은 르장드르 기호를 정의했다.

$\left(\frac{a}{p}\right) = \begin{cases} 1 & a \text{ 가 } p \text{ 에 대한 제곱잉여인 경우} \\ -1 & a \text{ 가 } p \text{ 에 대한 제곱잉여가 아닌 경우} \end{cases}$

르장드르 기호는 다음 성질들을 이용해 계산할 수 있다. 아래 성질들은 서로 다른 홀수 소수 $p$, $q$와 $p$로 나누어떨어지지 않는 정수 $a$, $b$에 대해서만 성립한다.

1. $\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$
2. $\left(\frac{1}{p}\right) = 1$
3. $a \equiv b \pmod{p} \Rightarrow \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)$
4. $\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}, \quad \left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$
5. $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{(p-1)(q-1)/4}$

예를 들어 르장드르 기호를 다음과 같이 계산할 수 있다.

$\left(\frac{29}{79}\right) = (-1)^{78\cdot28/4} \left(\frac{79}{29}\right) = \left(\frac{79}{29}\right) = \left(\frac{-8}{29}\right) = \left(\frac{-1}{29}\right) \left(\frac{2}{29}\right)^{3} = \left(\frac{-1}{29}\right) \left(\frac{2}{29}\right) = (-1)^{28/2}(-1)^{(29^2-1)/8} = (-1)^{14}(-1)^{105} = -1$

입력은 여러 개의 테스트 케이스로 이루어진다. 첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 각 테스트 케이스는 두 정수 $a$와 $p$로 이루어진다. $p$ $(2 < p < 10^9)$는 홀수 소수이고, $a$는 $a \not\equiv 0 \pmod{p}$와 $\left| a \right| \le 10^9$을 만족한다.

각 테스트 케이스에 대해 첫째 줄에 "Scenario #i:"를 출력한다. 여기서 $i$는 1부터 시작하는 테스트 케이스 번호이다. 다음 줄에 르장드르 기호 $\left(\frac{a}{p}\right)$의 값(1 또는 -1)을 출력한다. 서로 다른 테스트 케이스의 출력 사이에는 빈 줄을 하나 넣는다.