p진수-3

이제 어떤 방정식에서 p진수로 표현되는 해를 찾기를 시도해 보자. $x^2=2$의 해를 7진수에서 찾아보자.

$|a_n^2-2|_p{\leq}7^{-(n+1)}$을 만족하는 수열$a_n$을 찾을 수 있다면, $a_n$이 기존의 실수에서 $\sqrt{2}$에 해당하는 아주 신기한 값일 것이다. 합동을 이용해서 풀어보자.

$a_0^2{\equiv}2\;mod\;7$

이니 $a_0=3$이다.

$a_1^2{\equiv}2\;mod\;7^2$

이니 $a_1=3+1\cdot7$

$a_2^2{\equiv}2\;mod\;7^3$

$a_2=3+1\cdot7+2\cdot7^2$

이렇게 해서 계속해서 구할 수 있다!

사실 여기에서 미적분학에서 근사적으로 근을 구하는 뉴턴의 방식을 이용할 수도 있다.

$3^2-2\equiv 7\equiv 0\;\;mod\;7$이기 때문에 $a_0=3$라고 할 수 있다.

뉴턴 방법에서 근사해 $a_n$이 있을 때, $a_{n+1}:=a_n-\frac{a^2_n-2}{2a_n}$처럼 다음 근사해를 찾을 수 있으니 이를 이용해 보자.

$a_1=3-\frac{1}{6}7=3+1\cdot7+O(7^2)$

$a_2=3-\frac{1}{6}7+\frac{1}{22}7^2=3+1\cdot7+2\cdot7^2+O(7^3)$

로 계속 찾을 수 있다.

같은 방정식에 대해 초기값을 구할 수가 없기 때문에 3진수나 5진수의 해를 구하는 것을 시도해보면 해가 존재하지 않는다. 미리 스포를 하자면, 어떤 p에 대해 p진수의 해가 존재하지 않기 때문에, 유리수해는 존재하지 않는다는 것도 알 수 있다.

그럼 $x^2=\beta$의 해는 언제 존재할까?

$\beta=u\cdotp^N$라고 해보자. 여기서 $u$는 분자와 분모가 $p$로 나눠지지 않는 유리수이다.

$\alpha^2=\beta$라면 $|\alpha|_p=p^{-\frac{N}{2}}$이기 때문에 N이 적어도 짝수여야 한다.

또한 해가 존재하기 위해서는 $|u|=1$인 $u$가 어떤 $p$진수의 제곱으로 표현되면 된다.

$u=u_0+u_1\cdot p+u_2\cdot p^2+\dots$인 p전개로 표현 가능하고, $u_0$는 0일 수 없다.

여기서 p가 짝수인 경우와 홀수인 경우를 나눠서 생각해보자.

$p\neq2$일 때, u_0가 p에 대한 제곱 잉여라면 뉴턴 방법을 이용하여 해를 찾을 수 있다. 만약에 제곱 잉여가 아니라면 초기값을 찾을 수가 없기 때문에 존재하지 않게 된다.

이 정리를 활용해 보면, 가우스의 이차 상호 법칙의 제2보충 법칙을 이용하면 2가 p에 대한 제곱 잉여일 필요충분조건은 $p\equiv\pm1\;\;mod\;8$인 것을 알 수 있다. 더 일반적인 방법인 헨젤의 보조정리도 있다.

지2러